But of course, if our ideas about physics are even approximately correct, then Moore's Law can't be a law. If it doesn't break down when transistors reach the subatomic scale, certainly it has to when they reach the Planck scale.
Dave, your comment causes me to ask myself two things: first, is it possible to be a "graybeard" at 26? And secondly, if I say it's likely that quantum computers can't solve NP-complete problems in polynomial time, why do so many people think I'm saying quantum computers "won't amount to much"? It's as if popular opinion in the 19th century held that airplanes, once built, would be able to fly to Mars, and someone pointed out that no, they probably couldn't, and that person were laughed off as a "graybeard" who just couldn't see airplanes' great potential. Are you able to separate one claim from another claim?
Yes, Grover's algorithm is important. As my article discusses, if all you're doing is brute-force search, then Grover's algorithm effectively doubles the size of the instances that you can solve with a given number of steps.
But there's a further wrinkle: in practice, people trying to solve difficult optimization problems on a classical computer usually use some sort of local search heuristic, which is much, much faster than brute-force. And while we do have a quantum analogue of local search (called the "quantum adiabatic algorithm"), it's not at all clear how much of a speedup it will give over classical local search on practical instances. Even the square-root speedup of Grover's algorithm might not be achievable in general (on the other hand, it's also conceivable that the speedup could be more than quadratic). If you're interested in this issue, see the original papers on the adiabatic algorithm by Farhi, Goldstone, Gutmann et al., as well as papers by van Dan, Mosca, and Vazirani and by Reichardt about the limitations of the adiabatic algorithm.
Shor's paper -- the one that showed how quantum computers can factor efficiently -- also showed how they can solve the discrete log problem efficiently (and thereby break Diffie-Hellman among other cryptosystems). Shortly afterward, Boneh and Lipton gave a simple extension to break elliptic curve cryptography (the key fact that makes this possible is that elliptic curve groups are abelian).
Basically, the one class of public-key cryptosystems that's *not* known to be breakable with quantum computers, is the class for which the encryption function consists of applying a linear transformation and then adding random noise. This class includes, e.g., the McEliece and Ajtai-Dwork cryptosystems, as well as more recent lattice-based cryptosystems due to Regev and Peikert-Waters. Breaking this class of cryptosystems with a quantum computer reduces to solving the "hidden subgroup problem over the dihedral group," which (in contrast to the HSP over abelian groups) we don't yet know how to do.
I should mention that, if you're content with private-key cryptography, then we have *plenty* of examples not known to be efficiently breakable with a quantum computer (even DES, suitably generalized to n-bit keys, would probably suffice).
I do mention them in the article! Here's the quote: "If quantum computers ever become a reality, the 'killer app' for them will most likely not be code breaking but rather something so obvious it is rarely even mentioned: simulating quantum physics. This is a fundamental problem for chemistry, nanotechnology, and other fields, important enough that Nobel Prizes have been awarded even for partial progress."
Author here. I thought those who accuse me of drawing a false dichotomy -- between quantum computers as "godlike" on the one hand or a hoax on the other -- might be interested in the following quotes from the actual published article.
"although we should not accept the usual hype, in my view it is equally misguided to dismiss quantum computing as science fiction. Instead we should find out what the limits of quantum computers are and what we could really do if we had them." (p. 63)
"According to our current understanding, [quantum computers] would provide dramatic speedups for a few problems -- such as breaking the cryptographic codes that are widely used for monetary transactions on the Internet. For other problems, however -- such as playing chess, scheduling airline flights and proving theorems -- evidence now strongly suggests that quantum computers would suffer from many of the same algorithmic limitations as today's classical computers." (p. 63)
"If a large, ideal quantum computer would face most of the same limitations as our present-day classical computers do, should the physicists working on the extraordinarily hard task of building even rudimentary quantum computers pack up and go home? I believe the answer is no, for four reasons..." (p. 65)
"To some, the apparent limitations of quantum computers might come as a letdown. One can, however, give those same limitations a more optimistic spin. They mean that although certain cryptographic codes could be broken in a world with quantum computers, other codes would probably remain secure..." (p. 69)
In short, the precise misconception that I wrote my article to try to combat, is the one I then get accused of! Reading an article can, indeed, provide useful clues about its contents.
Slashdot Mirror
But of course, if our ideas about physics are even approximately correct, then Moore's Law can't be a law. If it doesn't break down when transistors reach the subatomic scale, certainly it has to when they reach the Planck scale.
Dave, your comment causes me to ask myself two things: first, is it possible to be a "graybeard" at 26? And secondly, if I say it's likely that quantum computers can't solve NP-complete problems in polynomial time, why do so many people think I'm saying quantum computers "won't amount to much"? It's as if popular opinion in the 19th century held that airplanes, once built, would be able to fly to Mars, and someone pointed out that no, they probably couldn't, and that person were laughed off as a "graybeard" who just couldn't see airplanes' great potential. Are you able to separate one claim from another claim?
Yes, Grover's algorithm is important. As my article discusses, if all you're doing is brute-force search, then Grover's algorithm effectively doubles the size of the instances that you can solve with a given number of steps. But there's a further wrinkle: in practice, people trying to solve difficult optimization problems on a classical computer usually use some sort of local search heuristic, which is much, much faster than brute-force. And while we do have a quantum analogue of local search (called the "quantum adiabatic algorithm"), it's not at all clear how much of a speedup it will give over classical local search on practical instances. Even the square-root speedup of Grover's algorithm might not be achievable in general (on the other hand, it's also conceivable that the speedup could be more than quadratic). If you're interested in this issue, see the original papers on the adiabatic algorithm by Farhi, Goldstone, Gutmann et al., as well as papers by van Dan, Mosca, and Vazirani and by Reichardt about the limitations of the adiabatic algorithm.
Shor's paper -- the one that showed how quantum computers can factor efficiently -- also showed how they can solve the discrete log problem efficiently (and thereby break Diffie-Hellman among other cryptosystems). Shortly afterward, Boneh and Lipton gave a simple extension to break elliptic curve cryptography (the key fact that makes this possible is that elliptic curve groups are abelian). Basically, the one class of public-key cryptosystems that's *not* known to be breakable with quantum computers, is the class for which the encryption function consists of applying a linear transformation and then adding random noise. This class includes, e.g., the McEliece and Ajtai-Dwork cryptosystems, as well as more recent lattice-based cryptosystems due to Regev and Peikert-Waters. Breaking this class of cryptosystems with a quantum computer reduces to solving the "hidden subgroup problem over the dihedral group," which (in contrast to the HSP over abelian groups) we don't yet know how to do. I should mention that, if you're content with private-key cryptography, then we have *plenty* of examples not known to be efficiently breakable with a quantum computer (even DES, suitably generalized to n-bit keys, would probably suffice).
I do mention them in the article! Here's the quote: "If quantum computers ever become a reality, the 'killer app' for them will most likely not be code breaking but rather something so obvious it is rarely even mentioned: simulating quantum physics. This is a fundamental problem for chemistry, nanotechnology, and other fields, important enough that Nobel Prizes have been awarded even for partial progress."
Author here. I thought those who accuse me of drawing a false dichotomy -- between quantum computers as "godlike" on the one hand or a hoax on the other -- might be interested in the following quotes from the actual published article. "although we should not accept the usual hype, in my view it is equally misguided to dismiss quantum computing as science fiction. Instead we should find out what the limits of quantum computers are and what we could really do if we had them." (p. 63) "According to our current understanding, [quantum computers] would provide dramatic speedups for a few problems -- such as breaking the cryptographic codes that are widely used for monetary transactions on the Internet. For other problems, however -- such as playing chess, scheduling airline flights and proving theorems -- evidence now strongly suggests that quantum computers would suffer from many of the same algorithmic limitations as today's classical computers." (p. 63) "If a large, ideal quantum computer would face most of the same limitations as our present-day classical computers do, should the physicists working on the extraordinarily hard task of building even rudimentary quantum computers pack up and go home? I believe the answer is no, for four reasons..." (p. 65) "To some, the apparent limitations of quantum computers might come as a letdown. One can, however, give those same limitations a more optimistic spin. They mean that although certain cryptographic codes could be broken in a world with quantum computers, other codes would probably remain secure..." (p. 69) In short, the precise misconception that I wrote my article to try to combat, is the one I then get accused of! Reading an article can, indeed, provide useful clues about its contents.