Quantum complexity theory: Difference between revisions

Revision as of 06:24, 23 November 2020

Revision as of 06:25, 23 November 2020

Line 124:

==== 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">{{Cite book|last=Nielsen, Michael A., 1974-|url=https://www.worldcat.org/oclc/665137861|title=Quantum computation and quantum information|date=2010|publisher=Cambridge University Press|others=Chuang, Isaac L., 1968-|isbn=978-1-107-00217-3|edition=10th anniversary ed|___location=Cambridge|oclc=665137861}}</ref> 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" />

<math>1</math>.

==See also==