Quantum complexity theory - Revision history

Éno Tallinavel: /* Simulation of quantum circuits */Clarified the sentence while preserving the same technical meaning.

2025-06-20T16:28:59Z

Simulation of quantum circuits: Clarified the sentence while preserving the same technical meaning.

← Previous revision		Revision as of 16:28, 20 June 2025
Line 74:		Line 74:

	== Simulation of quantum circuits ==		== Simulation of 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>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=":12"/> This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the <math>S(n)</math> qubits must be accounted for. Each of the states of the <math>S(n)</math> qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a [[linear combination]] of its [[Euclidean vector\|component vectors]] with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one.<ref name=":12" /> The entries of the state vector are these amplitudes. ~~Which~~ ~~entry~~ ~~each~~ of the ~~amplitudes~~ ~~are~~ correspond to ~~the~~ ~~none~~-zero component of the ~~component~~ vector ~~which they are the coefficients of in the linear combination description~~. As an equation this is described as <math>\alpha \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> or <math>\alpha \left \vert 1 \right \rangle + \beta \left \vert 0 \right \rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> using [[Bra–ket notation\|Dirac notation]]. The state of the entire <math>S(n)</math> qubit system can be described by a single state vector. This state vector describing the entire system is the tensor product of the state vectors describing the individual qubits in the system. The result of the tensor products of the <math>S(n)</math> qubits is a single state vector which has <math>2^{S(n)}</math> dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, <math>2^{S(n)}</math>amplitudes must be accounted for with a <math>2^{S(n)}</math> dimensional complex vector which is the state vector for the <math>S(n)</math> qubit system.<ref>{{Cite book\|last1=Häner\|first1=Thomas\|last2=Steiger\|first2=Damian S.\|title=Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis \|chapter=0.5 petabyte simulation of a 45-qubit quantum circuit \|date=2017-11-12\|chapter-url=http://dx.doi.org/10.1145/3126908.3126947\|pages=1–10\|location=New York, NY, USA\|publisher=ACM\|doi=10.1145/3126908.3126947\|arxiv=1704.01127\|isbn=978-1-4503-5114-0\|s2cid=3338733}}</ref> In order to obtain an upper bound for the number of gates required to simulate a quantum circuit we need a sufficient upper bound for the amount data used to specify the information about each of the <math>2^{S(n)}</math> amplitudes. To do this <math>O(T(n))</math> bits of precision are sufficient for encoding each amplitude.<ref name=":12" /> So it takes <math>O(2^{S(n)}T(n))</math> classical bits to account for the state vector of the <math>S(n)</math> qubit system. Next the application of the <math>T(n)</math> quantum gates on <math>2^{S(n)}</math> amplitudes must be accounted for. The quantum gates can be represented as <math>2^{S(n)}\times2^{S(n)}</math> [[Sparse matrix\|sparse matrices]].<ref name=":12" /> So to account for the application of each of the <math>T(n)</math> quantum gates, the state vector must be multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix for each of the <math>T(n)</math> quantum gates. 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 performed.<ref name=":12" /> 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 are needed to simulate a quantum circuit of <math>S(n)</math> qubits with <math>T(n)</math> quantum gates.<ref name=":12" /> While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the fact that <math>\mathsf{BPP\subseteq BQP}</math>.<ref name=":27"/>		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>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=":12"/> This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the <math>S(n)</math> qubits must be accounted for. Each of the states of the <math>S(n)</math> qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a [[linear combination]] of its [[Euclidean vector\|component vectors]] with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one.<ref name=":12" /> The entries of the state vector are these amplitudes. The amplitudes, acting as coefficients in the linear combination description, each correspond to a non-zero component of the state vector. As an equation this is described as <math>\alpha \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> or <math>\alpha \left \vert 1 \right \rangle + \beta \left \vert 0 \right \rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> using [[Bra–ket notation\|Dirac notation]]. The state of the entire <math>S(n)</math> qubit system can be described by a single state vector. This state vector describing the entire system is the tensor product of the state vectors describing the individual qubits in the system. The result of the tensor products of the <math>S(n)</math> qubits is a single state vector which has <math>2^{S(n)}</math> dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, <math>2^{S(n)}</math>amplitudes must be accounted for with a <math>2^{S(n)}</math> dimensional complex vector which is the state vector for the <math>S(n)</math> qubit system.<ref>{{Cite book\|last1=Häner\|first1=Thomas\|last2=Steiger\|first2=Damian S.\|title=Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis \|chapter=0.5 petabyte simulation of a 45-qubit quantum circuit \|date=2017-11-12\|chapter-url=http://dx.doi.org/10.1145/3126908.3126947\|pages=1–10\|location=New York, NY, USA\|publisher=ACM\|doi=10.1145/3126908.3126947\|arxiv=1704.01127\|isbn=978-1-4503-5114-0\|s2cid=3338733}}</ref> In order to obtain an upper bound for the number of gates required to simulate a quantum circuit we need a sufficient upper bound for the amount data used to specify the information about each of the <math>2^{S(n)}</math> amplitudes. To do this <math>O(T(n))</math> bits of precision are sufficient for encoding each amplitude.<ref name=":12" /> So it takes <math>O(2^{S(n)}T(n))</math> classical bits to account for the state vector of the <math>S(n)</math> qubit system. Next the application of the <math>T(n)</math> quantum gates on <math>2^{S(n)}</math> amplitudes must be accounted for. The quantum gates can be represented as <math>2^{S(n)}\times2^{S(n)}</math> [[Sparse matrix\|sparse matrices]].<ref name=":12" /> So to account for the application of each of the <math>T(n)</math> quantum gates, the state vector must be multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix for each of the <math>T(n)</math> quantum gates. 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 performed.<ref name=":12" /> 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 are needed to simulate a quantum circuit of <math>S(n)</math> qubits with <math>T(n)</math> quantum gates.<ref name=":12" /> While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the fact that <math>\mathsf{BPP\subseteq BQP}</math>.<ref name=":27"/>

	==Quantum query complexity ==		==Quantum query complexity ==

Headbomb: Altered template type. Add: series, chapter, title. | Use this tool. Report bugs. | #UCB_Gadget

2024-12-16T15:27:47Z

Altered template type. Add: series, chapter, title. | Use this tool. Report bugs. | #UCB_Gadget

← Previous revision		Revision as of 15:27, 16 December 2024
Line 10:		Line 10:
	A [[complexity class]] is a collection of [[computational problem]]s 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 circuit\|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]].		A [[complexity class]] is a collection of [[computational problem]]s 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 circuit\|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=":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" />		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 book\|last=Vazirani\|first=Umesh V.\|title=Quantum Computation \|chapter=A survey of quantum complexity theory \|series=Proceedings of Symposia in Applied Mathematics \|date=2002 \|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.		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.

