Quantum complexity theory: Difference between revisions

Revision as of 06:07, 23 November 2020

Revision as of 06:16, 23 November 2020

Line 13:

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.

== Complexity Classes Overview ==

Some important complexity classes are P, BPP, BQP, PP, and P-Space. To define these we first define a promise problem. A promise problem is a decision problem which has an input assumed to be selected from the set of all possible input strings. A promise problem is a pair <math>A=(A_{yes},A_{no})</math>. <math>A_{yes}</math> is the set of yes instances, <math>A_{no}</math> is the set of no instances, and the intersection of these sets is such that <math>A_{yes}\cap A_{no}=\emptyset</math>. All of the previous complexity classes contain promise problems.<ref name=":2">{{Cite journal|last=Watrous|first=John|date=2008-04-21|title=Quantum Computational Complexity|url=http://arxiv.org/abs/0804.3401|journal=arXiv:0804.3401 [quant-ph]}}</ref>

{| class="wikitable"

|+

!Complexity Class

!Criteria

|-

|P

|Promise problems for which a polynomial time deterministic Turing machine accepts all strings in <math>A_{yes}</math> and rejects all strings in <math>A_{no}</math><ref name=":22">{{Cite journal|last=Watrous|first=John|date=2008-04-21|title=Quantum Computational Complexity|url=http://arxiv.org/abs/0804.3401|journal=arXiv:0804.3401 [quant-ph]}}</ref>

|-

|BPP

|Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in <math>A_{yes}</math> with a probability of at least <math>\frac{2}{3}</math>, and accepts every string in <math>A_{no}</math> with a probability of at most <math>\frac{1}{3}</math><ref name=":23">{{Cite journal|last=Watrous|first=John|date=2008-04-21|title=Quantum Computational Complexity|url=http://arxiv.org/abs/0804.3401|journal=arXiv:0804.3401 [quant-ph]}}</ref>

|-

|BQP

|Promise problems such that for functions <math>a,b:\mathbb {N}\rightarrow[0,1]</math>, there exists a polynomial time generated family of quantum circuits <math>Q={\{Q_n:n\in \mathbb{N}\}}</math>, where <math>Q_n</math> is a circuit which accepts <math>n</math> qubits and gives an output of one qubit. An element <math>x</math> of <math>A_{yes}</math> is accepted by <math>Q</math> with a probability greater than or equal to <math>a(\left \vert x \right \vert) </math>. An element <math>x</math> of <math>A_{no}</math> is accepted by <math>Q</math> with a probability less than or equal to <math>b(\left \vert x\right \vert)</math>. <ref name=":24">{{Cite journal|last=Watrous|first=John|date=2008-04-21|title=Quantum Computational Complexity|url=http://arxiv.org/abs/0804.3401|journal=arXiv:0804.3401 [quant-ph]}}</ref>

|-

|PP

|Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in <math>A_{yes}</math> with a probability greater than <math>\frac{1}{2}</math>, and accepts every string in <math>A_{no}</math> with a probability of at most <math>\frac{1}{2}</math><ref name=":25">{{Cite journal|last=Watrous|first=John|date=2008-04-21|title=Quantum Computational Complexity|url=http://arxiv.org/abs/0804.3401|journal=arXiv:0804.3401 [quant-ph]}}</ref>

|-

|P-SPACE

|Promise problems for which a deterministic Turing machine, that runs in polynomial space, accepts every string in <math>A_{yes}</math> and rejects all strings in <math>A_{no}</math><ref name=":26">{{Cite journal|last=Watrous|first=John|date=2008-04-21|title=Quantum Computational Complexity|url=http://arxiv.org/abs/0804.3401|journal=arXiv:0804.3401 [quant-ph]}}</ref>

|}

==BQP==