The quest for practical quantum computers is one of the great engineering challenges of our time. It is motivated by theory and experiments — some being currently debated — showing that quantum computation and communication can achieve results that are inaccessible to conventional computers and communication channels. At the heart is Peter Shor's algorithm for factoring d-digit numbers in roughly d^3 quantum operations, as opposed to exponential in the cube root of d for today's computers. Certainly our current mathematical notation for these operations is exponential in size. Insofar as computation is symbolic, this suggests Nature has "linguistics" that our classical computer programming and thought patterns cannot emulate. Either:
- Nature computes in ways that are ineffable to our notation; or
- Our classical modes can catch up to Nature — in which case we already have the power to factor numbers and hence break "RSA" and related cryptosystems on which the bulk of Internet commerce relies for security.
(Part of the last work is joint with Dr. Amlan Chakrabarti, University of Calcutta. It was covered in a post "Grilling Quantum Circuits" on the "Gödel's Lost Letter and P=NP" blog, and was incorporated into Chapter 16 of my text with Richard Lipton, Quantum Algorithms Via Linear Algebra.)
Kenneth Regan is Associate Professor at the University at Buffalo.