Quantum complexity theory: Difference between revisions

Revision as of 02:26, 2 December 2020

Revision as of 08:36, 7 December 2020

Line 121:

==== Grover's algorithm ====

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 optimized than the best possible classical algorithm, we know that Grover's algorithm is not one hundred percent optimal.<ref>{{Cite journal|last=Ambainis|first=Andris|date=October 28, 2005|title=Polynomial degree vs. quantum query complexity|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000005000899|journal=Journal of Computer and System Sciences|language=en|volume=72|issue=2|pages=220–238|doi=10.1016/j.jcss.2005.06.006}}</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 optimizedoptimal]]; ifin at worstfact, it performsuses at a constant factor worse than the most efficienta possible<math>1+o(1)</math> algorithm.fraction Note that an algorithm is still considered to be optimized if it performsmore worsequeries than the most efficientbest 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 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., Meaningmaking theits query complexity of the Deutsch-Jozsa algorithm is <math>1</math>.<ref name=":32" />

==See also==