Maxeto0910: no sentence

2023-10-22T08:41:18Z

no sentence

← Previous revision		Revision as of 08:41, 22 October 2023
Line 55:		Line 55:
	\|}		\|}

	[[File:BQP complexity class diagram.svg\|thumb\|The suspected relationship of BQP to other complexity classes.<ref>Nielsen, p. 42</ref>]]		[[File:BQP complexity class diagram.svg\|thumb\|The suspected relationship of BQP to other complexity classes<ref>Nielsen, p. 42</ref>]]

	<!-- Basic definition of BQP -->		<!-- Basic definition of BQP -->

179.29.131.129: /* Background */typo

2023-08-18T00:02:54Z

Background: typo

← Previous revision		Revision as of 00:02, 18 August 2023
Line 12:		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" />		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 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.		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 ==		== Overview of complexity classes ==

Citation bot: 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

2023-08-08T17:03:49Z

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

← Previous revision		Revision as of 17:03, 8 August 2023
Line 74:		Line 74:

	== Simulation of quantum circuits ==		== Simulation of 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>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=":12"/> This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the <math>S(n)</math> qubits must be accounted for. Each of the states of the <math>S(n)</math> qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a [[linear combination]] of its [[Euclidean vector\|component vectors]] with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one.<ref name=":12" /> The entries of the state vector are these amplitudes. Which entry each of the amplitudes are correspond to the none-zero component of the component vector which they are the coefficients of in the linear combination description. As an equation this is described as <math>\alpha \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> or <math>\alpha \left \vert 1 \right \rangle + \beta \left \vert 0 \right \rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> using [[Bra–ket notation\|Dirac notation]]. The state of the entire <math>S(n)</math> qubit system can be described by a single state vector. This state vector describing the entire system is the tensor product of the state vectors describing the individual qubits in the system. The result of the tensor products of the <math>S(n)</math> qubits is a single state vector which has <math>2^{S(n)}</math> dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, <math>2^{S(n)}</math>amplitudes must be accounted for with a <math>2^{S(n)}</math> dimensional complex vector which is the state vector for the <math>S(n)</math> qubit system.<ref>{{Cite ~~journal~~\|last1=Häner\|first1=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~~\|pages=1–10\|location=New York, NY, USA\|publisher=ACM\|doi=10.1145/3126908.3126947\|arxiv=1704.01127\|isbn=978-1-4503-5114-0\|s2cid=3338733}}</ref> In order to obtain an upper bound for the number of gates required to simulate a quantum circuit we need a sufficient upper bound for the amount data used to specify the information about each of the <math>2^{S(n)}</math> amplitudes. To do this <math>O(T(n))</math> bits of precision are sufficient for encoding each amplitude.<ref name=":12" /> So it takes <math>O(2^{S(n)}T(n))</math> classical bits to account for the state vector of the <math>S(n)</math> qubit system. Next the application of the <math>T(n)</math> quantum gates on <math>2^{S(n)}</math> amplitudes must be accounted for. The quantum gates can be represented as <math>2^{S(n)}\times2^{S(n)}</math> [[Sparse matrix\|sparse matrices]].<ref name=":12" /> So to account for the application of each of the <math>T(n)</math> quantum gates, the state vector must be multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix for each of the <math>T(n)</math> quantum gates. 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 performed.<ref name=":12" /> 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 are needed to simulate a quantum circuit of <math>S(n)</math> qubits with <math>T(n)</math> quantum gates.<ref name=":12" /> While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the fact that <math>\mathsf{BPP\subseteq BQP}</math>.<ref name=":27"/>		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>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=":12"/> This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the <math>S(n)</math> qubits must be accounted for. Each of the states of the <math>S(n)</math> qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a [[linear combination]] of its [[Euclidean vector\|component vectors]] with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one.<ref name=":12" /> The entries of the state vector are these amplitudes. Which entry each of the amplitudes are correspond to the none-zero component of the component vector which they are the coefficients of in the linear combination description. As an equation this is described as <math>\alpha \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> or <math>\alpha \left \vert 1 \right \rangle + \beta \left \vert 0 \right \rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> using [[Bra–ket notation\|Dirac notation]]. The state of the entire <math>S(n)</math> qubit system can be described by a single state vector. This state vector describing the entire system is the tensor product of the state vectors describing the individual qubits in the system. The result of the tensor products of the <math>S(n)</math> qubits is a single state vector which has <math>2^{S(n)}</math> dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, <math>2^{S(n)}</math>amplitudes must be accounted for with a <math>2^{S(n)}</math> dimensional complex vector which is the state vector for the <math>S(n)</math> qubit system.<ref>{{Cite book\|last1=Häner\|first1=Thomas\|last2=Steiger\|first2=Damian S.\|title=Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis \|chapter=0.5 petabyte simulation of a 45-qubit quantum circuit \|date=2017-11-12\|chapter-url=http://dx.doi.org/10.1145/3126908.3126947\|pages=1–10\|location=New York, NY, USA\|publisher=ACM\|doi=10.1145/3126908.3126947\|arxiv=1704.01127\|isbn=978-1-4503-5114-0\|s2cid=3338733}}</ref> In order to obtain an upper bound for the number of gates required to simulate a quantum circuit we need a sufficient upper bound for the amount data used to specify the information about each of the <math>2^{S(n)}</math> amplitudes. To do this <math>O(T(n))</math> bits of precision are sufficient for encoding each amplitude.<ref name=":12" /> So it takes <math>O(2^{S(n)}T(n))</math> classical bits to account for the state vector of the <math>S(n)</math> qubit system. Next the application of the <math>T(n)</math> quantum gates on <math>2^{S(n)}</math> amplitudes must be accounted for. The quantum gates can be represented as <math>2^{S(n)}\times2^{S(n)}</math> [[Sparse matrix\|sparse matrices]].<ref name=":12" /> So to account for the application of each of the <math>T(n)</math> quantum gates, the state vector must be multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix for each of the <math>T(n)</math> quantum gates. 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 performed.<ref name=":12" /> 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 are needed to simulate a quantum circuit of <math>S(n)</math> qubits with <math>T(n)</math> quantum gates.<ref name=":12" /> While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the fact that <math>\mathsf{BPP\subseteq BQP}</math>.<ref name=":27"/>

	==Quantum query complexity ==		==Quantum query complexity ==

RobinK: /* Overview of complexity classes */ typos

2023-07-22T00:39:24Z

Overview of complexity classes: typos

← Previous revision		Revision as of 00:39, 22 July 2023
Line 15:		Line 15:

	== Overview of complexity classes ==		== Overview of complexity classes ==
	The important complexity classes P, BPP, BQP, PP, and ~~P-Space~~ can be compared based on [[Promise problem\|promise problems]]. 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 empty: <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>		The important complexity classes P, BPP, BQP, PP, and PSPACE can be compared based on [[Promise problem\|promise problems]]. 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 empty: <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"		{\| class="wikitable"
	\|+		\|+
Line 33:		Line 33:
	\|Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in <math>A_\text{yes}</math> with a probability greater than <math>\frac{1}{2}</math>, and accepts every string in <math>A_\text{no}</math> with a probability of at most <math>\frac{1}{2}</math><ref name=":27"/>		\|Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in <math>A_\text{yes}</math> with a probability greater than <math>\frac{1}{2}</math>, and accepts every string in <math>A_\text{no}</math> with a probability of at most <math>\frac{1}{2}</math><ref name=":27"/>
	\|-		\|-
			\|PSPACE
	\|P-SPACE
	\|Promise problems for which a deterministic Turing machine, that runs in polynomial space, accepts every string in <math>A_\text{yes}</math> and rejects all strings in <math>A_\text{no}</math><ref name=":27"/>		\|Promise problems for which a deterministic Turing machine, that runs in polynomial space, accepts every string in <math>A_\text{yes}</math> and rejects all strings in <math>A_\text{no}</math><ref name=":27"/>
	\|}		\|}

