quantum computation


Definition: Computation based on quantum mechanical effects, such as superposition and entanglement, in addition to classical digital manipulations.

Specialization (... is a kind of me.)
Shor's algorithm, Grover's algorithm, Simon's algorithm, Deutsch-Jozsa algorithm.

See also model of computation.

Note: Quantum computers can, in theory, make computations that are impossible to do exactly with classical computers or achieve exponential speedup. Since nobody has yet (as of February 2005) implemented more than a few bit operations, problems such as decoherence and measurement error may limit quantum computation to a few specialized roles.

Author: PEB

More information

Ethan Bernstein and Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, 26(5):1411-1473, 1997.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 17 December 2007.
HTML page formatted Fri Mar 25 16:20:34 2011.

Cite this as:
Paul E. Black, "quantum computation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2007. (accessed TODAY) Available from:

to NIST home page