Quantum complexity theory: Difference between revisions

Revision as of 15:12, 12 July 2023

Revision as of 00:39, 22 July 2023

Line 15:

== Overview of complexity classes ==

The important complexity classes P, BPP, BQP, PP, and P-SpacePSPACE can be compared based on [[Promise problem|promise problems]]. 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>, where <math>A_\text{yes}</math> is the set of yes instances and <math>A_\text{no}</math> is the set of no instances, and the intersection of these sets is empty: <math>A_\text{yes} \cap A_\text{no} = \varnothing</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 33:

|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"/>

|-

|PSPACE

|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"/>

|}