Quantum complexity theory

Quantum complexity theory is a part of computational complexity theory in theoretical computer science. It studies complexity classes defined using quantum computers and quantum information which are computational models based on quantum mechanics. It studies the hardness of problems in relation to these complexity classes, and the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes.

A complexity class is a collection of problems which can be solved by some computational model under resource constraints. For instance, the complexity class P is defined to be the set of problems solvable by a Turing machine in polynomial time. Similarly, one may define a quantum complexity class using a quantum model of computation, such as a standard quantum computer or a quantum Turing machine. Thus, the complexity class BQP is defined to be the set of problems solvable by a quantum computer in polynomial time with bounded error.

Two important quantum complexity classes are BQP and QMA which are the bounded-error quantum analogues of P and NP. One of the main aims of quantum complexity theory is to find out where these classes lie with respect to classical complexity classes such as P, NP, PP, PSPACE and other complexity classes.

Quantum Query Complexity

In the query complexity model, the input is given as an oracle (black box). The algorithm gets information about the input only by querying the oracle. The algorithm starts in some fixed quantum state and the state evolves as it queries the oracle.

Quantum Query Complexity is the smallest number of queries to the oracle that are required in order to calculate the function. Clearly, Quantum Query Complexity is a lower bound on the overall time complexity of a function.

An example depicting the power of Quantum Computing is Grover's algorithm for searching unstructured databases. Its Quantum Query Complexity is O(N^1/2) which is quadratically better than the best known classical query complexity.

External links

• Complexity Zoo is a good place to read more about Quantum Complexity Theory.

References

• John Watrous (2008). "Quantum Computational Complexity". arXiv:0804.3401v1 [quant-ph]. 
• Artem Kaznatcheev. Quantum query complexity. 

Quantum information science
General	Quantum computer Qubit DiVincenzo's criteria Quantum information Quantum machine Quantum programming Timeline of quantum computing
Quantum communication	Quantum capacity Classical capacity Entanglement-assisted classical capacity Quantum channel Quantum network Quantum cryptography Quantum key distribution Quantum energy teleportation Quantum teleportation Superdense coding LOCC Entanglement distillation
Quantum algorithms	Universal quantum simulator Deutsch–Jozsa algorithm Grover's algorithm Quantum Fourier transform Shor's algorithm Simon's problem Quantum phase estimation algorithm Quantum annealing Algorithmic cooling
Quantum complexity theory	Quantum Turing machine EQP BQP QMA PostBQP
Quantum computing models	Quantum circuit Quantum gate One-way quantum computer cluster state Adiabatic quantum computation Topological quantum computer
Decoherence prevention	Quantum error correction Stabilizer codes Entanglement-Assisted Quantum Error Correction Quantum convolutional codes
Physical implementations	Quantum optics Cavity QED Circuit QED Linear optical quantum computing Ultracold atoms Trapped ion quantum computer Optical lattice Spin-based Nuclear magnetic resonance QC Kane QC Loss–DiVincenzo QC Nitrogen-vacancy center Superconducting quantum computing Charge qubit Flux qubit Phase qubit