Quantum Computation Models

Quantum computation replaces classical bits with quantum states that can be superposed and entangled, defining models such as the quantum circuit and the complexity class BQP that appear to solve some problems faster than any classical method.

Definition

A quantum model of computation processes information stored in qubits whose states are unit vectors in a complex space; computation applies reversible quantum gates to create superposition and entanglement, and a final measurement yields a classical outcome with probabilities set by the quantum state.

Scope

This topic covers qubits and quantum gates, the quantum circuit model and its equivalence to the quantum Turing machine, the complexity class BQP of efficient quantum computation and its relation to classical classes, foundational algorithms such as Shor's factoring and Grover's search, and the role of measurement and decoherence in defining the model.

Core questions

• How do superposition and entanglement change what a computation can do?
• What is the relationship between the efficient quantum class BQP and classical classes?
• For which problems do quantum algorithms offer a provable or apparent speedup?
• How do measurement and the no-cloning principle constrain quantum computation?

Key theories

Quantum circuit model and BQP

Efficient quantum computation is captured by polynomial-size quantum circuits over a universal gate set, defining the class BQP, which contains P and is believed to extend it while still lying within PSPACE.

Quantum speedups

Shor's algorithm factors integers in polynomial time and Grover's algorithm searches an unstructured space with a quadratic speedup, demonstrating concrete advantages of the quantum model for specific tasks.

Clinical relevance

Quantum models guide the design of quantum hardware and algorithms; Shor's factoring algorithm threatens public-key cryptosystems whose security rests on the hardness of factoring, motivating the development of post-quantum cryptography, while quantum simulation promises advances in chemistry and materials science.

History

Feynman proposed using quantum systems to simulate physics in 1982, and Deutsch formalized the quantum Turing machine in 1985. Shor's 1994 factoring algorithm and Grover's 1996 search algorithm showed concrete speedups, turning quantum computation into a major branch of complexity theory and a driver of experimental effort.

Debates

How large is the quantum advantage, and is it physically realizable at scale?

Quantum computers compute the same functions as classical ones, so the question is efficiency. The precise relationship between BQP and classical classes is unresolved, and whether large fault-tolerant quantum computers can be built despite decoherence remains an open scientific and engineering question.

Key figures

• Richard Feynman
• David Deutsch
• Peter Shor
• Lov Grover

Seminal works

• nielsenChuang2010
• aroraBarak2009

Frequently asked questions

Do quantum computers compute things classical computers cannot?

No. Quantum computers solve exactly the same class of problems as classical computers; the difference is speed. For certain problems, such as factoring large numbers, the quantum model appears to be dramatically faster, but it does not extend the boundary of what is computable in principle.

Why does quantum computing matter for cryptography?

Shor's algorithm would let a large quantum computer factor large integers and compute discrete logarithms efficiently, breaking the public-key systems that secure much of today's communication. This prospect has driven the search for post-quantum schemes based on problems thought to be hard even for quantum machines.