Grover's algorithm offers no quantum advantage(arxiv.org)
arxiv.org
Grover's algorithm offers no quantum advantage
https://arxiv.org/abs/2303.11317
34 comments
For those who are curious, here's the specific thing that Appendix C misses.
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.
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.
Yeah, this article seems pretty wrong to me.
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.
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.
AES-192 is a bit weird, I'd use AES-256 instead because it gives you more buffer against the problems caused by the block size and key size not matching. Or just use ChaCha20 in an AEAD configuration.
Sure, AES-256 or ChaCha20 is probably an even better choice. I just mean to say that even a 192-bit key is comfortably out of reach of Grover-assisted brute-force for the foreseeable future, which would not be true if Grover effectively halved the key size.
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.
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.
I'm actually not sure, I would need to look at it again. As you said, AES-128 is probably the most sound in a theoretical sense, but AES-256 stronger against brute force and that makes up for the theoretical problems. AES-192 is a weird middle option that's less strong against brute force than AES-256, and is also theoretically less sound that AES-128.
As one of the authors, I'm ok with reasonable disagreements (e.g. see D. Bacon's below) about whether our overall conclusions are justified. But I feel it important to point out that your comment above is just a pure misrepresentation of the procedure in our paper.
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.
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.
These comments assume readers are deeply familiar with the workings of quantum computers. Here's a brief background on Glover's algorithm for those who are new: https://vertex.pub/Grover-s-Algoritm-3f98327e2e84482a93846d4...
I miss the connection between your paragraph "1." and the classical algorithm in the section:
"IV. A QUANTUM INSPIRED ALGORITHM FOR SIMULATING GROVER’S ALGORITHM IN A SINGLE CALL TO THE ORACLE"
"IV. A QUANTUM INSPIRED ALGORITHM FOR SIMULATING GROVER’S ALGORITHM IN A SINGLE CALL TO THE ORACLE"
The “quantum inspired algorithm” simulates a call to the oracle and then reads off the amplitudes. The latter part is not something a quantum computer can do.
There are some word games going on here. They propose a classical algorithm that uses the oracle exponentially fewer times than Grover's algorithm. But they're using a special definition of what it means for a classical algorithm to use a quantum oracle, meaning that each classical 'use' can take exponentially longer than a quantum computer using the oracle.
The net result is that for the worst case of oracles, Grover's algorithm is still faster than a classical computer.
The net result is that for the worst case of oracles, Grover's algorithm is still faster than a classical computer.
There are no word games.
(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.
(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.
They moved the goal posts to misrepresent Grover speedup. Taking an oracular result and opening the box, in almost all cases, changes the query complexity speed up. Yes we've known that since, well since people thought about oracular speedups. Periodically someone notices this, writes up a paper pointing it out, and then promptly is forgotten about because it misses the point.
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.
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.
Your comment is helpful to us to see what are some common misunderstandings about what we are saying in our paper versus not saying. It could be some problems with our writing. For example, we state all of the things you said above explicitly in the paper and wrestle with them in quite a few places. Also there is a whole second half of the paper that addresses precisely the question of "what if we have an instance that we can't classically simulate? i.e. scales as 2^n?". Your comments don't address that part of the paper.
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.
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.
To clarify a bit more, for us the purpose of opening the oracle and simulating it, whether or not we were the first ones to do it (e.g. we weren't, see Chamon paper above) was to say that
"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.
"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.
Great to see a real expert here.
And thanks for your lecture notes.
And thanks for your lecture notes.
Yeah, very few speedups can actually be proven. For all we know, P = PSPACE. In which case everything in between those two classes becomes polynomial, including all quantum speedups and also NP-complete problems.
I don't want to read the whole thing because it looks like it's very cynical - it judges TCS scientists who believe in Grover speedup as naive because they are unaware of real life noise, without actually realizing that's the point of TCS.
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.
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.
Does this finding affect Shor's Algorithm which I only learnt about last night from Veritasium ?
Shor's algorithm and Grovers algorithm are fundamentally very different. Most conventional asymmetric crypto algorithms are essentially all hidden sub group problems which are NP hard for classical computers. What Shor's algorithm does is reduce hidden sub group problems to P on quantum computers.
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.
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.
Shor's algorithm absolutely does not reduce NP hard problems to P (or BQP). These kinds of problems with quantum speedups reside in an intermediate class of difficulty sometimes called NP-intermediate which may or may not already be in P, and which NP complete problems do not reduce to.
You're correct, I got some of the terminology mixed up. It's after all been a long time since I've been in the field :p
This finding does not affect either Shor's Algorithm or Grover's algorithm, as far as I can tell.
I haven't read it in detail, but the abstract is so absurd that I won't bother.
I haven't read it in detail, but the abstract is so absurd that I won't bother.
Is this purely a preprint or has it passed a peer review?
For why you should basically ignore this paper because it is "both novel and correct, but not in the same places" see Scott's writeup https://scottaaronson.blog/?p=7143
I encourage people to read the article for themselves and reach their own conclusions.
This means that symmetric cryptography is safe from quantum computing.
Before, folks were saying we had to double the key length.
Before, folks were saying we had to double the key length.
People have been saying that 256 bits is enough because even with Grover's algorithm the largest possible impact is to halve the key size. 128-bit brute force is still prohibitive in reasonable time frames. AES-256 and Salsa/ChaCha should be fine even post-QC.
Symmetric crypto and hashes have never really been considered at risk except for very small sizes.
Symmetric crypto and hashes have never really been considered at risk except for very small sizes.
The actual meaningful quantum attacks on modern cryptography all target the asymmetric key exchange algorithms, and make them practically attachable (assuming the standard “big enough” and “with low enough noise” constraints).
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.
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.
There might be other algorithms that can take advantage of quantum computing to break symmetric cryptography (although the paper does argue we should expect it is unlikely these algorithms exist).
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.
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.
I'd still use AES256 or ChaCha20 (as part of a secure AEAD construction if at all possible) for any new crypto system designs, or a new profile of an existing system. See "Understanding brute force" by Daniel J. Bernstein. Get someone who knows what they are doing to look at the basic design before you start.
Double is probably way too much anyways. Grover's does not parallelize very well. So you would have to do each and every one of those 2^64 operations serially on your quantum computer to get the full benefit of Grover's when cracking a 128 bit key.
It is entirely possible that there is more than enough margin in 128 bit keys to prevent a successful Grover's based attack.
It is entirely possible that there is more than enough margin in 128 bit keys to prevent a successful Grover's based attack.
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...
[1] https://en.wikipedia.org/wiki/Threshold_theorem