Since you seem to already familiar with integer factoring, isn't factoring large integers something that "solvable by QC, and unsolvable by classical computers"?
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)
> 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.
> > 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.
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.
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).