6 ms·

Grover's algorithm offers no quantum advantage

52 points by GavCo 4y ago

jnwatson 4y ago
This means that symmetric cryptography is safe from quantum computing. Before, folks were saying we had to double the key length.
- api 4y ago
  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.
- fwlr 4y ago
  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.
- olliej 4y ago
  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.
- Vecr 4y ago
  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.
- upofadown 4y ago
  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.
pyentropy 4y ago
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.
mparlane 4y ago
Does this finding affect Shor's Algorithm which I only learnt about last night from Veritasium ?
- sebzim4500 4y ago
  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.
- msm_ 4y ago
  As far as I understand, no. This is only about Grover's algorithm.
  - amluto 4y ago
    But it's also about another of Peter Shor's famous results: the Threshold theorem! But only in the sense that the authors seem to have never heard of it. (See my other comment.)
- Pepe1vo 4y ago
  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.
  - yarvos 4y ago
    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.
    - 4y ago
Atlas22 4y ago
Is this purely a preprint or has it passed a peer review?
OscarCunningham 4y ago
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.
- hackandthink 4y ago
  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.
  - OscarCunningham 4y ago
    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.
  - da-bacon 4y ago
    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.
amluto 4y ago
Sigh, this paper is extremely misguided. It gets two things egregiously wrong (not in the sense of a math error, although the math is barely worth reading), but in the sense of fundamentally misunderstanding what it's talking about. 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-003/html https://www.degruyter.com/document/doi/10.1515/9781400882618... [1] https://en.wikipedia.org/wiki/Threshold_theorem https://en.wikipedia.org/wiki/Threshold_theorem
da-bacon 4y ago
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 https://scottaaronson.blog/?p=7143
- miles7 4y ago
  I encourage people to read the article for themselves and reach their own conclusions.

52 points by GavCo 4y ago

This means that symmetric cryptography is safe from quantum computing. Before, folks were saying we had to double the key length.

api 4y ago
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.
fwlr 4y ago
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.
olliej 4y ago
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.
Vecr 4y ago
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.
upofadown 4y ago
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.

pyentropy 4y ago

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.

mparlane 4y ago

Does this finding affect Shor's Algorithm which I only learnt about last night from Veritasium ?

sebzim4500 4y ago
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.
msm_ 4y ago
As far as I understand, no. This is only about Grover's algorithm.
- amluto 4y ago
  But it's also about another of Peter Shor's famous results: the Threshold theorem! But only in the sense that the authors seem to have never heard of it. (See my other comment.)
Pepe1vo 4y ago
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.
- yarvos 4y ago
  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.
  - 4y ago

Atlas22 4y ago

Is this purely a preprint or has it passed a peer review?

OscarCunningham 4y ago

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.

hackandthink 4y ago
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.
- OscarCunningham 4y ago
  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.
- da-bacon 4y ago
  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.

amluto 4y ago

Sigh, this paper is extremely misguided. It gets two things egregiously wrong (not in the sense of a math error, although the math is barely worth reading), but in the sense of fundamentally misunderstanding what it's talking about. 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-003/html https://www.degruyter.com/document/doi/10.1515/9781400882618... [1] https://en.wikipedia.org/wiki/Threshold_theorem https://en.wikipedia.org/wiki/Threshold_theorem

da-bacon 4y ago

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 https://scottaaronson.blog/?p=7143

miles7 4y ago
I encourage people to read the article for themselves and reach their own conclusions.