Quantum complexity theory
Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers and quantum information, which are computational models based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes.
Overview
A complexity class is a collection of problems that 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. The quantum complexity class BQP is defined in this way as the set of all problems solvable by a quantum computer in polynomial time with bounded error.
One of the main aims of quantum complexity theory is to find out how these classes relate to classical complexity classes such as P, NP, PP, PSPACE and other complexity classes. For instance, the two important quantum complexity classes BQP and QMA are the bounded-error quantum analogues of P and NP.
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. This makes the quantum query complexity 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. The algorithm's quantum query complexity is , a quadratic improvement over the best possible classical query complexity, which is a linear search.
See also
References
- Nielsen, Michael; Chuang, Isaac (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 978-0-521-63503-5. OCLC 174527496.
- Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 201–236. ISBN 978-0-521-42426-4.
- John Watrous (2008). "Quantum Computational Complexity". arXiv:0804.3401v1 [quant-ph].
- Watrous J. (2009) Quantum Computational Complexity. In: Meyers R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY
External links
| General |  | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems | |||||||||
| Quantum communication | |||||||||
| Quantum algorithms | |||||||||
| Quantum complexity theory | |||||||||
| Quantum computing models | |||||||||
| Quantum error correction | |||||||||
| Physical implementations |
| ||||||||
| Software | |||||||||
