Home▸Quantum Computing▸Deutsch–Jozsa Algorithm — One Query Beats Classical

🧮 Deutsch–Jozsa Algorithm — One Query Beats Classical

Interactive Deutsch–Jozsa algorithm simulator: pick a constant or balanced oracle, watch the Walsh–Hadamard transform decide the answer with a single quantum query.

Quantum Computing2DAdvanced60 FPS

About the Deutsch–Jozsa Algorithm

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.

Frequently Asked Questions

What problem does the Deutsch–Jozsa algorithm solve?

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.

Why is a classical computer so much slower at this?

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.

How does a single quantum query decide the answer?

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.

What do the bar chart and the P(0…0) value mean?

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.

⚙ Under the hood

Interactive Deutsch–Jozsa algorithm simulator: pick a constant or balanced oracle, watch the Walsh–Hadamard transform decide the answer with a single quantum query.

Quantum ComputingQuantum AlgorithmCircuit DiagramCanvas 2DHadamard Transform

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install