NIST

quantum computation

(definition)

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 Black.

Entry modified 17 December 2007.
HTML page formatted Mon Nov 18 10:44:10 2013.

Cite this as:
Paul E. Black, "quantum computation", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/quantumComputation.html