Freoh: Copied content from quantum computing; see that page's history for attribution

2023-07-12T15:12:38Z

Copied content from quantum computing; see that page's history for attribution

← Previous revision		Revision as of 15:12, 12 July 2023
Line 125:		Line 125:
	==== Deutsch-Jozsa algorithm ====		==== Deutsch-Jozsa algorithm ====
	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=":32"/> 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=":32" /> 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, making its query complexity <math>1</math>.<ref name=":32" />		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=":32"/> 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=":32" /> 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, making its query complexity <math>1</math>.<ref name=":32" />

			==Other theories of quantum physics==

			It has been speculated that further advances in physics could lead to even faster computers. For instance, it has been shown that a non-local hidden variable quantum computer based on [[De Broglie–Bohm theory\|Bohmian Mechanics]] could implement a search of an {{mvar\|N}}-item database in at most <math>O(\sqrt[3]{N})</math> steps, a slight speedup over [[Grover's algorithm]], which runs in <math>O(\sqrt{N})</math> steps. Note, however, that neither search method would allow quantum computers to solve [[NP-complete]] problems in polynomial time.<ref name="auto">{{cite web \|title=Quantum Computing and Hidden Variables \|last=Aaronson \|first=Scott \|url=http://www.scottaaronson.com/papers/qchvpra.pdf}}</ref> Theories of [[quantum gravity]], such as [[M-theory]] and [[loop quantum gravity]], may allow even faster computers to be built. However, defining computation in these theories is an open problem due to the [[problem of time]]; that is, within these physical theories there is currently no obvious way to describe what it means for an observer to submit input to a computer at one point in time and then receive output at a later point in time.<ref>{{Cite journal \|first=Scott \|last=Aaronson \|title=NP-complete Problems and Physical Reality \|journal=ACM SIGACT News \|volume=2005 \|arxiv=quant-ph/0502072 \|year=2005 \|bibcode=2005quant.ph..2072A \|author-link=Scott Aaronson}} See section 7 "Quantum Gravity": "[...] to anyone who wants a test or benchmark for a favorite quantum gravity theory,[author's footnote: That is, one without all the bother of making numerical predictions and comparing them to observation] let me humbly propose the following: ''can you define Quantum Gravity Polynomial-Time?'' [...] until we can say what it means for a 'user' to specify an 'input' and 'later' receive an 'output'—''there is no such thing as computation, not even theoretically.''" (emphasis in original)</ref><ref>{{cite web \|url=http://www.dwavesys.com/en/pressreleases.html#lm_2011 \|title=D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation \|access-date=30 May 2011 \|date=25 May 2011 \|publisher=D-Wave \|archive-date=22 December 2020 \|archive-url=https://web.archive.org/web/20201222041457/https://www.dwavesys.com/en/pressreleases.html#lm_2011 \|url-status=dead }}</ref>

	==See also==		==See also==

Jessymilare: /* Simulation of quantum circuits */Fixed typo.

2023-07-02T15:03:11Z

Simulation of quantum circuits: Fixed typo.

← Previous revision		Revision as of 15:03, 2 July 2023
Line 74:		Line 74:

	== Simulation of quantum circuits ==		== Simulation of 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>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=":12"/> This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the <math>S(n)</math> qubits must be accounted for. Each of the states of the <math>S(n)</math> qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a [[linear combination]] of its [[Euclidean vector\|component vectors]] with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one.<ref name=":12" /> The entries of the state vector are these amplitudes. Which entry each of the amplitudes are correspond to the none-zero component of the component vector which they are the coefficients of in the linear combination description. As an equation this is described as <math>\alpha \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> or <math>\alpha \left \vert 1 \right \rangle + \beta \left \vert 0 \right \rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> using [[Bra–ket notation\|Dirac notation]]. The state of the entire <math>S(n)</math> qubit system can be described by a single state vector. This state vector describing the entire system is the tensor product of the state vectors describing the individual qubits in the system. The result of the tensor products of the <math>S(n)</math> qubits is a single state vector which has <math>2^{S(n)}</math> dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, <math>2^{S(n)}</math>amplitudes must be accounted for with a <math>2^{S(n)}</math> dimensional complex vector which is the state vector for the <math>S(n)</math> qubit system.<ref>{{Cite journal\|last1=Häner\|first1=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\|pages=1–10\|location=New York, NY, USA\|publisher=ACM\|doi=10.1145/3126908.3126947\|arxiv=1704.01127\|isbn=978-1-4503-5114-0\|s2cid=3338733}}</ref> In order to obtain an upper bound for the number of gates required to simulate a quantum circuit we need a sufficient upper bound for the amount data used to specify the information about each of the <math>2^{S(n)}</math> amplitudes. To do this <math>O(T(n))</math> bits of precision are sufficient for encoding each amplitude.<ref name=":12" /> So it takes <math>O(2^{S(n)}T(n))</math> classical bits to account for the state vector of the <math>S(n)</math> qubit system. Next the application of the <math>T(n)</math> quantum gates on <math>2^{S(n)}</math> amplitudes must be accounted for. The quantum gates can be represented as <math>2^{S(n)}\times2^{S(n)}</math> [[Sparse matrix\|sparse matrices]].<ref name=":12" /> So to account for the application of each of the <math>T(n)</math> quantum gates, the state vector must be multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix for each of the <math>T(n)</math> quantum gates. 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 performed.<ref name=":12" /> 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 are needed to simulate a quantum circuit of <math>S(n)</math> qubits with <math>T(n)</math> quantum gates.<ref name=":12" /> While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the ~~belief~~ that <math>\mathsf{BPP\subseteq BQP}</math>.<ref name=":27"/>		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>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=":12"/> This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the <math>S(n)</math> qubits must be accounted for. Each of the states of the <math>S(n)</math> qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a [[linear combination]] of its [[Euclidean vector\|component vectors]] with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one.<ref name=":12" /> The entries of the state vector are these amplitudes. Which entry each of the amplitudes are correspond to the none-zero component of the component vector which they are the coefficients of in the linear combination description. As an equation this is described as <math>\alpha \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> or <math>\alpha \left \vert 1 \right \rangle + \beta \left \vert 0 \right \rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}</math> using [[Bra–ket notation\|Dirac notation]]. The state of the entire <math>S(n)</math> qubit system can be described by a single state vector. This state vector describing the entire system is the tensor product of the state vectors describing the individual qubits in the system. The result of the tensor products of the <math>S(n)</math> qubits is a single state vector which has <math>2^{S(n)}</math> dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, <math>2^{S(n)}</math>amplitudes must be accounted for with a <math>2^{S(n)}</math> dimensional complex vector which is the state vector for the <math>S(n)</math> qubit system.<ref>{{Cite journal\|last1=Häner\|first1=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\|pages=1–10\|location=New York, NY, USA\|publisher=ACM\|doi=10.1145/3126908.3126947\|arxiv=1704.01127\|isbn=978-1-4503-5114-0\|s2cid=3338733}}</ref> In order to obtain an upper bound for the number of gates required to simulate a quantum circuit we need a sufficient upper bound for the amount data used to specify the information about each of the <math>2^{S(n)}</math> amplitudes. To do this <math>O(T(n))</math> bits of precision are sufficient for encoding each amplitude.<ref name=":12" /> So it takes <math>O(2^{S(n)}T(n))</math> classical bits to account for the state vector of the <math>S(n)</math> qubit system. Next the application of the <math>T(n)</math> quantum gates on <math>2^{S(n)}</math> amplitudes must be accounted for. The quantum gates can be represented as <math>2^{S(n)}\times2^{S(n)}</math> [[Sparse matrix\|sparse matrices]].<ref name=":12" /> So to account for the application of each of the <math>T(n)</math> quantum gates, the state vector must be multiplied by a <math>2^{S(n)}\times2^{S(n)}</math> sparse matrix for each of the <math>T(n)</math> quantum gates. 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 performed.<ref name=":12" /> 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 are needed to simulate a quantum circuit of <math>S(n)</math> qubits with <math>T(n)</math> quantum gates.<ref name=":12" /> While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the fact that <math>\mathsf{BPP\subseteq BQP}</math>.<ref name=":27"/>

	==Quantum query complexity ==		==Quantum query complexity ==

