Content deleted Content added
Addressed comments for the third paragraph |
m changed phrasing to takes advantage of in subsection Deutsch-Jozsa Algorithm |
||
| (8 intermediate revisions by the same user not shown) | |||
Line 4:
A [[complexity class]] is a collection of [[Computational problem|computational problems]] that can be solved by a computational model under certain resource constraints. For instance, the complexity class [[P (complexity)|P]] is defined as the set of problems solvable by a [[Turing machine]] in [[polynomial time]]. Similarly, quantum complexity classes may be defined using quantum models of computation, such as the [[Quantum computer|quantum circuit model]] or the equivalent [[quantum Turing machine]]. One of the main aims of quantum complexity theory is to find out how these classes relate to classical complexity classes such as [[P (complexity)|P]], [[NP (complexity)|NP]], [[BPP (complexity)|BPP]], and [[PSPACE]].
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=":0">{{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|pages=193–217|doi=10.1090/psapm/058/1922899|issn=2324-7088}}</ref><ref name=":3">{{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 ed|___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=":0" />
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=":1" /> These notations also 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.
== Complexity Classes Overview ==
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=":2">{{Cite journal|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]}}</ref>
{| class="wikitable"
|+
!Complexity Class
!Criteria
|-
|P
|Promise problems for which a polynomial time deterministic Turing machine accepts all strings in <math>A_{yes}</math> and rejects all strings in <math>A_{no}</math><ref name=":2" />
|-
|BPP
|Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in <math>A_{yes}</math> with a probability of at least <math>\frac{2}{3}</math>, and accepts every string in <math>A_{no}</math> with a probability of at most <math>\frac{1}{3}</math><ref name=":2" />
|-
|BQP
|Promise problems such that for functions <math>a,b:\mathbb {N}\rightarrow[0,1]</math>, there exists a polynomial time generated family of quantum circuits <math>Q={\{Q_n:n\in \mathbb{N}\}}</math>, where <math>Q_n</math> is a circuit which accepts <math>n</math> qubits and gives an output of one qubit. An element <math>x</math> of <math>A_{yes}</math> is accepted by <math>Q</math> with a probability greater than or equal to <math>a(\left \vert x \right \vert) </math>. An element <math>x</math> of <math>A_{no}</math> is accepted by <math>Q</math> with a probability less than or equal to <math>b(\left \vert x\right \vert)</math>. <ref name=":2" />
|-
|PP
|Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in <math>A_{yes}</math> with a probability greater than <math>\frac{1}{2}</math>, and accepts every string in <math>A_{no}</math> with a probability of at most <math>\frac{1}{2}</math><ref name=":2" />
|-
|P-SPACE
|Promise problems for which a deterministic Turing machine, that runs in polynomial space, accepts every string in <math>A_{yes}</math> and rejects all strings in <math>A_{no}</math><ref name=":2" />
|}
== Simulating Quantum Circuits ==▼
There is no known way to efficiently simulate a quantum computational model with a classical computer. This means that a classical computer cannot simulate a quantum computational model in polynomial time. However, a [[quantum circuit]] of <math>S(n)</math> qubits with <math>
▲== Quantum Circuits ==
== Query Complexity ==
===
The Deutsch-Jozsa algorithm is a quantum algorithm designed to solve a toy problem with a smaller query complexity than is possible with a classical algorithm. The toy problem asks whether a function <math>f:\{0,1\}^n\rightarrow\{0,1\}</math> is constant or balanced, those being the only two possibilities.<ref name=":3" /> The only way to evaluate the function <math>f</math> is to consult a [[black box]] or [[Oracle machine|oracle]]. A classical [[deterministic algorithm]] will have to check more than half of the possible inputs to be sure of whether or not the function is constant or balanced. With <math>2^n</math> possible inputs, the query complexity of the most efficient classical deterministic algorithm is <math>2^{n-1}+1</math>.<ref name=":3" /> The Deutsch-Jozsa algorithm takes advantage of quantum parallelism to check all of the elements of the ___domain at once and only needs to query the oracle once. Meaning the query complexity of the Deutsch-Jozsa algorithm is <math>1</math>.<ref name=":3" />
▲There is no known way to efficiently simulate a quantum computational model with a classical computer. This means that a classical computer cannot simulate a quantum computational model in polynomial time. However, a [[quantum circuit]] of <math>S(n)</math> qubits with <math>O(T(n))</math> quantum gates can be simulated by a classical circuit with <math>O(2^{S(n)}T(n)^3)</math> [[Logic gate|classical gates]].<ref name=":1">{{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|volume=|pages=103–127|publisher=WORLD SCIENTIFIC|isbn=978-981-02-4117-9|access-date=October 10, 2020}}</ref> This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. First the amplitudes associated with the <math>S(n)</math> qubits must be accounted for. Therefore, <math>2^{S(n)}</math>amplitudes must be accounted for with a <math>2^{S(n)}</math> dimensional complex vector which it the state vector for the <math>S(n)</math> qubit system.<ref>{{Cite journal|last=Häner|first=Thomas|last2=Steiger|first2=Damian S.|date=2017-11-12|title=0.5 petabyte simulation of a 45-qubit quantum circuit|url=http://dx.doi.org/10.1145/3126908.3126947|journal=Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis|___location=New York, NY, USA|publisher=ACM|doi=10.1145/3126908.3126947|isbn=978-1-4503-5114-0}}</ref> Next the application of the <math>T(n)</math> quantum gates on <math>2^{S(n)}</math> amplitudes must be accounted for. Therefore, <math>O(T(n))</math> bits of precision will be required required for encoding each amplitude.<ref name=":1" /> So it takes <math>O(2^{S(n)}T(n))</math> classical bits to account for the state vector. The quantum gates can be represented as <math>2^{S(n)}\times2^{S(n)}</math> [[Sparse matrix|sparse matrices]].<ref name=":1" /> So to account for the each application of all of the quantum gates, the state vector must be multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix for every quantum gate. Every time the state vector is multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix <math>O(2^{S(n)})</math> arithmetic operations must be preformed.<ref name=":1" /> Therefore, there are <math>O(2^{S(n)}T(n)^2)</math> bit operations for every quantum gate applied to the state vector. So <math>O(2^{S(n)}T(n)^2)</math> classical gate are needed to simulate <math>S(n)</math> qubit circuit with just one quantum gate. Therefore, <math>O(2^{S(n)}T(n)^3)</math> classical gates can simulate a quantum circuit of <math>S(n)</math> qubits with <math>O(T(n))</math> quantum gates.<ref name=":1" />
== References ==
| |||