Quantum complexity theory: Difference between revisions

Revision as of 15:22, 5 April 2023

Revision as of 19:03, 10 May 2023

Line 15:

== Overview of complexity classes ==

SomeThe important complexity classes are P, BPP, BQP, PP, and P-Space. Tocan definebe thesecompared webased firston define a[[Promise problem|promise problemproblems]]. 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 such thatempty: <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"

|+