So ... more proof that D-Wave is fluff.
They could run the classical algorithms a factor of 1,000,000× slower and reach the same conclusion, that the D-Wave's quantum annealing process is asymptotically equivalent (scales equivalently) to classical algorithms.
edit: I was trying to be polite, but Scott Aaronson has spilled quite a lot of blog ink denouncing remarks like the parent post as utter nonsense.
Classical computers are limited by what they can compute because the universe has limits. A 10,000 qubit quantum computer can factor fairly large numbers. 10,000 qubits is pretty small, one day hopefully it will fit inside a small room.
To factor those same numbers using a classical computer you'd have to make a computer the size of the entire known universe and run that computer until the heat death of the universe. Obviously this is not possible, even in principal.
Theoretically any QC computation can be simulated by a classical computer but in our limited universe you quickly run into the wall where the classical computer just becomes too big (bigger than the entire universe) and too slow (slower than the life of the universe).
Aside from factoring, what kinds of things do we think will meaningfully change if we get general QC? Cryptographers are already preparing for the post-quantum world. Who else needs to be preparing?
Everything I think I understand about QC suggests that a practical breakthrough will not cause any changes in society, other than the abandonment of RSA. Am I missing something?
I could see this causing massive changes in society. An artificial intelligent simulation of a super-smart human, that can be tuned toward a specific problem area and made much more focused and efficient than a purely biological brain could work...
Is the argument that I've heard.
I don't know how that works when the qubits are being used to deal with other sorts of variables than bits though?
And that changes everything, probably more than anything since (the iPhone|the internet|computers|penicillin|the industrial revolution|fire) depending on how optimistic you are. It'll change things a lot, anyway.
Before this thread, I knew that Shor's algorithm and Grover's algorithm were two very important QC results. I knew that Shor's algorithm means that a QC would be able to decrypt anything that was ever encrypted with RSA. (ECC schemes are likely just as vulnerable, so cryptographers are looking at purely hash-based schemes: http://pqcrypto.org/hash.html)
What I learned this morning based on hints in this thread:
1) Grover's algorithm is a far more modest speedup compared to Shor's algorithm
2) Shor's algorithm only factors integers, but Grover's algorithm can more generally invert a function (which still threatens many currently used cryptographic functions)
So I'd guess that Grover's algorithm is the sort of thing people are talking about as useful in machine learning. There are probably other QC results that are worth getting excited about for people working with neural networks. The Google/Microsoft workshop this weekend has a number of sessions on quantum annealing, as well.
A big reason "unsolvable by classical computers" is such a silly way to phrase things is (paraphrasing Dr. Aaronson here) that simulated annealing techniques on classical computers are already producing such good results without QC. In the previous Shtetl-Optimized post to this one, he posts a Powerpoint deck for a talk he gave at the same conference, and it is quite instructive (but still enough over my head that I'm sitting on HN asking dumb questions).
I mean, since the best-known quantum algorithm for factoring integers is asymptotically faster than the best-known classical algorithm for factoring integers, isn't there some definition of "large" for which this is no longer true?
(I'm assuming you mean "classical computers can factor large integers effectively", since the class of all problems solvable by a classical computer is exactly the same as the class of all problems solvable by a quantum computer)
I started this sub-thread because I'm pretty sure this statement is true. But the details are tricky.
> the best-known quantum algorithm for factoring integers is asymptotically faster than the best-known classical algorithm for factoring integers
The only reason that current commercial cryptography works is that classical computers can't factor large integers effectively. But quantum speedups to factoring isn't particularly profound, since factoring is just a small part of computing.
> I started this sub-thread because I'm pretty sure this statement is true. But the details are tricky.
Actually that is one of the first problems that was solved when we started looking into quantum computers. Our models of classical and quantum computation are both Turing complete and only Turing complete. Any classical computer can simulate a quantum computer, and any quantum computer can simulate a classical one. A quantum computer's only advantage is in speed, and we don't yet have proof that there is an exponential speed benefit that cannot be circumvented by finding a better classical algorithm.
Since asymmetric cryptography generally relies on an exponential barrier between the process of using the encryption and the process of breaking the encryption, that is what we really need to completely break modern asymmetric cryptography.
https://en.wikipedia.org/wiki/Grover%27s_algorithm
For some reason, his comment was killed.
The space between unsolvable by classical computers and solvable practically by classical computers is... significant.
Your first statement is correct, but Shor's algorithm (the one I suspect you are referring to when you talk about a universe sized computer) is not an example of one. We do not know that there is not a classical factoring algorithm that is as good or better than Shor's, and we have no quantum algorithms as of yet that can give an exponential speedup over any possible (but possible yet unknown) classical algorithm (which is needed for the universe sized computer thing). We have some that give more modest speed ups that are known to be unbeatable by classical algorithms; Grover's search algorithm is such an example, but it is only quadratic. This means you have a quantum computer of size N, you only need a classical computer of size N^2 to match it.
> Optimisation quickly becomes irrelevant when you scale these problems just a little bit more.
The problem with quantum computers isn't optimization of algorithms, but it's still optimization of strategies for dealing with errors (which sometimes look a lot like algorithms). Building reasonably accurate logic gates was figured out with a lot less effort when we started even thinking of building such things, and their reliability didn't fall off with increasing size very quickly. Our technology for quantum computers, on the other hand, all have crippling flaws as of yet. The most common one (superconducting qubits and ion trap based designs both suffer from this) is that when we try to make the computer bigger, it needs an unscalable amount of error correction an eventually stops working altogether. Some other approaches (linear optical quantum computer for example) can scale up without getting worse per se, but the gates we can build are already so unreliable that we still need too much error correction to scale. So optimizing our error correction strategies is one possible avenue that is being explored.