The Computational Power of Quantum Mechanics
N. David Mermin, Cornell University
Over the past decade people have realized that a computer that fully exploits the possibilities allowed by the laws of quantum mechanics can accomplish tasks that are extraordinary from the perspective of conventional (classical) computation. I shall try to describe quantum computation to physicists unfamiliar with the recent application of quantum mechanics to computation, in a manner that is also accessible to computer scientists (or mathematicians) unfamiliar with quantum physics. People familiar with both topics may have to settle for the pleasure of understanding everything they hear, though they may be interested in my somewhat unorthodox presentation of quantum mechanics as a generalization of the classical theory of bits.