Quantum complexity theory: Difference between revisions

Revision as of 04:17, 23 November 2020

Revision as of 06:07, 23 November 2020

Line 9:

{{See also|Computational complexity|Complexity class}}

A [[complexity class]] is a collection of [[computational problem]]s that can be solved by a computational model under certain resource constraints. For instance, the complexity class [[P (complexity)|P]] is defined as the set of problems solvable by a [[Turing machine]] in [[polynomial time]]. Similarly, quantum complexity classes may be defined using quantum models of computation, such as the [[quantum computer|quantum circuit model]] or the equivalent [[quantum Turing machine]]. One of the main aims of quantum complexity theory is to find out how these classes relate to classical complexity classes such as [[P (complexity)|P]], [[NP (complexity)|NP]], [[BPP (complexity)|BPP]], and [[PSPACE]].

One of the reasons quantum complexity theory is studied are the implications of quantum computing for the modern [[Church–Turing thesis|Church-Turing thesis]]. In short the modern Church-Turing thesis states that any computational model can be simulated in polynomial time with a [[probabilistic Turing machine]].<ref name=":02">{{Cite journal|last=Vazirani|first=Umesh V.|date=2002|title=A survey of quantum complexity theory|url=http://dx.doi.org/10.1090/psapm/058/1922899|journal=Proceedings of Symposia in Applied Mathematics|pages=193–217|doi=10.1090/psapm/058/1922899|issn=2324-7088}}</ref><ref name=":3">{{Cite book|last=Nielsen, Michael A., 1974-|url=https://www.worldcat.org/oclc/665137861|title=Quantum computation and quantum information|date=2010|publisher=Cambridge University Press|others=Chuang, Isaac L., 1968-|isbn=978-1-107-00217-3|edition=10th anniversary ed|___location=Cambridge|oclc=665137861}}</ref> However, questions around the Church-Turing thesis arise in the context of quantum computing. It is unclear whether the Church-Turing thesis holds for the quantum computation model. There is much evidence that the thesis does not hold. It may not be possible for a probabilistic Turing machine to simulate quantum computation models in polynomial time.<ref name=":02" />

Both quantum computational complexity of functions and classical computational complexity of functions are often expressed with [[asymptotic notation]]. Some common forms of asymptotic notion of functions are <math>O(T(n))</math>, <math>\Omega(T(n))</math>, and <math>\Theta(T(n))</math>. <math>O(T(n))</math> expresses that something is bounded above by <math>cT(n)</math> where <math>c</math> is a constant such that <math>c>0</math> and <math>T(n)</math> is a function of <math>n</math>, <math>\Omega(T(n))</math> expresses that something is bounded below by <math>cT(n)</math> where <math>c</math> is a constant such that <math>c>0</math> and <math>T(n)</math> is a function of <math>n</math>, and <math>\Theta(T(n))</math> expresses both <math>O(T(n))</math> and <math>\Omega(T(n))</math>.<ref name=":1">{{Citation|last=Cleve|first=Richard|title=An Introduction to Quantum Complexity Theory|date=2000|url=http://dx.doi.org/10.1142/9789810248185_0004|work=Quantum Computation and Quantum Information Theory|volume=|pages=103–127|publisher=WORLD SCIENTIFIC|isbn=978-981-02-4117-9|access-date=October 10, 2020}}</ref> These notations also their own names. <math>O(T(n))</math> is called [[Big O notation]], <math>\Omega(T(n))</math> is called Big Omega notation, and <math>\Theta(T(n))</math> is called Big Theta notation.

==BQP==