Suggestions for Further Reading

There was a time when the newspapers said that only twelve men understood the theory of relativity. I do not believe there ever was such a time . . . On the other hand, I think I can safely say that nobody understands quantum mechanics.

—Richard Feynman, The Character of Physical Law, BBC, 1965

Quantum mechanics came into existence, when Werner Heisenberg, at the age of 25, proposed the uncertainty principle in 1927. It created an immediate stir in the physics community. Eventually Heisenberg and Niels Bohr came up with an interpretation of quantum mechanics, known as the Copenhagen interpretation. While many physicists (like Max Born, Wolfgang Pauli and John von Neumann) subscribed to this interpretation, many other eminent ones (including Albert Einstein, Erwin Schrödinger, Max Planck and Bertrand Russell) did not. Interested readers may consult textbooks by Sakurai [255] and Schiff [258] to study this fascinating area of fundamental science.^[3]

^[3] Well! We are not physicists. These books are followed in graduate and advanced undergraduate courses in many institutes and universities.

For a comprehensive treatment of quantum computation (including cryptographic and cryptanalytic quantum algorithms), we refer the reader to the book by Nielsen and Chuang [218]. Mermin’s paper [197] and course notes [198] are also good sources for learning quantum mechanics and computation, and are suitable for computer scientists. Preskill’s course notes [244] are also useful, though a bit more physics-oriented. The very readable article [243] by Preskill on the realizability of quantum computers is also worth mentioning in this context. The first known quantum algorithm is due to Deutsch [75].

Bennett and Brassard’s quantum key-exchange algorithm (BB84) appeared in [20]. The implementation due to Stucki et al. of this algorithm is reported in [293].

Shor’s polynomial-time quantum factorization and discrete-log algorithms are described in [271]. All the details missing in Section 8.4.4 can be found in this paper. No polynomial-time quantum algorithms are known to solve the elliptic curve discrete logarithm problem. Proos and Zalka [245] present an extension of Shor’s algorithm for a special class of elliptic curves. See [146] for an adaptation of this algorithm applicable to fields of characteristic 2.