Editing Deutsch–Jozsa algorithm (section)

{{Short description|Deterministic quantum algorithm}}
The '''Deutsch–Jozsa algorithm''' is a [[deterministic algorithm|deterministic]] [[quantum algorithm]] proposed by [[David Deutsch]] and [[Richard Jozsa]] in 1992 with improvements by [[Richard Cleve]], [[Artur Ekert]], Chiara Macchiavello, and [[Michele Mosca]] in 1998.<ref name="DJ92">{{cite journal| author = David Deutsch| author-link = David Deutsch| author2 = Richard Jozsa| author2-link = Richard Jozsa| name-list-style = amp| title = Rapid solutions of problems by quantum computation| journal = Proceedings of the Royal Society of London A| volume = 439| issue = 1907| pages = 553–558| year = 1992|bibcode = 1992RSPSA.439..553D |doi = 10.1098/rspa.1992.0167 | citeseerx = 10.1.1.655.5997| s2cid = 121702767}}</ref><ref name="CEMM98">{{cite journal|author1=R. Cleve |author2=A. Ekert |author3=C. Macchiavello |author4=M. Mosca | title = Quantum algorithms revisited| journal = Proceedings of the Royal Society of London A| volume = 454|issue=1969 | pages = 339–354| year = 1998| arxiv = quant-ph/9708016|bibcode = 1998RSPSA.454..339C |doi = 10.1098/rspa.1998.0164 |s2cid=16128238 }}</ref> Although of little practical use, it is one of the first examples of a quantum algorithm that is [[Time complexity|exponentially faster]] than any possible deterministic classical algorithm.<ref>{{Cite book|last=Simon|first=Daniel|title=Proceedings 35th Annual Symposium on Foundations of Computer Science |chapter=On the power of quantum computation |date=November 1994|chapter-url=http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.51.5477&rep=rep1&type=pdf|pages=116–123|doi=10.1109/SFCS.1994.365701|isbn=0-8186-6580-7|s2cid=7457814}}</ref>

The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm. It is a [[black box]] problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need an exponential number of queries to the black box to solve the problem. More formally, it yields an oracle relative to which '''[[EQP (complexity)|EQP]]''', the class of problems that can be solved exactly in polynomial time on a quantum computer, and '''[[P (complexity)|P]]''' are different.<ref name="Johansson2017">
{{cite journal |author=Johansson, N. |author2=Larsson, JÅ. |year=2017 |title=Efficient classical simulation of the Deutsch–Jozsa and Simon's algorithms |journal=Quantum Inf Process (2017) |volume=16 |issue=9 |pages=233 |arxiv=1508.05027 |bibcode=2017QuIP...16..233J |doi=10.1007/s11128-017-1679-7 |s2cid=28670540}}
</ref>

Since the problem is easy to solve on a probabilistic classical computer, it does not yield an oracle separation with '''[[BPP (complexity)|BPP]]''', the class of problems that can be solved with bounded error in polynomial time on a probabilistic classical computer. [[Simon's problem]] is an example of a problem that yields an oracle separation between '''[[BQP]]''' and '''BPP'''.