← Quantum Store · Guides · Lessons · Glossary · About · Türkçe
What is the Deutsch–Jozsa algorithm?
The Deutsch–Jozsa algorithm is one of the first quantum algorithms: it decides with certainty, in a single query, whether a function is constant or balanced.
Published by David Deutsch and Richard Jozsa in 1992, it was one of the first examples showing that a quantum computer can solve a problem with exponentially fewer queries than a deterministic classical computer. The function is promised to be either constant or balanced; classically, in the worst case, more than half of the inputs must be queried.
The algorithm puts the inputs into superposition with H gates, applies the function as an oracle circuit and, through phase kickback, writes the phase (−1)^f(x) onto each input. After the final H gates the inputs read 00…0 with certainty for a constant function and never read 00…0 for a balanced one.
Try it yourself
The lesson Deutsch–Jozsa: a certain answer in one query lets you try this concept in the browser, with no installation.
Related packages
Related concepts
- Bernstein–Vazirani algorithm · The Bernstein–Vazirani algorithm finds the hidden bit string s inside a function f(x) = s·x in a single query, instead of the n queries needed classically.
- Quantum interference · Quantum interference is the way amplitudes add up like waves, raising the probability of some results and cancelling others to zero.
- Hadamard gate (H) · The Hadamard gate is a single-qubit quantum gate that turns a qubit in |0⟩ into an equal superposition of 0 and 1.