(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

**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 Feb 2 13:10:40 2015.

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