Processed: 2017-02-27T02:16:27.133258
| Citations checked | 2 |
| * Citations changed | 1 |
| + Citations with a new free link | 1 |
| + No new free link, but new access icon | 0 |
| * Citations left unchanged | 1 |
| + Green lock already present | 1 |
| + No room for a new |url= | 0 |
| + Citation uses |registration= or |subscription= | 0 |
| + No free version found | 0 |
{{Cite journal | last1=Fortnow | first1=Lance | last2=Rogers | first2=John | title=Complexity limitations on Quantum computation | url=http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf | publisher=[[Academic Press]] | location=Boston, MA | year=1999 | journal=J. Comput. Syst. Sci. | issn=0022-0000 | volume=59 | issue=2 | pages=240–252 | doi=10.1006/jcss.1999.1651 | postscript=}}
{{cite journal|last=Aaronson|first=Scott|year=2005|title=Quantum computing, postselection, and probabilistic polynomial-time|journal=Proceedings of the Royal Society A|volume=461|issue=2063|pages=3473–3482|doi=10.1098/rspa.2005.1546}}
| 33 | In fact, {{sans-serif|BQP}} is [[low (complexity)|low]] for {{sans-serif|PP}}, meaning that a {{sans-serif|PP}} machine achieves no benefit from being able to solve {{sans-serif|BQP}} problems instantly, an indication of the possible difference in power between these similar classes. | 33 | In fact, {{sans-serif|BQP}} is [[low (complexity)|low]] for {{sans-serif|PP}}, meaning that a {{sans-serif|PP}} machine achieves no benefit from being able to solve {{sans-serif|BQP}} problems instantly, an indication of the possible difference in power between these similar classes. | ||
| 34 | :<math>\mathsf{P \subseteq BPP \subseteq BQP\subseteq AWPP \subseteq PP \subseteq PSPACE}</math> | 34 | :<math>\mathsf{P \subseteq BPP \subseteq BQP\subseteq AWPP \subseteq PP \subseteq PSPACE}</math> | ||
| 35 | 35 | ||||
| 36 | As the problem of {{sans-serif|P ≟ PSPACE}} has not yet been solved, the proof of inequality between {{sans-serif|BQP}} and classes mentioned above is supposed to be difficult.<ref name=BernVazi/> The relation between {{sans-serif|BQP}} and {{sans-serif|[[NP (complexity)|NP]]}} is not known. | 36 | As the problem of {{sans-serif|P ≟ PSPACE}} has not yet been solved, the proof of inequality between {{sans-serif|BQP}} and classes mentioned above is supposed to be difficult.<ref name=BernVazi/> The relation between {{sans-serif|BQP}} and {{sans-serif|[[NP (complexity)|NP]]}} is not known. | ||
| 37 | 37 | ||||
| t | 38 | Adding [[postselection]] to {{sans-serif|BQP}} results in the complexity class {{sans-serif|[[PostBQP]]}} which is equal to {{sans-serif|[[PP (complexity)|PP]]}}.<ref name="PostBQP=PP">{{cite journal|last=Aaronson|first=Scott|year=2005|title=Quantum computing, postselection, and probabilistic polynomial-time|journal=Proceedings of the Royal Society A|volume=461|issue=2063|pages=3473–3482|doi=10.1098/rspa.2005.1546}}. Preprint available at [http://arxiv.org/abs/quant-ph/0412187]</ref><ref>{{cite web|url=http://weblog.fortnow.com/2004/01/complexity-class-of-week-pp-by-guest.html|title=Complexity Class of the Week: PP|last=Aaronson|first=Scott|date=2004-01-11|work=Computational Complexity Weblog|accessdate=2008-05-02}}</ref> | t | 38 | Adding [[postselection]] to {{sans-serif|BQP}} results in the complexity class {{sans-serif|[[PostBQP]]}} which is equal to {{sans-serif|[[PP (complexity)|PP]]}}.<ref name="PostBQP=PP">{{cite journal|last=Aaronson|first=Scott|year=2005|title=Quantum computing, postselection, and probabilistic polynomial-time|journal=Proceedings of the Royal Society A|volume=461|issue=2063|pages=3473–3482|doi=10.1098/rspa.2005.1546|arxiv=quant-ph/0412187}}. Preprint available at [http://arxiv.org/abs/quant-ph/0412187]</ref><ref>{{cite web|url=http://weblog.fortnow.com/2004/01/complexity-class-of-week-pp-by-guest.html|title=Complexity Class of the Week: PP|last=Aaronson|first=Scott|date=2004-01-11|work=Computational Complexity Weblog|accessdate=2008-05-02}}</ref> |
| 39 | 39 | ||||
| 40 | == External links == | 40 | == External links == | ||
| 41 | * [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp Complexity Zoo link to BQP] | 41 | * [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp Complexity Zoo link to BQP] | ||
| 42 | 42 | ||||
| 43 | ==References== | 43 | ==References== |