Content deleted Content added
Citation bot (talk | contribs) Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 1635/2306 |
→Background: typo Tags: Mobile edit Mobile web edit |
||
Line 12:
One of the reasons quantum complexity theory is studied are the implications of quantum computing for the modern [[Church–Turing thesis|Church-Turing thesis]]. In short the modern Church-Turing thesis states that any computational model can be simulated in polynomial time with a [[probabilistic Turing machine]].<ref name=":02">{{Cite journal|last=Vazirani|first=Umesh V.|date=2002|title=A survey of quantum complexity theory|url=http://dx.doi.org/10.1090/psapm/058/1922899|journal=Proceedings of Symposia in Applied Mathematics|volume=58|pages=193–217|doi=10.1090/psapm/058/1922899|isbn=9780821820841|issn=2324-7088}}</ref><ref name=":32">{{Cite book|last=Nielsen, Michael A., 1974-|url=https://www.worldcat.org/oclc/665137861|title=Quantum computation and quantum information|date=2010|publisher=Cambridge University Press|others=Chuang, Isaac L., 1968-|isbn=978-1-107-00217-3|edition=10th anniversary|___location=Cambridge|oclc=665137861}}</ref> However, questions around the Church-Turing thesis arise in the context of quantum computing. It is unclear whether the Church-Turing thesis holds for the quantum computation model. There is much evidence that the thesis does not hold. It may not be possible for a probabilistic Turing machine to simulate quantum computation models in polynomial time.<ref name=":02" />
Both quantum computational complexity of functions and classical computational complexity of functions are often expressed with [[asymptotic notation]]. Some common forms of asymptotic notion of functions are <math>O(T(n))</math>, <math>\Omega(T(n))</math>, and <math>\Theta(T(n))</math>. <math>O(T(n))</math> expresses that something is bounded above by <math>cT(n)</math> where <math>c</math> is a constant such that <math>c>0</math> and <math>T(n)</math> is a function of <math>n</math>, <math>\Omega(T(n))</math> expresses that something is bounded below by <math>cT(n)</math> where <math>c</math> is a constant such that <math>c>0</math> and <math>T(n)</math> is a function of <math>n</math>, and <math>\Theta(T(n))</math> expresses both <math>O(T(n))</math> and <math>\Omega(T(n))</math>.<ref name=":12">{{Citation|last=Cleve|first=Richard|title=An Introduction to Quantum Complexity Theory|date=2000|url=http://dx.doi.org/10.1142/9789810248185_0004|work=Quantum Computation and Quantum Information Theory|pages=103–127|publisher=WORLD SCIENTIFIC|doi=10.1142/9789810248185_0004|arxiv=quant-ph/9906111|bibcode=2000qcqi.book..103C|isbn=978-981-02-4117-9|s2cid=958695|access-date=October 10, 2020}}</ref> These notations also have their own names. <math>O(T(n))</math> is called [[Big O notation]], <math>\Omega(T(n))</math> is called Big Omega notation, and <math>\Theta(T(n))</math> is called Big Theta notation.
== Overview of complexity classes ==
| |||