The construction of computer algorithms and software models that simulate
physical systems plays a fundamental role in all branches of science and engineering.
The physicist and Nobel laureate Richard Feynman, among others,
observed in the 1980s that the important task of simulating quantummechanical
processes on a standard computer requires an extraordinary
amount of computer memory and runtime [41]. Such observations gave rise to
the notion of quantum computing, where quantum mechanics itself is used to
simulate quantum behavior. The key insight is to replace the familiar 0 and
1 bits of conventional or classical computing with information units called
qubits (quantum bits) that capture quantum states of elementary particles or
atomic nuclei. By operating on qubits, a quantum computer can, in principle,
process exponentially more data than a classical computer in a similar number
of steps. In the 1990s, several fast quantum methods were discovered for such
applications as searching large databases [38] and factoring large numbers [82];
the latter is a basic step in some forms of codebreaking.