Grover's algorithm offers no quantum advantage
arxiv.org
arxiv.org
1. A quantum computer is not a magic exponentially parallel computer. There's a fairly common misunderstanding of quantum computers that goes like this: a quantum state is a superposition of classical states. So a classical number with n bits of RAM is in one of 2^n states, but a quantum computer is in all of them at once, with an "amplitude" that takes the form of a complex number associated with each state. And you can compute things exponentially faster because you can compute with this whole 2^n-element vector at once!
This is just a tiny bit true (you can, in fact, write the state of a quantum computer like that), but quantum computers do discrete operations, you can't read the vector directly and, in general, you can't actually get this magic factor-of-2^n speedup naively, nor can you get any speedup at all unless you are doing something clever.
But, for some reason, this paper buys into this myth with its quantum-inspired classical algorithm. It's magic! You compute the Grover oracle and get:
|s> - sum over all n-bit "winner" strings w_i (|w_i>)
And the form of that expression barely matters, nor does whether I transcribed it right or whether you read it right. Because, if you can literally just look at the coefficients (of which there are 2^n!), you can easily find all the "winners". And that would take, shocker, 2^n guesses on a regular computer, or O(2^(n/2)) on a quantum computer with Grover's algorithm. So they've invented a really stunningly bad way to implement brute-force search on a classical computer using fancy math, and you would do much better trying to solve SAT by simply checking each possible input one-by-one. News at 11.
2. They have entirely missed the point of quantum error correction. Here's the classical analogue, as observed by John von Neumann in 1956 [0]: if you build a computer (or a brain!) out of unreliable components, then, as you do a longer an longer computation, the chance that you get the right answer seems like it would decay exponentially or worse. But our brains work pretty well and computers work pretty well! von Neumann proved that it is possible to design an computer out of unreliable parts that is nonetheless reliable by inserting error correction steps regularly in a carefully arranged way. (Of course, modern semiconductor technology is so amazingly good that you can get quite far with no error correction. Although we're at the point that you need ECC RAM for really good results.) What you cannot do is run a computer that screws up each gate with, say, probability 0.001%, carelessly run a calculation of any appreciable length, and expect any reasonable chance of getting the right answer.
Again, news at 11 -- this stuff has been known since at least the 1950s.
In quantum computing, the situation is exactly the same, except the numbers are worse and the error correction is a lot harder. No one expects quantum gates to ever be nearly as good as a CMOS gate. Nonetheless, Peter Shor and others proved the threshold theorem [1], which shows that you can take a quantum circuit and implement it (with more memory and more gates!) in a way that increases complexity only by a polynomial factor and gets the right answer arbitrarily close to 100% of the time. This is really cool! But you have to error correct your memory, and you have to error correct the calculation as you do it.
So this paper somehow missed the entire point, computes the degree to which the algorithm is sensitive to noise if you run the whole thing without error correction, determines that the output is not even close to correct, and gives up. No kidding! The fact that this doesn't work has been known for about as long as anyone has been thinking about quantum computers at all. It would be like running a year-long calculation without ECC memory and expecting that you can make up for the lack of ECC memory by simply repeating the calculation until you get lucky and get no errors. Nope, doesn't work.
edit: Huh, Appendix C of this paper acknowledges the existence of something vaguely resembling the threshold theorem, and then proceeds to do a calculation showing that a particular (asymptotically suboptimal) construction isn't good enough to make Grover's algorithm useful. I'm not impressed. Maybe paper's title should be changed: "A badly implemented quantum algorithm may not outperform an totally ridiculous classical algorithm, but we didn't bother to analyze the classical algorithm very well and we are merely hypothesizing that there exist problems for which it's better than exhaustive search."
[0] https://www.degruyter.com/document/doi/10.1515/9781400882618...
Suppose you have gates (quantum or CMOS -- doesn't matter), and they are imperfect. And you want to implement some algorithm that won't work without error correction. So you use an error-correcting code of complexity c. (Classically, this could be as simple as copying every memory cell c times and taking a majority vote of c attempts of each gate. Some extra complication is needed to put the pieces together while still getting exponentially close to 100% accuracy.)
So you start by setting c=3 (majority vote of three tries), and you get really really far. But you need a longer calculation, so you go up to c=5. Then c=7. Then c=9. And so on.
And you discover that this actually scales pretty poorly. This is because the little gizmo that takes a majority vote is itself error-prone, and just making it wider doesn't improve fast enough with increasing width.
But you can instead use recursive error correction. Take c=3, look at the result as its own imperfect computer, and error-correct that with a second code with c=3. It's kind of like c=9, except all the little majority-of-three voting gizmos become majority-of-majorities-of-3 instead of majority-of-9 gizmos, and you get a natural way to make them arbitrarily wide.
And (IIRC -- it's been quite a while since I've gone through the whole derivation), this works! You can recurse this construction (or at least something quite similar) a number of times that grows sufficiently slowly in the size of the circuit that you get the overall O(t * polylog(t)) scaling that you want.
To make this work on a quantum computer is much harder (majority-of-3 doesn't work at all -- you need a bare minimum of 5 physical qubits per logical qubit for anything resembling this to work, and it's not a majority vote per se), but the overall conclusion is the same.
The paper looks at what coding width is needed without recursion to make Grover's algorithm work for large problems, concludes that you at least square the complexity, and decides that Grover's algorithm is useless. But anyone actually trying to do a huge Grover search would use a proper recursive code, and they wouldn't have this problem.
And this has known since 1996.
However! I believe that Grover's algorithm will not be a very big deal, at least in early-ish quantum computers.
* The speedup is proportional to the depth of the quantum computation, measured in oracle calls. So we're talking maybe 2^40 speedup, not 2^64 or 2^128.
* There is a significant cost in converting practical algorithms to run on a QC, because QC algorithms have to be reversible.
* Early QCs will have a huge overhead from quantum error correction.
* Just guessing, but early QCs will probably have lower clock speed (taking long to compute a gate than a classical computer uses for a whole clock period), a higher fabrication cost and a vastly higher error energy usage due to the fridge and classical electronics.
Divide that 2^40 by all these factors and you can see that it won't get very far, at least until all these "early QC" problems can be solved. So the impact on symmetric crypto probably won't be much at all, but moving from 128-bit keys to 192-bit keys would be plenty.
The above mostly does not apply to Shor's algorithm. Shor might be slow on early QCs, but it's exponentially faster than any known classical algorithm, instead of only linearly faster.
I'm not aware of problems with the AES block size and key size not matching... is there some cryptanalysis in that direction? On the contrary, I'd thought that AES-256 had a slightly shakier key schedule than AES-128 or -192, though due to the longer key it is still stronger than AES-192 vs known attacks.
In a future draft we will bring out this point more clearly, but we do not unroll the post-oracle state into a vector of size 2^n and just look at the winners. We use a well-established sampling technique from the matrix product state literature (reference: https://arxiv.org/abs/1201.3974, also cited in the paper) which runs deterministically and always scales as log(N) = n. (This part is independent of the oracle used.)
Overall our approach scales as log(N) for cases where the oracle can be simulated in polynomial time. We give such a case explicitly in the paper. Of course for many oracles, applying the oracle will scale exponentially which we say, but we show that there exist quite a few instances (we could show many more) where the actual time is minutes or hours to sizes of qubits (e.g. 40 qubits) that would require a million iterations of Grover's algorithm if it were run on a physical quantum computer.
"IV. A QUANTUM INSPIRED ALGORITHM FOR SIMULATING GROVER’S ALGORITHM IN A SINGLE CALL TO THE ORACLE"
The net result is that for the worst case of oracles, Grover's algorithm is still faster than a classical computer.
(1) "Our finding implies that there is no a priori theoretical quantum speed-up associated with Grover’s algorithm"
(2) "we show that there is no theoretical quantum advantage unless proven otherwise and quantum advantage has to be decided in a case-by-case manner"
(1) is surprising (at least for me). I took the quadratic speedup of GA as proven.
(2) concedes that GA may be faster for certain quantum oracles but it has to be shown.
Further they completely ignore that when you open up the oracle like they have done, the problem they are considering is really CIRCUIT-SAT, and in this case the grover algorithm yields a 2^{n/2} algorithm whereas the best classical algorithm is 2^n. That the classical algorithm cannot do better that 2^n is the "exponential time hypothesis". I don't think the authors want to claim that they have disproven this hypothesis, since they didn't really. They just showed in some cases, in CIRCUIT-SAT, the problem is easy. This is a fairly benign, "yes...and....", statement.
So I think this is word games where the game the authors has played is to chose the worst words to describe their result. It's a bit sad because the authors are trying to think about the role of entanglement in these algorithms, and where entanglement is low we know that we can efficiently simulate classically these quantum systems.
The first half of the paper, about opening up the oracle is written by definition for people who don't know it, as is the case in any article. Personally knowing about something but which is not published is not a valid or helpful criticism of a published work (or preprint). On the other hand we could not find any publications talking about opening the oracle in the context of attempting to simulate it nor discussing entanglement barriers in the oracle (other than giving unhelpfully general worst-case bounds). The one exception is the following paper by Chamon and Mucciolo https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.10.... If you know of some publications you could point us to, we'd be happy to incorporate them into a later draft of the article and cite them.
"There are many cases where it's already known one doesn't need Grover's algorithm, such as if a problem already has a polynomial-time solution. We have now identified a new set of cases where one doesn't need Grover's, which is where the oracle can be simulated only once by a tensor network (or log(N) times in a "closed" simulation".
So the point of that part of the article is to further delineate when Grover's algorithm is actually needed or not needed. It only applies to real-life problems where one must actually know the circuit.
And thanks for your lecture notes.
We don't know how noise will scale IRL so the job of theoretical scientists is to design the basic units of quantum computation regardless of how it may or may not work IRL. It's like judging XOR and NAND in 1920s because transistors maybe won't be able to simulate them.
Grover's algorithm is quite complex and I'm not qualified to say much about how it works, but I do know that the underlying mathematics is very different.
I haven't read it in detail, but the abstract is so absurd that I won't bother.
Before, folks were saying we had to double the key length.
Symmetric crypto and hashes have never really been considered at risk except for very small sizes.
Grover’s algorithm is essentially just a square root improvement on the search complexity for finding the symmetric key. That means the search complexity remains exponential and the encryption is still secure - we might want to increase the key size[1], but that is all that is needed. The attacks on asymmetric ciphers mean increasing the key size isn’t a meaningful solution.
[1] currently under classical attack aes128 is “secure”, and assuming no algorithmic weakness being discovered will remain so for a while. However most modern protocols have increased to 256 but keys already as a pre-emotive defense against increasing classical computing capacity. Grover’s algorithm logically reduces the strength of a 256 bit key to 128 bits, but doing so requires quantum computers which so far seem to have some fundamental performance limits that leads me to not being overly concerned. I’d be more concerned about a quantum attack on aes128 as complexity on the order of 2^64 becomes much more plausibly broken.
My understanding is there’s a fair bit of quantum computation research that uses Grover’s algorithm as a building block, and this paper pulls that foundational stone out from under them.
It is entirely possible that there is more than enough margin in 128 bit keys to prevent a successful Grover's based attack.