Shor's algorithm for factoring in polynomial time on a quantum computer\cite{Shor} gives an enormous advantage over all known classical factoring algorithm. We demonstrate how to factor products of large prime numbers using a compiled version of Shor's quantum factoring algorithm. Our technique can factor all products of $p,q$ such that $p,q$ are unequal primes greater than two, runs in constant time, and requires only two coherent qubits. This illustrates that the correct measure of difficulty when implementing Shor's algorithm is not the size of number factored, but the length of the period found.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
> By late 2024 the biggest numbers that had been factored by an actual digital quantum computer had 35 bits (citing https://arxiv.org/pdf/2410.14397v1 )
This is incorrect. The cited reference says "N <= 35". That N is the number being factored, not the number of bits in the number. Also, footnote a of that paper points out (correctly) that the circuits that were used likely needed knowledge of the factors to create (e.g. as explained in https://arxiv.org/abs/1301.7007 ). As far as I know, only N=15 has been factored on a quantum computer in a no-shenanigans way.
It's conceivable that current ion trap machines could do a no-shenanigans N=21.... but anyone judging progress in quantum computing by largest-number-factored is looking at the wrong metric (for now). You won't see that metric move meaningfully until quantum error correction is done spinning up.
Even 21 was only possible by cheating (optimizing away the difficult part using prior knowledge of the results) [1]. Craig Gidney has a blog post that shows the actual quantum circuit for factoring 21 which is far beyond the capabilities of current quantum computers [2].
[1] https://www.nature.com/articles/nature12290
[2] https://algassert.com/post/2500
They were illegitimate instances of Shor according to [1]:
> Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice. While there is no objection to having a classical compiler help design a quantum circuit (indeed, probably all quantum computers will function in this way), it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language.
[1] https://arxiv.org/pdf/1301.7007
Factoring 15 with quantum computers happened nearly 22 years ago[1]. The current record for factoring, with just Shor's and no minimization, is 21. Like you said, a lot of the hyped ones aren't practical. It's not that hard to pretend to factor large numbers on a quantum computer [2]. There have been a few newer algorithms can work with larger numbers, but they have scaling issues and so aren't useful for cryptography.
[1]https://research.ibm.com/blog/factor-15-shors-algorithm [2]https://arxiv.org/abs/1301.7007
For those who are interested in the papers about this topic:
https://arxiv.org/abs/1301.7007
"Pretending to factor large numbers on a quantum computer (2013)"
"Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however,
illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees,
all previous factorization experiments have benefited from this artifice. While there is no objection
to having a classical compiler help design a quantum circuit (indeed, probably all quantum
computers will function in this way), it is not legitimate for a compiler to know the answer to the
problem being solved. To even call such a procedure compilation is an abuse of language."
More references:
https://crypto.stackexchange.com/questions/59795/largest-int...
Two excellent questions.
Regarding claims of factoring small numbers: First note that error correction becomes exponentially more important for longer computations. Second, see this
https://arxiv.org/abs/1301.7007
Regarding building a tower of ever less noisy qubits: it turns out there is something called a threshold theorem which requires a certain minimal level of noise before concatenating error correction schemes makes things better rather than worse.
https://en.m.wikipedia.org/wiki/Quantum_threshold_theorem
Reaching this threshold for physical qubits in the laboratory is perhaps the primary goal of experimental quantum computing.
> For the record, this is also true for every quantum computer in existence.
Yes, I'm well aware. The difference from D-wave is that the labs at IBM, UCSB, and Yale haven't claimed they've built a quantum computer (mostly).
> What is clear though, is that quantum computers have already solved problems in fewer steps than classical computers.
This is statement is false and probably not even interpretable in a sensible way. See, for instance, my esteemed colleagues on why some labs' claims to have factored small numbers like 15 are bogus:
http://arxiv.org/abs/1301.7007
> And to be fair, it's going to take a while to beat current computers. We've had decades to get them…
Read the full comment
faster and faster, and we will need some time because we can perform low level operations nearly as fast and get enough qubits to get to sizes of problems that classical computers have issues with
Although it will take a while, it will probably not be because classical computers are so great. I could be wrong (I'm no expert and there could always be scaling surprises), but I'm willing to bet it takes us longer until we perform the first quantum computation that can't be done by hand than between that time and the time when we perform a computation that can't be done with a classical computer.
The short version is that you're mistaken about how research in quantum computers has been progressing. There have been fantastic successes and advances, but they cannot be measured by "number of qubits" or "difficulty of computations done". There simply haven't been any real computation performed. You should think of researchers at the stage of still trying to get the first transistor to work, not the Moore's-law stage of trying to cram the 2^Nth transistor into the silicon.
It depends how much circuit optimization you consider to be cheating.
The hard part of Shor's algorithm is computing `pow(g, e, modulus=N)` where g is a uniformly random number, e is a uniformly superposed number, and N is the number you want to factor. But note that 15 is one less than a power of 2, so modular arithmetic mod 15 can use special circuits that are surprisingly efficient. Since it's easy to check if a number is one less than a power of 2, there's no obstacle to using this optimization on a "real" problem. On the other hand, most products of two primes aren't one less than a power of 2 and so this case is absurdly rare. So is using the more optimized circuit…
Read the full comment
allowed or isn't it?
It get so much worse. In [1] it's shown that, if you know the factors behind a factoring problem of any size, you can derive constant sized quantum circuits that "solve it". Basically, you can force Shor's algorithm into a trivial corner case and then implement the corner case. For all intents and purposes this makes the quantum computer irrelevant. E.g. I used this result for an April fool's post where I "factored" the largest number ever "with" a quantum computer [2].
The other problem with Shor's algorithm on small cases is that as soon as you get a "correct" output from the quantum part the following classical part will succeed. But for small cases there are too few possible outputs. Even if the quantum computer is totally broken and generating random noise, the algorithm will still succeed pretty quickly. So you need to define success as some kind of noise metric to beat, instead of as actually solving the problem.
Here is maybe something that will answer the intent of your question. I haven't checked on this particular chip, but from experience with running things on various quantum computers and from the numbers in the data sheet, I can confidently say that this chip will struggle to count to 10 before suffering an error. A 4-qubit increment circuit is going to use at least 10 two-qubit gates [3], you need to increment 10 times, and the listed two qubit gate error rates are around 1%. So presumably the success rate is going to be on the order of (99%)^(10*10) ~= 35%.
Disclaimer: I work on the google quantum team.
1: https://arxiv.org/abs/1301.7007
2: https://algassert.com/post/2000
3: https://quantumcomputing.stackexchange.com/a/3975/119
In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.