Quantum mechanics via quantum computing
I've been reading Avi Wigdenson's new book Mathematics and Computation. It brings a lot of interesting ideas together in compact but readable form.
A couple days ago I quoted Widgerson's comment about problems in class P often having small exponents. Here I wanted to point out another interesting comment [1]. The chapter on quantum computing has this interesting tidbit.
How does a quantum algorithm work? It turns out that to understand that, one does not need to know any quantum mechanics. Indeed, quantum algorithms may be viewed as a language to explain many of the principles of quantum mechanics.
I don't know much about quantum mechanics, and I know even less about quantum computing. I've thought of looking into it just out of curiosity. I picked up Nielsen and Chuang's book on quantum computing at a used book store a while back. I still have the book, even though I've gotten rid of a lot of books this year, and may read it eventually.
I imagine it would help to know some quantum mechanics first before tackling quantum computing, but if your goal is quantum computing, maybe you should just start with quantum computing.
Wigderson suggests you could try the opposite of the conventional path, learning quantum computing in preparation for learning quantum mechanics. I imagine one would iterate between computing and mechanics rather than sequentially learning all you care to ever know about one then moving on to the other.
One thing I know about quantum computing is that it has the potential to make it radically faster to factor integers and to compute discrete logarithms. Most public key cryptography in common use is based on the computational difficulty of these two problems. I've been more interested in post-quantum cryptography-encryption algorithms not based on problems that a quantum computer would break-than in quantum computing per se.
You'll often hear that quantum computers and Shor's algorithm would break everything in cryptography. That's certainly not true. It would have a much bigger impact on asymmetric (public key) encryption than on symmetric encryption. That is, RSA and elliptic curve cryptography would be broken, but algorithms like AES would not.
There are public key encryption methods that are expected to be quantum-resistant. These algorithms may not be ready for prime time yet, but neither are quantum computers. It seems these new algorithms will be thoroughly studied and well-implemented by the time they're needed [2].
Related posts
[1] I don't want to give the impression that Mathematics of Computation is all about philosophical speculation. There is some philosophical speculation in the book, but there's also a lot of solid mathematics and computer science.
[2] If they're ever needed. It's not a foregone conclusion that large-scale quantum computers will become practical. See, for example, Gil Kalai's paper The Case Against Quantum Computers. Google's announcement last month created a wave of optimism regarding quantum computing, but we'll see whether the wave collapses.