Quantum complexity theory: Difference between revisions

Revision as of 08:36, 7 December 2020

Revision as of 03:33, 16 December 2020

Line 1:

{{Short description|Computational complexity of quantum algorithms}}

{{Use American English|date=January 2019}}

{{more footnotes|date=March 2020}}

{{Short description|Computational complexity of quantum algorithms}}

'''Quantum complexity theory''' is the subfield of [[computational complexity theory]] that deals with [[complexity classes]] defined using [[quantum computers]], a [[computational model]] based on [[quantum mechanics]]. It studies the hardness of [[computational problem]]s in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes.

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_{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=":27">{{Citecite journalarxiv|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]|arxiv=0804.3401}}</ref>

{| class="wikitable"

|+

Line 83:

==== Adjacency matrix model ====

When considering quantum computation of the solution to directed directed graph problems, there are two important query models to understand. First, there is the adjacency matrix model, where the graph of the solution is given by the adjacency matrix: <math>M \in \{0,1\}a^{n\Chi n} </math>, with <math>M_{ij}=1 </math>, if and only if <math>(v_{i},v_{j})\in E </math>.<ref name=":0">{{Cite journal|last1=Durr|first1=Christoph|last2=Heiligman|first2=Mark|last3=Hoyer|first3=Peter|last4=Mhalla|first4=Mehdi|date=January 2006|title=Quantum query complexity of some graph problems|url=http://arxiv.org/abs/quant-ph/0401091|journal=SIAM Journal on Computing|volume=35|issue=6|pages=1310–1328|doi=10.1137/050644719|arxiv=quant-ph/0401091|s2cid=27736397|issn=0097-5397}}</ref>

==== Adjacency array model ====