Deutsch-Jozsa Algorithm

Overview

The Deutsch-Jozsa algorithm answers a simple question about a hidden function with a single query. The function takes n bits and returns one bit, and you are promised that it is either constant (the same output for every input) or balanced (output 0 for exactly half of the inputs and 1 for the other half). A deterministic classical algorithm may need up to 2 to the n minus 1, plus 1, queries to be sure. A quantum computer needs exactly one.

The problem itself has no practical use. The algorithm matters because it was one of the first demonstrations that quantum computers can do something provably better than classical ones in the query model, and because its circuit structure, with Hadamard gates before and after an oracle, appears again in Bernstein-Vazirani, Simon's, and Shor's algorithms.

The problem it solves

Determining whether a given function is 'constant' (same output for all inputs) or 'balanced' (different outputs for half the inputs).

History and background

David Deutsch described the first quantum algorithm in 1985 in a paper that introduced the idea of a universal quantum computer. That version solved the one-bit case and succeeded only with probability one half. In 1992, Deutsch and Richard Jozsa generalized it to n bits, and the resulting speedup was exponential relative to deterministic classical algorithms.

In 1998, Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca reformulated the algorithm in the clean form used in textbooks today, which always succeeds. Small versions of the algorithm were among the first to be run on real quantum hardware, including NMR machines in 1998 and 2000 and later on superconducting and ion-trap devices. It is still a common first program used to test a new quantum chip.

How it works

Uses superposition to evaluate the function on all inputs simultaneously, then uses interference so a single measurement reveals whether the function is constant or balanced.

A quantum computer can feed a superposition of all inputs into the oracle at once. The oracle does not return the output directly. Instead it encodes each output in the phase of the corresponding input, multiplying its amplitude by plus or minus 1 depending on the function value. This trick, called phase kickback, is a core technique in quantum algorithms.

After the oracle, a second layer of Hadamard gates converts the phase pattern into measurement outcomes. If the function is constant, all amplitudes have the same sign, and the Hadamard layer interferes them all back into the all-zeros state. If the function is balanced, the positive and negative amplitudes cancel exactly at the all-zeros state, so that outcome has probability zero. A single measurement therefore tells you which case holds: all zeros means constant, anything else means balanced.

The speedup is real but limited. A randomized classical algorithm can solve the problem with a handful of queries and a tiny chance of error, which is why the advantage appears only against deterministic algorithms that must always be correct.

Step by step

1. Prepare n input qubits in the state 0 and one ancilla qubit in the state 1.
2. Apply a Hadamard gate to all n plus 1 qubits. The input register becomes an equal superposition of all 2 to the n inputs, and the ancilla becomes the minus state.
3. Apply the oracle U sub f, which maps x and y to x and y XOR f of x. Because the ancilla is in the minus state, this puts the phase minus 1 to the f of x on each input state.
4. Apply Hadamard gates to the n input qubits again.
5. Measure the n input qubits.
6. If every measured bit is 0, the function is constant. If any bit is 1, the function is balanced.

A worked example

Take n = 2 and the balanced function f of 00 = 0, f of 01 = 0, f of 10 = 1, f of 11 = 1, which depends only on the first bit. After the first Hadamards and the oracle, the phases are plus, plus, minus, minus on the four inputs. The second Hadamards turn this pattern into the state 10, because the signs vary only along the first bit. Measuring 10 is not all zeros, so the function is balanced.

Now take the constant function f of x = 0. The oracle does nothing, the two Hadamard layers cancel, and the measurement gives 00 with certainty. A classical deterministic algorithm would need three queries in the worst case to be sure for n = 2, and 2 to the n minus 1 plus 1 queries in general.

Complexity and resources

What hardware it needs

• A few qubits and a handful of gates, so it runs on any current hardware for small n.
• An oracle implementation. For a general function the oracle can be as costly as the problem it is meant to test.

Applications

• Teaching phase kickback, interference, and the query model of quantum computation.
• Benchmarking new quantum hardware as a simple, verifiable circuit.
• Serving as the blueprint for Bernstein-Vazirani, Simon's, and Shor's algorithms.

Limitations and caveats

• The promise that the function is constant or balanced is artificial and rarely arises in practice.
• The advantage disappears against randomized classical algorithms.
• The oracle cost is not counted in the query model, so a fair comparison needs care.

Common misconceptions

• It does not show that quantum computers are exponentially faster at everything. It shows an exponential gap against deterministic algorithms on a contrived problem.
• It does not evaluate the function on all inputs and read them all out. It uses interference so that one measurement reveals a global property.

How it compares

• Bernstein-Vazirani uses the same circuit but extracts a hidden bit string.
• Simon's algorithm extends the idea to a problem where even randomized classical algorithms need exponentially many queries.
• Compared with Grover's algorithm, it solves a promise problem exactly instead of searching with probability.

Real-world impact

Mainly historical and educational — it proved quantum speedup was possible in principle, paving the way for Shor's and Grover's algorithms, though the problem itself has limited practical use.

Why it matters

Deutsch-Jozsa is the first example most students meet in which a quantum computer beats a classical one in a mathematically precise way. Understanding why it works gives you the vocabulary of superposition, oracles, phase kickback, and interference that every later algorithm builds on.

It also teaches an important lesson in being careful about comparisons. The result is only an exponential speedup when you compare with the right class of classical algorithm, a habit worth keeping when reading advantage claims.

Frequently asked questions

Keep learning

• Related algorithm: Bernstein-Vazirani Algorithm
• Related algorithm: Simon's Algorithm
• Related algorithm: Quantum Fourier Transform (QFT)

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database