The Deutsch–Jozsa algorithm was the first concrete example of a quantum algorithm that provably outperforms every possible classical algorithm on a black-box problem. Given a hidden function f that is promised to be either constant (same output for every input) or balanced (0 for exactly half the inputs, 1 for the other half), a classical computer may need to check more than half the inputs in the worst case, while a quantum computer settles it with a single query. It is the conceptual seed that later grew into Grover's and Shor's algorithms.
|ψ⟩ = H^⊗n|0⟩ — equal superposition of all N = 2ⁿ
inputs. U_f|x⟩ = (−1)^f(x)|x⟩ — the oracle's phase
kickback. P(y) = |⟨y|H^⊗n U_f H^⊗n|0⟩|² — probability
of measuring output y. If f is constant, P(0…0) = 1 exactly; if f
is balanced, P(0…0) = 0 exactly.
David Deutsch proposed the single-qubit version in 1985; David Deutsch and Richard Jozsa generalised it to n qubits in 1992 — nearly a decade before Peter Shor's 1994 factoring algorithm made quantum computing famous. At the time it was one of the only rigorous proofs that quantum computers could ever beat classical ones at anything.
The Deutsch–Jozsa algorithm answers a simple promise problem: given a black-box function f that maps n bits to a single bit and is guaranteed to be either constant (the same output for every input) or balanced (0 for exactly half the inputs and 1 for the other half), decide which. A classical computer that can only query f as a black box may need to check more than half of the 2ⁿ inputs before it is certain — up to 2⁽ⁿ⁻¹⁾ + 1 queries in the worst case. A quantum computer settles the same question with a single call to the oracle, by encoding f into a phase and letting interference concentrate all the probability at the all-zero outcome exactly when f is constant.
This simulator builds the exact quantum state by hand: it applies Hadamard gates to reach an equal superposition, encodes the chosen oracle as a sign flip on each basis state, then performs a genuine Walsh–Hadamard transform to obtain the final measurement probabilities. The verdict banner reads off the probability of measuring the all-zero string live — near 1 means constant, near 0 means balanced — exactly as the real algorithm works. It remains a foundational example in quantum computing courses because it was the first rigorous demonstration that quantum interference can provide an unconditional speed-up over any classical strategy, years before Shor's algorithm made the idea famous.
It decides, with certainty, whether a black-box Boolean function f is constant or balanced, using the fewest possible queries to f. The function is promised in advance to be one or the other, so the algorithm never needs to handle a function that is neither.
Classically you must query f on inputs one at a time. If you happen to get the same output 2⁽ⁿ⁻¹⁾ times in a row you still cannot be sure the function is constant — the very next query could reveal a different value. Only after checking just over half the inputs, 2⁽ⁿ⁻¹⁾ + 1 queries in the worst case, can you be certain.
Superposition lets the oracle be applied to all 2ⁿ inputs simultaneously, encoding f(x) into a phase rather than a bit flip. A second layer of Hadamard gates then interferes those phases together. If f is constant, every path adds up constructively at the all-zero outcome, giving it probability 1. If f is balanced, the paths cancel completely there, giving probability 0.
The bar chart shows the probability of measuring every possible output string. The bar at y = 0 (the all-zero string) is highlighted because it alone carries the verdict: this simulator reads that single probability live and reports CONSTANT when it is close to 1 or BALANCED when it is close to 0.