No, there was no such demonstration.
Quote from https://eprint.iacr.org/2015/1018.pdf:
As pointed out in [57], there has never been a genuine implementation of Shor’s algorithm. The only numbers ever to have been factored by that type of algorithm are 15 and 21, and those factorizations used a simplified version of Shor’s algorithm that requires one to know the factorization in advance. In [13,15] the authors describe how a different algorithm that converts integer factorization to an optimization problem can be used to factor significantly larger integers (without using advance knowledge of the factors). However, the optimization problem is NP-hard and so presumably cannot be solved in polynomial time on a quantum computer, and it is not known whether or not the sub-problem to which integer factorization reduces can be solved efficiently at scale. So most experts in the field prefer to gauge progress in quantum computing not by the size of numbers factored (which would lead to a very pessimistic prognosis), but rather by certain engineering benchmarks, such as coherence time and gate fidelity.The quantum papers on "factorization as optimization" are borderline scams though. I wouldn't put those papers in the same sentence as Shor.
I can't quite get this - surely until we have an execution on the proper hardware we can't accept that it works? There are engineering problems to resolve before we can be confident - perhaps they can be easily resolved, but so far they haven't.
I would be very curious to learn what the barriers to a demonstration of Shores on an arbitrary 8bit prime are...
The limiting factor in practice, as with everything quantum, is noise. You are right -- we don't know for certain until it's implemented. I suppose it's part of a bigger question: whether quantum computing will work at all. My knowledge of quantum hardware is limited, so I can't really comment more on this.
T_T
You could replace the quantum chip with a classical signal processor decoding the gates to perform, feeding them to a Clifford simulator, and it would solve the problem just fine. They're just arbitrarily declaring that the classical computer isn't allowed to do the thing that solves the problem fast, because that would "violate the black box condition", despite the fact that their quantum compilation and error mitigation pipeline also has to violate the black box condition.
As with many quantum papers, you should ignore the headline and just focus on how large the circuits are:
> Our current implementation of Simon’s problem requires roughly 400 two-qubit gates (after compilation) and 60 qubits
So a few hundred gates. A few times smaller than random circuit sampling experiments from 2019, though much cheaper to verify and simulate.
ForOldHack•1w ago
https://en.wikipedia.org/wiki/Hidden_subgroup_problem
thesz•1w ago
Complete quote: "...we demonstrate an algorithmic quantum speedup for a variant of Simon’s problem where the hidden period has a restricted Hamming weight . For sufficiently small values of ..."
If we know that hidden period is exactly k bits away, we can generate C(k,n) samples, which puts us into polynomial complexity class in classical case, not exponential.
So, hold you "wow"s.