User:ColeDU/Quantum complexity theory: Difference between revisions

Revision as of 19:37, 21 November 2020

Revision as of 20:37, 21 November 2020

Line 17:

== Complexity Classes Overview ==

Some important complexity classes are P, NP, 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" />

{| 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=":2" />

|-

|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=":2" />

|-

|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. Strings in <math>A_{yes}</math> are accepted by <math>Q</math> with a probability greater than or equal to <math>a</math> where the input for <math>a</math> is the absolute value of the particular string in question. Strings in <math>A_{no}</math> are rejected by <math>Q</math> with a probability less than or equal to <math>b</math> where the input for <math>b</math> is the absolute value of the particular string in question. <ref name=":2" />

|-

|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=":2" />

|-

|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=":2" />

|}

== Quantum Circuits ==