Quantum complexity theory: Difference between revisions

Revision as of 08:04, 1 September 2021

Revision as of 20:32, 15 November 2021

Line 15:

== Overview of complexity classes ==

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_\text{yes},A_\text{no})</math>. <math>A_\text{yes}</math> is the set of yes instances, <math>A_\text{no}</math> is the set of no instances, and the intersection of these sets is such that <math>A_\text{yes} \cap A_\text{no} = \emptysetvarnothing</math>. All of the previous complexity classes contain promise problems.<ref name=":27">{{cite arxiv| last=Watrous|first=John| date=2008-04-21| title=Quantum Computational Complexity| class=quant-ph|eprint=0804.3401}}</ref>

{| class="wikitable"

|+

Line 22:

|-

|P

|Promise problems for which a polynomial time deterministic Turing machine accepts all strings in <math>A_\text{yes}</math> and rejects all strings in <math>A_\text{no}</math><ref name=":27"/>

|-

|BPP

|Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in <math>A_\text{yes}</math> with a probability of at least <math>\frac{2}{3}</math>, and accepts every string in <math>A_\text{no}</math> with a probability of at most <math>\frac{1}{3}</math><ref name=":27"/>

|-

|BQP

|Promise problems such that for functions <math>a,b:\mathbb {N}\rightarrowto [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_\text{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_\text{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=":27"/>

|-

|PP

|Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in <math>A_\text{yes}</math> with a probability greater than <math>\frac{1}{2}</math>, and accepts every string in <math>A_\text{no}</math> with a probability of at most <math>\frac{1}{2}</math><ref name=":27"/>

|-

|P-SPACE

|Promise problems for which a deterministic Turing machine, that runs in polynomial space, accepts every string in <math>A_\text{yes}</math> and rejects all strings in <math>A_\text{no}</math><ref name=":27"/>

|}