Nuretok: /* Overview of complexity classes */ Wording

2023-05-10T19:03:24Z

Overview of complexity classes: Wording

← Previous revision		Revision as of 19:03, 10 May 2023
Line 15:		Line 15:

	== Overview of complexity classes ==		== 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_\text{yes},A_\text{no})</math>. <math>A_\text{yes}</math> is the set of yes instances, <math>A_\text{no}</math> is the set of no instances, and the intersection of these sets is ~~such that~~ <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>		The important complexity classes P, BPP, BQP, PP, and P-Space can be compared based on [[Promise problem\|promise problems]]. 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 empty: <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"		{\| class="wikitable"
	\|+		\|+

198.168.103.76: changed the link for "quantum circuit model" to a more specific page

2023-04-05T15:22:29Z

changed the link for "quantum circuit model" to a more specific page

← Previous revision		Revision as of 15:22, 5 April 2023
Line 8:		Line 8:
	==Background==		==Background==
	{{See also\|Computational complexity\|Complexity class}}		{{See also\|Computational complexity\|Complexity class}}
	A [[complexity class]] is a collection of [[computational problem]]s 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]].		A [[complexity class]] is a collection of [[computational problem]]s 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 circuit\|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=":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" />		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" />

← Previous revision		Revision as of 15:27, 16 December 2024
Line 10:		Line 10:
	A [[complexity class]] is a collection of [[computational problem]]s 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 circuit\|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]].		A [[complexity class]] is a collection of [[computational problem]]s 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 circuit\|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=":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" />		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 book\|last=Vazirani\|first=Umesh V.\|title=Quantum Computation \|chapter=A survey of quantum complexity theory \|series=Proceedings of Symposia in Applied Mathematics \|date=2002 \|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.		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.