Exhaustive Searching Is Less Tiring with a Bit of Quantum Magic
OCT 01, 1997
Quantum computers have been shown to provide a dramatic speedup over classical computers in solving problems by exhaustive searching. For example, the widely used 56‐bit Data Encryption Standard could be cracked with a mere 200 million or so computations instead of about 35 quadrillion.
DOI: 10.1063/1.881969
The elementary particle of information used by modern digital computers is the bit—a register or memory element that can be in one of two distinct states, 0 or 1. But we live in a quantum world, and one can design computers in which each elementary unit of information is a quantum bit, or qubit, which can be in any superposition of two quantum states, |0〉 and |1〉. A quantum computer built with n such components could itself be in a superposition of
This article is only available in PDF format
© 1997 American Institute of Physics
