A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time of at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer. These algorithms take a number of steps polynomial in the input size, e.g., the number of digits of the integer to be factored.
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
I want to contrast this paper with Shor's factoring paper [1].
One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work. Also, given a working seed, sometimes the quantum sampling process can correctly return a useless result. He bounds how often that can occur as well. He never says "I think this problem is rare so it's probably fine", instead he says "this problem is at least…
Read the full comment
this rare therefore it is fine". Essentially the only real problem not addressed by the paper was that it required arbitrarily good qubits... so he went and invented quantum error correction [2].
The paper being discussed here [3] does not strike me as meticulous. It strikes me as sloppy. They are getting good numbers by hoping potential problems are not problems. Instead of addressing the biggest potential showstoppers, they have throwaway sentences like "It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA".
How many shots are needed for each sample point fed into the classical optimization algorithm? How many steps does the optimization algorithm need? How do these scale as the problem size is increased? How big are they for the largest classically simulable size (RSA128 with 37 qubits according to their table)? These are absolutely critical questions!... and the paper doesn't satisfyingly address them.
Is there somewhere where I can bet money that this doesn't amount to anything?
1: https://arxiv.org/abs/quant-ph/9508027
2: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2...
3: https://arxiv.org/abs/2212.12372
Shor's original paper discusses the fundamental need for several runs and gives the time complexity.
https://arxiv.org/pdf/quant-ph/9508027.pdf
The paper you linked to is just saying that the need for several runs and 2006 readout error rates together led to awful scaling (though still better than classical factorisation). That isn't surprising. Error rates in all parts of even modern quantum computers are still too high to scale well. Especially when repetition is called for.
Ultimately, complexity is calculated using logical qbits. Kalai doesn't think that even with error correction codes we can get close enough. Most other people think we can. That paper you linked to is just making the point that we're definitely not there yet. When we do, algorithms in BQP will still need several runs on many algorithms (the exact same way as algorithms in BPP do) but that should already be incorporated into those algorithm's complexity.
@tptacek
> I believe you to be wrong about the idea that tenably factoring 1024 or 2048 bit moduli implies a solution to the elliptic curve discrete modulus problem
Probably. This mathy stuff is way over my head. I'm just repeating what I read in Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer [1] published by Peter W. Shor on behalf of AT&T Research in 1995. Supposedly his proof is valid, predicated on the existence of quantum computers. Quantum computers actually exist [insert epistemological joke here].
[1] https://arxiv.org/abs/quant-ph/9508027v2
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will.