Quantum complexity theory: Difference between revisions

Revision as of 19:14, 23 November 2020

Latest revision as of 12:53, 3 August 2025

(35 intermediate revisions by 26 users not shown)

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 8:

==Background==

{{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 [[quantumQuantum computercircuit|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 journalbook|last=Vazirani|first=Umesh V.|datetitle=2002Quantum Computation |titlechapter=A survey of quantum complexity theory |url=http://dx.doi.org/10.1090/psapm/058/1922899|journalseries=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|volume=|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 ==

== Complexity Classes Overview ==

SomeThe important complexity classes are P, BPP, BQP, PP, and P-Space.PSPACE Tocan definebe thesecompared webased firston define a[[Promise problem|promise problemproblems]]. 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 such thatempty: <math>A_\text{yes} \cap A_\text{no} = \emptysetvarnothing</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 class=http://arxiv.org/abs/0804.3401|journal=arXiv:0804.3401 [quant-ph]|arxiveprint=0804.3401}}</ref>

{| class="wikitable"

|+

Line 22:

|-

|P

|Promise problems for which a polynomial time deterministic Turing machine accepts all strings in <math>A_\text{yes}</math> and rejects all strings in <math>A_\text{no}</math><ref name=":27"/>

|-

|BPP

|Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in <math>A_\text{yes}</math> with a probability of at least <math>\frac{2}{3}</math>, and accepts every string in <math>A_\text{no}</math> with a probability of at most <math>\frac{1}{3}</math><ref name=":27"/>

|-

|BQP

|Promise problems such that for functions <math>a,b:\mathbb {N}\rightarrowto [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_\text{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_\text{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=":27"/>

|-

|PP

|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"/>

|}

Line 55:

|}

[[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 -->

Line 61:

<!-- Relation of BQP to probabilistic complexity classes -->

As a class of probabilistic problems, BQP is the quantum counterpart to [[Bounded-error probabilistic polynomial|BPP]] ("bounded error, probabilistic, polynomial time"), the class of problems that can be efficiently solved by [[probabilistic Turing machine]]s with bounded error.<ref>{{cite book | author1-link= Michael Nielsen| author1=Nielsen, Michael |author2-link = Isaac L. Chuang |author2=Chuang, Isaac |title=Quantum Computation and Quantum Information |publisher=Cambridge University Press |___location=Cambridge |year=2000|page=41 |isbn=978-0-521-63503-5 |oclc= 174527496 |url=https://books.google.com/books?id=aai-P4V9GJ8C}}</ref> It is known that BPP<math>\mathsf{BPP\subseteq BQP}</math>BQP and widely suspected, but not proven, that BQP<math>\mathsf{BQP\nsubseteq BPP}</math>BPP, which intuitively would mean that quantum computers are more powerful than classical computers in terms of time complexity.<ref>Nielsen, p. 201</ref> BQP is a subset of [[PP (complexity)|PP]].

<!-- Relation of BQP to basic deterministic complexity classes -->

The exact relationship of BQP to [[P (complexity)|P]], [[NP (complexity)|NP]], and [[PSPACE (complexity)|PSPACE]] is not known. However, it is known that P<math>\mathsf{P\subseteq</math> BQP<math> \subseteq PSPACE}</math>PSPACE; that is, the class of problems that can be efficiently solved by quantum computers includes all problems that can be efficiently solved by deterministic classical computers but does not include any problems that cannot be solved by classical computers with polynomial space resources. It is further suspected that BQP is a strict superset of P, meaning there are problems that are efficiently solvable by quantum computers that are not efficiently solvable by deterministic classical computers. For instance, [[integer factorization]] and the [[discrete logarithm problem]] are known to be in BQP and are suspected to be outside of P. On the relationship of BQP to NP, little is known beyond the fact that some NP problems are in BQP (integer factorization and the discrete logarithm problem are both in NP, for example). It is suspected that NP<math>\mathsf{NP\nsubseteq BQP}</math>BQP; that is, it is believed that there are efficiently checkable problems that are not efficiently solvable by a quantum computer. As a direct consequence of this belief, it is also suspected that BQP is disjoint from the class of [[NP-complete]] problems (if any NP-complete problem were in BQP, then it follows from [[NP-hard]]ness that all problems in NP are in BQP).<ref name=BernVazi>{{cite journal |last1=Bernstein |first1=Ethan |last2=Vazirani |first2=Umesh |doi=10.1137/S0097539796300921 |title=Quantum Complexity Theory |year=1997 |pages=1411–1473 |volume=26 |journal=SIAM Journal on Computing |url=http://www.cs.berkeley.edu/~vazirani/bv.ps |issue=5|citeseerx=10.1.1.144.7852 }}</ref>

<!-- Summary of relationship to essential complexity classes -->

Line 71:

<!-- Relation of BQP to other complexity classes -->

It is also known that BQP is contained in the complexity class ''[[Sharp-P|{{tmath|\color{Blue}\mathsf{\#P} }}]]'' (or more precisely in the associated class of decision problems ''{{tmath|\mathsf{P^{^{\#P}''} } }}),<ref name=BernVazi/> which is a subset of [[PSPACE]].

== Simulation of quantum circuits ==

== 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>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. WhichThe entryamplitudes, eachacting ofas coefficients in the amplitudeslinear arecombination description, each correspond to thea nonenon-zero component of the componentstate 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 journalbook|last1=Häner|first1=Thomas|last2=Steiger|first2=Damian S.|datetitle=2017-11-12Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis |titlechapter=0.5 petabyte simulation of a 45-qubit quantum circuit |date=2017-11-12|chapter-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 preformedperformed.<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 belieffact that <math>BBP\mathsf{BPP\subseteq BQP}</math>.<ref name=":27"/>

==Quantum Queryquery Complexitycomplexity ==

One major advantage of using a quantum computational system instead of a classical one, is that a quantum computer may be able to give a [[Polynomial-time algorithm|polynomial time algorithm]] for some problem for which no classical polynomial time algorithm exists, but more importantly, a quantum computer may significantly decrease the calculation time for a problem that a classical computer can already solve efficiently. Essentially, a quantum computer may be able to both determine how long it will take to solve a problem, while a classical computer may be unable to do so, and can also greatly improve the computational efficiency associated with the solution to a particular problem. Quantum query complexity refers to how complex, or how many queries to the graph associated with the solution of a particular problem, are required to solve the problem. Before we delve further into query complexity, let us consider some background regarding graphing solutions to particular problems, and the queries associated with these solutions.

=== Query Modelsmodels of Directeddirected Graphsgraphs ===

One type of problem that quantum computing can make easier to solve are graph problems. If we are to consider the amount of queries to a graph that are required to solve a given problem, let us first consider the most common types of graphs, called [[directed graph]]s, that are associated with this type of computational modelling. In brief, directed graphs are graphs where all edges between vertices are unidirectional. Directed graphs are formally defined as the graph <math>G=(N,E)</math>, where N is the set of vertices, or nodes, and E is the set of edges.<ref>{{Cite web|last=Nykamp|first=D.Q.|date=|title=Directed Graph Definition|url=https://mathinsight.org/definition/directed_graph|url-status=live|archive-url=|archive-date=|access-date=|website=}}</ref>

==== Adjacency Matrixmatrix Modelmodel ====

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 Arrayarray Modelmodel ====

Next, there is the slightly more complicated adjacency array model built on the idea of [[adjacency list]]s, where every vertex, <math>u </math>'','' is associated with an array of neighboring vertices such that <math>f_i:[d_i^+]\rightarrow[n] </math>, for the out-degrees of vertices <math>d_i^+,...,d_n^+ </math>, where <math>n </math> is the minimum value of the upper bound of this model, and <math>f_i(j) </math> returns the "<math>j^{th} </math>" vertex adjacent to <math>i </math>. Additionally, the adjacency array model satisfies the simple graph condition, <math>\forall i\in[n],j,j^{'}\in[k],j\neq j^{'}: f_i(j)\neq f_i(j^{'}) </math>, meaning that there is only one edge between any pair of vertices, and the number of edges is minimized throughout the entire model (see [[Spanning tree]] model for more background).<ref name=":0" />

=== Quantum Queryquery Complexitycomplexity of Certaincertain Typestypes of Graphgraph Problemsproblems ===

Both of the above models can be used to determine the query complexity of particular types of graphing problems, including the [[Connectivity (graph theory)|connectivity]], [[Strongly connected component|strong connectivity]] (a directed graph version of the connectivity model), [[minimum spanning tree]], and [[Shortest path problem|single source shortest path]] models of graphs. An important caveat to consider is that the quantum complexity of a particular type of graphing problem can change based on the query model (namely either matrix or array) used to determine the solution. The following table showing the quantum query complexities of these types of graphing problems illustrates this point well.

{| class="wikitable"

|+

Quantum Queryquery Complexitycomplexity of Certaincertain Typestypes of Graphgraph Problemsproblems

!Problem

!Matrix Modelmodel

!Array Modelmodel

|-

|Minimum Spanningspanning Treetree

|<math>\Theta(n^{3/2})</math>

|<math>\Theta(\sqrt{nm})</math>

Line 105:

|<math>\Theta(n)</math>

|-

|Strong Connectivityconnectivity

|<math>\Theta(n^{3/2})</math>

|<math>\Omega(\sqrt{nm})</math>, <math>O(\sqrt{nmlognm\log(n)})</math>

|-

|Single Sourcesource Shortestshortest Pathpath

|<math>\Omega(n^{3/2})</math>, <math>O(n^{3/2}\log^2n)</math>

|<math>\Omega(\sqrt{nm})</math>, <math>O(\sqrt{nm}\log^2(n))</math>

|}

Notice the discrepancy between the quantum query complexities associated with a particular type of problem, depending on which query model was used to determine the complexity. For example, when the matrix model is used, the quantum complexity of the connectivity model in [[Big O notation]] is <math>\Theta(n^{3/2})</math>, but when the array model is used, the complexity is <math>\Theta(n)</math>. Additionally, for brevity, we use the shorthand <math>m</math> in certain cases, where <math>m=\Theta(n^2)</math>.<ref name=":0" /> The important implication here is that the efficiency of the algorithm used to solve a graphing problem is dependent on the type of query model used to model the graph.

=== Other Typestypes of Quantumquantum Computationalcomputational Queriesqueries ===

In the query complexity model, the input can also be given as an oracle (black box). The algorithm gets information about the input only by querying the oracle. The algorithm starts in some fixed quantum state and the state evolves as it queries the oracle.

Similar to the case of graphing problems, the quantum query complexity of a black-box problem is the smallest number of queries to the oracle that are required in order to calculate the function. This makes the quantum query complexity a lower bound on the overall time complexity of a function.

==== Grover's Algorithmalgorithm ====

An example depicting the power of quantum computing is [[Grover's algorithm]] for searching unstructured databases. The algorithm's quantum query complexity is <math display="inline">O{\left(\sqrt{N}\right)}</math>, a quadratic improvement over the best possible classical query complexity <math>O(N)</math>, which is a [[linear search]]. While Grover's algorithm is more[[Asymptotic optimizedoptimality|asymptotically thanoptimal]]; thein bestfact, possibleit classicaluses algorithm,at wemost knowa that<math>1+o(1)</math> Grover'sfraction algorithmmore isqueries notthan onethe hundredbest percentpossible optimalalgorithm.<ref>{{Cite journal|last=AmbainisZalka|first=AndrisChristof|date=October 28, 20051999-10-01|title=PolynomialGrover's degreequantum vs.searching quantumalgorithm queryis complexityoptimal|url=https://linkinghublink.elsevieraps.comorg/retrievedoi/pii10.1103/S0022000005000899PhysRevA.60.2746|journal=JournalPhysical ofReview Computer and System Sciences|language=enA|volume=7260|issue=24|pages=220–2382746–2751|doi=10.10161103/jPhysRevA.jcss60.20052746|arxiv=quant-ph/9711070|bibcode=1999PhRvA.06.00660.2746Z|vias2cid=1542077}}</ref> Optimization of a query algorithm refers to how the algorithm compares to the most efficient theoretical algorithm that solves the same problem. An algorithm is said to be [[Asymptotic optimality|asymptotically optimized]] if at worst, it performs at a constant factor worse than the most efficient possible algorithm. Note that an algorithm is still considered to be optimized if it performs worse than the most efficient possible algorithm, as long as the algorithm doesn't get exponentially worse than the most efficient possible algorithm, as the number of inputs increases.

==== Deutsch-Jozsa Algorithmalgorithm ====

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., Meaningmaking theits query complexity of the Deutsch-Jozsa algorithm is <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, but non-signaling hidden variable quantum computer 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 journal |title=Quantum Computing and Hidden Variables |last=Aaronson |first=Scott |journal=Phys. Rev. A |volume=71 |pages=032325 |date=2005 |doi=10.1103/PhysRevA.71.032325 |arxiv=quant-ph/0408035 |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>

==== 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. Meaning the query complexity of the Deutsch-Jozsa algorithm is <math>1</math>.<ref name=":32" />

==See also==

Line 137 ⟶ 141:

* {{cite book | author1-link= Michael Nielsen| author1=Nielsen, Michael |author2-link = Isaac L. Chuang |author2=Chuang, Isaac |title=Quantum Computation and Quantum Information | title-link=Quantum Computation and Quantum Information |publisher=Cambridge University Press |___location=Cambridge |year=2000 |isbn=978-0-521-63503-5 |oclc= 174527496}}

* {{cite book |last1=Arora |first1=Sanjeev|author1-link=Sanjeev Arora |last2=Barak |first2=Boaz|author2-link=Boaz Barak |title=Computational Complexity: A Modern Approach |url=https://archive.org/details/computationalcom00aror |url-access=limited |date=2016 |publisher=Cambridge University Press |isbn=978-0-521-42426-4 |pages=[https://archive.org/details/computationalcom00aror/page/n226 201]–236}}

* {{cite arXiv|eprint=0804.3401v1|author1=Watrous, John Watrous|authorlinkauthor-link=John Watrous (computer scientist)|title=Quantum Computational Complexity|class=quant-ph|year=2008}}

* Watrous J. (2009) [https://link.springer.com/referencework/10.1007/978-0-387-30440-3 Quantum Computational Complexity]. In: Meyers R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY

Line 149 ⟶ 153:

[[Category:Quantum complexity theory| ]]

[[Category:Computational complexity theory]]

[[Category:Quantum information science]]

[[Category:Theoretical computer science]]