The Deutsch-Jozsa Algorithm: Quantum's First Speedup Explained

What Problem Does It Solve?

Imagine someone hands you a black-box function f(x) that takes an n-bit string and returns either 0 or 1. You are told that the function is either constant (returns the same value for every input) or balanced (returns 0 for exactly half the inputs and 1 for the other half). Your task is to determine which one it is.

This is the Deutsch-Jozsa problem. In the real world you might not care about black-box functions, but this problem is a clean, provable example where a quantum computer wins decisively over any possible classical approach.

Classical Worst Case

Classically you have to call the function and check outputs. In the best case you get lucky: two different outputs on the first two queries and you immediately know the function is balanced. But luck is not an algorithm.

In the worst case you could query 2^(n-1) inputs and get the same answer every time. You still would not know whether you are seeing a constant function or a very unlucky balanced one. Only on query number 2^(n-1) + 1 can you be certain. For n = 50 that is over a quadrillion queries.

A deterministic classical algorithm requires 2^(n-1) + 1 queries in the worst case. There is no classical shortcut.

Classical Randomized Algorithm

Before jumping to the quantum solution, it is worth noting that a randomized classical algorithm performs much better than the deterministic worst case.

The strategy is simple. Query k random inputs. If you ever see two different outputs, the function is balanced. If all k queries return the same value, guess constant.

If the function is truly constant, you always guess correctly, so the error probability is zero for constant functions. If the function is balanced, the only way to get it wrong is to see k identical outputs. Since exactly half the inputs return 0 and half return 1, the probability of picking k inputs that all return the same value is 2 * (1/2)^k = 1/2^(k-1).

Queries (k)	Error probability
1	1
2	1/2
5	1/16
10	~1/512
20	~1/524,288
30	~1/536,870,912

With 30 queries, the error probability is below one in a billion. This is extraordinarily reliable.

So does this undermine the significance of Deutsch-Jozsa? No, but it does sharpen what the algorithm actually proves. The quantum advantage is exact: one query, zero error. The classical randomized algorithm achieves low error with a constant number of queries, so the quantum advantage is not exponential in a practical sense against a randomized adversary. However, in the query complexity model, the separation between deterministic classical (exponential queries) and quantum (one query) is rigorous and unconditional. The algorithm is a proof of principle, not a practical tool, and its importance lies in introducing the techniques that power every subsequent quantum algorithm.

Quantum Solution: One Query

The Deutsch-Jozsa algorithm answers the question with exactly one call to the oracle, regardless of n. This is not a probabilistic speedup with some chance of being wrong. It is deterministic and exact.

The key is that a quantum computer can query the oracle on a superposition of all 2^n inputs simultaneously, and the structure of the problem (constant vs. balanced) is encoded globally in the phase of the resulting state. Measurement then extracts that global information in one shot.

Circuit Overview

The algorithm uses n input qubits and one ancilla qubit. The steps are:

1. Initialize input qubits to |0⟩ and ancilla to |1⟩.
2. Apply Hadamard to every qubit. The input register is now in uniform superposition over all 2^n inputs; the ancilla is in the |−⟩ state.
3. Apply the oracle U_f, which flips the ancilla conditioned on f(x) = 1. Because the ancilla is |−⟩, this operation writes the phase (-1)^f(x) onto each input basis state (this is called phase kickback).
4. Apply Hadamard again to the input register.
5. Measure the input register. All zeros means constant; anything else means balanced.

Phase Kickback: Full Derivation

Phase kickback is the engine of the entire algorithm. Let us derive it step by step.

The oracle U_f acts on an input register |x⟩ and a single ancilla qubit |y⟩ as:

U_f |x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩

Here ⊕ denotes addition modulo 2 (XOR). The oracle leaves the input register unchanged and flips the ancilla if f(x) = 1.

Now suppose the ancilla is prepared in the |−⟩ state:

|−⟩ = (|0⟩ - |1⟩) / √2

Apply U_f to the joint state |x⟩|−⟩:

U_f |x⟩|−⟩ = U_f |x⟩ ⊗ (|0⟩ - |1⟩)/√2
            = (U_f |x⟩|0⟩ - U_f |x⟩|1⟩) / √2
            = (|x⟩|0 ⊕ f(x)⟩ - |x⟩|1 ⊕ f(x)⟩) / √2
            = |x⟩ ⊗ (|0 ⊕ f(x)⟩ - |1 ⊕ f(x)⟩) / √2

Now consider the two cases separately.

Case f(x) = 0:

|0 ⊕ 0⟩ - |1 ⊕ 0⟩ = |0⟩ - |1⟩

So the state is |x⟩ ⊗ (|0⟩ - |1⟩)/√2 = (+1) |x⟩|−⟩.

Case f(x) = 1:

|0 ⊕ 1⟩ - |1 ⊕ 1⟩ = |1⟩ - |0⟩ = -(|0⟩ - |1⟩)

So the state is |x⟩ ⊗ (-(|0⟩ - |1⟩))/√2 = (-1) |x⟩|−⟩.

Combining both cases:

U_f |x⟩|−⟩ = (-1)^f(x) |x⟩|−⟩

The ancilla is completely unchanged. It returns to |−⟩ regardless of f(x). The effect of the oracle is to attach the phase factor (-1)^f(x) to the input register. This is phase kickback: the information about f(x) is “kicked back” from the ancilla onto the phase of the input state.

Because the ancilla is untouched, it is effectively a catalyst. It enables the phase transfer but carries no information itself after the oracle acts.

Why Interference Makes This Work

After step 2 the state is:

|ψ⟩ = (1/√(2^n)) Σ_x |x⟩ ⊗ |−⟩

After the oracle the phase (-1)^f(x) is attached to each |x⟩:

|ψ'⟩ = (1/√(2^n)) Σ_x (-1)^f(x) |x⟩ ⊗ |−⟩

After the second Hadamard on the input register, the amplitude for the all-zeros outcome |0...0⟩ is:

⟨0...0| H^⊗n |ψ'⟩ = (1/2^n) Σ_x (-1)^f(x)

If f is constant, every term has the same sign and the sum is +1 or -1. The probability of measuring all zeros is |±1|^2 = 1. Measurement of all zeros is certain.

If f is balanced, exactly half the terms are +1 and half are -1. The sum is zero. The probability of measuring all zeros is |0|^2 = 0. Measurement of all zeros is impossible. The amplitude goes entirely into non-zero strings.

This is quantum interference: phases cancel out the all-zeros outcome when the function is balanced, and reinforce it when constant.

Full State Evolution for n=2

Let us trace every step of the algorithm with n = 2 input qubits.

After initialization (Step 1)

|ψ_0⟩ = |00⟩ ⊗ |1⟩

After Hadamard on all qubits (Step 2)

Applying H ⊗ H to the input register gives (|00⟩ + |01⟩ + |10⟩ + |11⟩)/2. Applying H to the ancilla |1⟩ gives |−⟩ = (|0⟩ - |1⟩)/√2.

|ψ_1⟩ = (1/2)(|00⟩ + |01⟩ + |10⟩ + |11⟩) ⊗ |−⟩

After oracle (Step 3)

Phase kickback gives (-1)^f(x) on each basis state. The ancilla remains |−⟩.

Constant_0: f(x) = 0 for all x, so (-1)^0 = 1 everywhere.

|ψ_2⟩ = (1/2)(|00⟩ + |01⟩ + |10⟩ + |11⟩) ⊗ |−⟩

Constant_1: f(x) = 1 for all x, so (-1)^1 = -1 everywhere.

|ψ_2⟩ = (1/2)(−|00⟩ − |01⟩ − |10⟩ − |11⟩) ⊗ |−⟩
       = −(1/2)(|00⟩ + |01⟩ + |10⟩ + |11⟩) ⊗ |−⟩

The global phase of -1 is physically unobservable, so this state is equivalent to the constant_0 case.

Balanced (parity oracle): f(x) = x_0 ⊕ x_1, so f(00) = 0, f(01) = 1, f(10) = 1, f(11) = 0.

|ψ_2⟩ = (1/2)(|00⟩ − |01⟩ − |10⟩ + |11⟩) ⊗ |−⟩

After second Hadamard on input register (Step 4)

We need the Hadamard transform H^⊗2 acting on the input register. Recall that for two qubits:

H^⊗2 |00⟩ = (1/2)(|00⟩ + |01⟩ + |10⟩ + |11⟩)
H^⊗2 |01⟩ = (1/2)(|00⟩ − |01⟩ + |10⟩ − |11⟩)
H^⊗2 |10⟩ = (1/2)(|00⟩ + |01⟩ − |10⟩ − |11⟩)
H^⊗2 |11⟩ = (1/2)(|00⟩ − |01⟩ − |10⟩ + |11⟩)

Constant_0 and Constant_1: The input state before H^⊗2 is (|00⟩ + |01⟩ + |10⟩ + |11⟩)/2. Applying H^⊗2:

(1/2) * (1/2)[(|00⟩+|01⟩+|10⟩+|11⟩) + (|00⟩−|01⟩+|10⟩−|11⟩)
             + (|00⟩+|01⟩−|10⟩−|11⟩) + (|00⟩−|01⟩−|10⟩+|11⟩)]
= (1/4)[4|00⟩] = |00⟩

Result: |00⟩ ⊗ |−⟩. Measurement yields 00 with probability 1.

Balanced (parity): The input state before H^⊗2 is (|00⟩ − |01⟩ − |10⟩ + |11⟩)/2. Applying H^⊗2:

(1/2) * (1/2)[(|00⟩+|01⟩+|10⟩+|11⟩) − (|00⟩−|01⟩+|10⟩−|11⟩)
             − (|00⟩+|01⟩−|10⟩−|11⟩) + (|00⟩−|01⟩−|10⟩+|11⟩)]
= (1/4)[0|00⟩ + 0|01⟩ + 0|10⟩ + 4|11⟩] = |11⟩

Result: |11⟩ ⊗ |−⟩. Measurement yields 11 with probability 1.

Summary table

Step	Constant_0	Constant_1	Balanced (parity)
Init	|00⟩|1⟩	|00⟩|1⟩	|00⟩|1⟩
After H	(1/2)(Σ|x⟩)|−⟩	(1/2)(Σ|x⟩)|−⟩	(1/2)(Σ|x⟩)|−⟩
After oracle	(1/2)(Σ|x⟩)|−⟩	-(1/2)(Σ|x⟩)|−⟩	(1/2)(|00⟩-|01⟩-|10⟩+|11⟩)|−⟩
After H^⊗2	|00⟩|−⟩	-|00⟩|−⟩	|11⟩|−⟩
Measurement	00 (prob 1)	00 (prob 1)	11 (prob 1)
Verdict	CONSTANT	CONSTANT	BALANCED

Oracle Construction in Qiskit

A constant-0 oracle does nothing (identity). A constant-1 oracle applies an X gate to the ancilla. A balanced oracle applies CNOT gates from selected input qubits to the ancilla, which flips the ancilla for exactly half the inputs.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
import numpy as np

def deutsch_jozsa(n: int, oracle_type: str = "balanced") -> QuantumCircuit:
    """
    Build the Deutsch-Jozsa circuit.

    Args:
        n: Number of input qubits.
        oracle_type: 'constant_0', 'constant_1', or 'balanced'.

    Returns:
        QuantumCircuit with measurement results.
    """
    input_qubits = QuantumRegister(n, name="x")
    ancilla = QuantumRegister(1, name="anc")
    cr = ClassicalRegister(n, name="c")
    qc = QuantumCircuit(input_qubits, ancilla, cr)

    # Step 1: Initialize ancilla to |1>
    qc.x(ancilla[0])

    # Step 2: Hadamard on all qubits
    qc.h(input_qubits)
    qc.h(ancilla[0])
    qc.barrier()

    # Step 3: Oracle
    if oracle_type == "constant_0":
        pass  # Identity oracle, f(x) = 0 always
    elif oracle_type == "constant_1":
        qc.x(ancilla[0])  # f(x) = 1 always, flip ancilla unconditionally
    elif oracle_type == "balanced":
        # CNOT from all input qubits implements the parity function
        # f(x) = x_0 XOR x_1 XOR ... XOR x_{n-1}, which is balanced.
        for qubit in input_qubits:
            qc.cx(qubit, ancilla[0])
    else:
        raise ValueError(f"Unknown oracle type: {oracle_type}")

    qc.barrier()

    # Step 4: Hadamard on input register
    qc.h(input_qubits)

    # Step 5: Measure input register
    qc.measure(input_qubits, cr)

    return qc


def run_deutsch_jozsa(n: int = 3):
    simulator = AerSimulator()

    for oracle in ["constant_0", "constant_1", "balanced"]:
        qc = deutsch_jozsa(n, oracle)
        job = simulator.run(qc, shots=1024)
        counts = job.result().get_counts()

        all_zeros = "0" * n
        if all_zeros in counts and counts[all_zeros] == 1024:
            verdict = "CONSTANT"
        else:
            verdict = "BALANCED"

        print(f"Oracle: {oracle:12s} | Measurement counts: {counts} | Verdict: {verdict}")


if __name__ == "__main__":
    run_deutsch_jozsa(n=3)

Running this should produce output like:

Oracle: constant_0   | Measurement counts: {'000': 1024} | Verdict: CONSTANT
Oracle: constant_1   | Measurement counts: {'000': 1024} | Verdict: CONSTANT
Oracle: balanced     | Measurement counts: {'111': 1024} | Verdict: BALANCED

For the balanced parity oracle, the measurement always returns all ones. The next section explains why.

Measurement Outcome Analysis: Why the Parity Oracle Gives All Ones

When the balanced oracle implements f(x) = x_0 ⊕ x_1 ⊕ ... ⊕ x_{n-1} (the parity function, built from CNOT gates from every input qubit), the specific output after the second Hadamard layer is always |1...1⟩. Here is why.

After phase kickback, the input register is in the state:

(1/√(2^n)) Σ_x (-1)^(x_0 ⊕ x_1 ⊕ ... ⊕ x_{n-1}) |x⟩

The parity function x_0 ⊕ x_1 ⊕ ... ⊕ x_{n-1} equals the sum of the bits modulo 2. So (-1)^(x_0 ⊕ ... ⊕ x_{n-1}) equals the product (-1)^{x_0} * (-1)^{x_1} * ... * (-1)^{x_{n-1}}. This means the state factors as a tensor product:

(1/√(2^n)) Σ_x (-1)^{x_0} ... (-1)^{x_{n-1}} |x_0 ... x_{n-1}⟩
= [(|0⟩ - |1⟩)/√2] ⊗ [(|0⟩ - |1⟩)/√2] ⊗ ... ⊗ [(|0⟩ - |1⟩)/√2]
= |−⟩^⊗n

Each qubit is independently in the |−⟩ state. Now applying H to each qubit:

H|−⟩ = H(|0⟩ - |1⟩)/√2 = |1⟩

So H^⊗n |−⟩^⊗n = |1⟩^⊗n = |1...1⟩.

The measurement outcome is deterministically 1...1, not just “something other than 0...0”.

Here is code that verifies this for n = 2, 3, and 4:

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator

def verify_parity_outcome(n_values: list[int]):
    """Verify that the parity oracle always produces the all-ones outcome."""
    simulator = AerSimulator()

    for n in n_values:
        input_qubits = QuantumRegister(n, name="x")
        ancilla = QuantumRegister(1, name="anc")
        cr = ClassicalRegister(n, name="c")
        qc = QuantumCircuit(input_qubits, ancilla, cr)

        # Initialize
        qc.x(ancilla[0])
        qc.h(input_qubits)
        qc.h(ancilla[0])

        # Parity oracle: CNOT from every input qubit to ancilla
        for qubit in input_qubits:
            qc.cx(qubit, ancilla[0])

        # Final Hadamard and measure
        qc.h(input_qubits)
        qc.measure(input_qubits, cr)

        job = simulator.run(qc, shots=1024)
        counts = job.result().get_counts()

        expected = "1" * n
        print(f"n={n}: counts = {counts}, expected = {expected}, "
              f"match = {expected in counts and counts[expected] == 1024}")


if __name__ == "__main__":
    verify_parity_outcome([2, 3, 4])

Expected output:

n=2: counts = {'11': 1024}, expected = 11, match = True
n=3: counts = {'111': 1024}, expected = 111, match = True
n=4: counts = {'1111': 1024}, expected = 1111, match = True

Multiple Balanced Oracles

The parity oracle (CNOT from all input qubits) is just one of many balanced functions. Any function that returns 0 for exactly half of its inputs and 1 for the other half is valid. Different balanced oracles produce different non-zero measurement outcomes, but they all correctly give a verdict of BALANCED (never all zeros).

Approach 1: CNOT from a subset of input qubits

If you CNOT from only a single input qubit x_k to the ancilla, the oracle computes f(x) = x_k. This is balanced because exactly half the n-bit strings have x_k = 0 and half have x_k = 1.

Approach 2: CNOT with X gates to flip trigger conditions

Start with a CNOT from qubit x_k. If you place an X gate on x_k before the CNOT (and another X after to uncompute), the oracle computes f(x) = NOT(x_k) = 1 - x_k. This is still balanced, just with the roles of 0 and 1 swapped for that qubit.

More generally, you can combine CNOTs from multiple qubits with X gates on selected qubits before and after the CNOT block. This produces f(x) = (x_0 ⊕ s_0) ⊕ (x_1 ⊕ s_1) ⊕ ... for some bit string s, where you only include the qubits you choose.

Code: three different balanced oracles

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator

def build_oracle_a(qc, input_qubits, ancilla):
    """Balanced oracle A: f(x) = x_0 (CNOT from first qubit only)."""
    qc.cx(input_qubits[0], ancilla[0])

def build_oracle_b(qc, input_qubits, ancilla):
    """Balanced oracle B: f(x) = x_0 XOR x_1 (CNOT from first two qubits)."""
    qc.cx(input_qubits[0], ancilla[0])
    qc.cx(input_qubits[1], ancilla[0])

def build_oracle_c(qc, input_qubits, ancilla):
    """Balanced oracle C: f(x) = NOT(x_0) XOR x_2 (X gates + CNOTs)."""
    # X on qubit 0 before CNOT flips the condition
    qc.x(input_qubits[0])
    qc.cx(input_qubits[0], ancilla[0])
    qc.cx(input_qubits[2], ancilla[0])
    qc.x(input_qubits[0])  # Uncompute X on qubit 0

def run_multiple_oracles():
    n = 3
    simulator = AerSimulator()

    oracles = {
        "A: f(x) = x_0":              build_oracle_a,
        "B: f(x) = x_0 XOR x_1":      build_oracle_b,
        "C: f(x) = NOT(x_0) XOR x_2": build_oracle_c,
    }

    for name, oracle_fn in oracles.items():
        input_qubits = QuantumRegister(n, name="x")
        ancilla = QuantumRegister(1, name="anc")
        cr = ClassicalRegister(n, name="c")
        qc = QuantumCircuit(input_qubits, ancilla, cr)

        # Deutsch-Jozsa setup
        qc.x(ancilla[0])
        qc.h(input_qubits)
        qc.h(ancilla[0])
        qc.barrier()

        # Apply the oracle
        oracle_fn(qc, input_qubits, ancilla)

        qc.barrier()
        qc.h(input_qubits)
        qc.measure(input_qubits, cr)

        job = simulator.run(qc, shots=1024)
        counts = job.result().get_counts()

        all_zeros = "0" * n
        is_all_zeros = (all_zeros in counts and counts[all_zeros] == 1024)
        verdict = "CONSTANT" if is_all_zeros else "BALANCED"

        print(f"Oracle {name:30s} | Result: {counts} | Verdict: {verdict}")


if __name__ == "__main__":
    run_multiple_oracles()

Expected output:

Oracle A: f(x) = x_0               | Result: {'001': 1024} | Verdict: BALANCED
Oracle B: f(x) = x_0 XOR x_1       | Result: {'011': 1024} | Verdict: BALANCED
Oracle C: f(x) = NOT(x_0) XOR x_2  | Result: {'101': 1024} | Verdict: BALANCED

All three return BALANCED, as they must. The specific measurement outcome differs for each oracle, but none of them produce all zeros.

Randomized Balanced Oracle

In a real experiment, you want to test the algorithm against oracles you did not hand-design. Here is how to construct a random balanced oracle.

Choose a random n-bit string s. Before the CNOT block, apply X gates to the input qubits where s_i = 1. Then apply a CNOT from one specific input qubit to the ancilla. Then uncompute the X gates. The X gates flip which inputs trigger the CNOT, producing a different balanced function for each choice of s.

For even more variety, you can CNOT from multiple qubits with different flip patterns. The following code generates a random s and builds the oracle:

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
import numpy as np

def random_balanced_oracle(n: int, seed: int = None) -> tuple[QuantumCircuit, str]:
    """
    Build a Deutsch-Jozsa circuit with a random balanced oracle.

    The oracle is f(x) = (x_0 XOR s_0) XOR (x_1 XOR s_1) XOR ... XOR (x_{n-1} XOR s_{n-1})
    for a random bit string s. This produces 2^n distinct balanced functions.

    Returns:
        (circuit, s_string) where s_string is the random bit string used.
    """
    rng = np.random.default_rng(seed)
    s = rng.integers(0, 2, size=n)
    s_string = "".join(str(b) for b in s)

    input_qubits = QuantumRegister(n, name="x")
    ancilla = QuantumRegister(1, name="anc")
    cr = ClassicalRegister(n, name="c")
    qc = QuantumCircuit(input_qubits, ancilla, cr)

    # Deutsch-Jozsa setup
    qc.x(ancilla[0])
    qc.h(input_qubits)
    qc.h(ancilla[0])
    qc.barrier()

    # Oracle: apply X where s_i = 1
    for i in range(n):
        if s[i] == 1:
            qc.x(input_qubits[i])

    # CNOT from all input qubits
    for qubit in input_qubits:
        qc.cx(qubit, ancilla[0])

    # Uncompute X gates
    for i in range(n):
        if s[i] == 1:
            qc.x(input_qubits[i])

    qc.barrier()

    # Final Hadamard and measurement
    qc.h(input_qubits)
    qc.measure(input_qubits, cr)

    return qc, s_string


def test_random_oracles(n: int = 3, num_trials: int = 5):
    simulator = AerSimulator()

    for trial in range(num_trials):
        qc, s = random_balanced_oracle(n, seed=trial)
        job = simulator.run(qc, shots=1024)
        counts = job.result().get_counts()

        all_zeros = "0" * n
        verdict = "CONSTANT" if (all_zeros in counts and counts[all_zeros] == 1024) else "BALANCED"
        print(f"Trial {trial}: s = {s} | Result: {counts} | Verdict: {verdict}")


if __name__ == "__main__":
    test_random_oracles()

Every trial should produce a verdict of BALANCED, regardless of the random string s.

Circuit Diagram for n=3

Let us print the actual circuit diagrams for n = 3 with each oracle type.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister

def print_circuits(n: int = 3):
    for oracle_type in ["constant_0", "constant_1", "balanced"]:
        input_qubits = QuantumRegister(n, name="x")
        ancilla = QuantumRegister(1, name="anc")
        cr = ClassicalRegister(n, name="c")
        qc = QuantumCircuit(input_qubits, ancilla, cr)

        qc.x(ancilla[0])
        qc.h(input_qubits)
        qc.h(ancilla[0])
        qc.barrier()

        if oracle_type == "constant_0":
            pass
        elif oracle_type == "constant_1":
            qc.x(ancilla[0])
        elif oracle_type == "balanced":
            for qubit in input_qubits:
                qc.cx(qubit, ancilla[0])

        qc.barrier()
        qc.h(input_qubits)
        qc.measure(input_qubits, cr)

        print(f"\n=== Oracle: {oracle_type} ===")
        print(qc.draw(output="text"))


if __name__ == "__main__":
    print_circuits()

The balanced oracle diagram for n=3 looks like:

       ┌───┐      ░            ░ ┌───┐┌─┐
  x_0: ┤ H ├──────░───■────────░─┤ H ├┤M├──────
       ├───┤      ░   │        ░ ├───┤└╥┘┌─┐
  x_1: ┤ H ├──────░───┼───■────░─┤ H ├─╫─┤M├───
       ├───┤      ░   │   │    ░ ├───┤ ║ └╥┘┌─┐
  x_2: ┤ H ├──────░───┼───┼──■─░─┤ H ├─╫──╫─┤M├
       ├───┤┌───┐ ░ ┌─┴─┐ │  │ ░ └───┘ ║  ║ └╥┘
anc_0: ┤ X ├┤ H ├─░─┤ X ├─┴──┴─░───────╫──╫──╫─
       └───┘└───┘ ░ └───┘      ░        ║  ║  ║
  c: 3/══════════════════════════════════╩══╩══╩═
                                         0  1  2

Reading the diagram from left to right:

1. Ancilla preparation: The ancilla qubit (anc_0) receives an X gate (to flip it to |1⟩) followed by an H gate (to create |−⟩).
2. Input superposition: Each input qubit (x_0, x_1, x_2) receives an H gate, creating a uniform superposition over all 8 three-bit strings.
3. Barrier: The vertical dashed line separates the preparation stage from the oracle.
4. Oracle section: Three CNOT gates, each controlled by one input qubit and targeting the ancilla. This implements the parity function f(x) = x_0 ⊕ x_1 ⊕ x_2.
5. Second barrier: Separates the oracle from the readout stage.
6. Final Hadamard layer: H gates on all input qubits to extract the phase information.
7. Measurement: Each input qubit is measured into a classical bit.

The n=1 Case: Original Deutsch’s Algorithm

When n = 1 this reduces to the original Deutsch algorithm from 1985, the very first quantum algorithm to show any speedup. The single-qubit version has two possible constant functions (f(0) = f(1) = 0 and f(0) = f(1) = 1) and two possible balanced functions (f(0) = 0, f(1) = 1 and f(0) = 1, f(1) = 0). Classically, determining which type requires two queries. Deutsch’s algorithm needs one.

The Deutsch-Jozsa generalization to n qubits (by Deutsch, Jozsa, Cleve, Ekert, and Macchiavello) made the exponential gap explicit. It was published in 1992 and set the stage for Simon’s algorithm and eventually Shor’s.

Bernstein-Vazirani: Reading a Hidden String

The Bernstein-Vazirani problem is a natural extension of Deutsch-Jozsa. Given an oracle for f(x) = s · x mod 2 (the bitwise inner product of x with a hidden string s), find s using as few queries as possible.

Classically, you need n queries: set x = 00...01 to learn s_0, then x = 00...10 to learn s_1, and so on, querying each standard basis vector.

The quantum algorithm finds s in a single query, using exactly the same circuit as Deutsch-Jozsa. The reason is striking: the oracle for f(x) = s · x is equivalent to a set of CNOT gates from input qubits x_i to the ancilla wherever s_i = 1. After phase kickback and the second Hadamard layer, the measurement outcome directly encodes s.

Here is the proof. After phase kickback, the state of the input register is:

(1/√(2^n)) Σ_x (-1)^{s · x} |x⟩

This is exactly H^⊗n |s⟩, because:

H^⊗n |s⟩ = (1/√(2^n)) Σ_x (-1)^{s · x} |x⟩

Applying H^⊗n again gives H^⊗n H^⊗n |s⟩ = |s⟩. So the measurement outcome is s with certainty.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator

def bernstein_vazirani(hidden_string: str) -> QuantumCircuit:
    """
    Build a Bernstein-Vazirani circuit that recovers the hidden string s.

    The oracle computes f(x) = s · x mod 2 (bitwise inner product).
    The circuit is identical to Deutsch-Jozsa: H, oracle, H, measure.

    Args:
        hidden_string: The secret bit string, e.g. '1011'.

    Returns:
        QuantumCircuit that, when run, measures the hidden string.
    """
    n = len(hidden_string)
    input_qubits = QuantumRegister(n, name="x")
    ancilla = QuantumRegister(1, name="anc")
    cr = ClassicalRegister(n, name="c")
    qc = QuantumCircuit(input_qubits, ancilla, cr)

    # Prepare ancilla in |->
    qc.x(ancilla[0])
    qc.h(input_qubits)
    qc.h(ancilla[0])
    qc.barrier()

    # Oracle: CNOT from qubit i to ancilla wherever s_i = 1
    # Qiskit uses little-endian ordering, so input_qubits[0] is the
    # least significant bit. We reverse the string so that
    # hidden_string[0] corresponds to the most significant qubit.
    for i, bit in enumerate(reversed(hidden_string)):
        if bit == "1":
            qc.cx(input_qubits[i], ancilla[0])

    qc.barrier()

    # Final Hadamard and measurement
    qc.h(input_qubits)
    qc.measure(input_qubits, cr)

    return qc


def test_bernstein_vazirani():
    simulator = AerSimulator()
    test_strings = ["101", "1101", "0110", "11111"]

    for s in test_strings:
        qc = bernstein_vazirani(s)
        job = simulator.run(qc, shots=1024)
        counts = job.result().get_counts()
        measured = max(counts, key=counts.get)
        print(f"Hidden string: {s} | Measured: {measured} | "
              f"Correct: {measured == s}")


if __name__ == "__main__":
    test_bernstein_vazirani()

Expected output:

Hidden string: 101 | Measured: 101 | Correct: True
Hidden string: 1101 | Measured: 1101 | Correct: True
Hidden string: 0110 | Measured: 0110 | Correct: True
Hidden string: 11111 | Measured: 11111 | Correct: True

Bernstein-Vazirani achieves an n vs. 1 query separation over classical algorithms. It demonstrates the same principle as Deutsch-Jozsa (superposition, phase kickback, interference) applied to a problem with richer structure.

Simon’s Algorithm: A Preview

Simon’s problem is the next level of difficulty. You are given an oracle for a function f: {0,1}^n -> {0,1}^n that is either one-to-one or two-to-one with a hidden period s. The promise is that f(x) = f(y) if and only if x = y or x = y ⊕ s. Your task is to find s.

Classically, finding s requires O(2^{n/2}) queries (by a birthday-paradox argument). The quantum algorithm finds s with O(n) queries.

Simon’s algorithm uses the same superposition-and-interference framework as Deutsch-Jozsa but adds classical post-processing. Each run of the quantum circuit produces a random string z satisfying z · s = 0 mod 2. After collecting n - 1 linearly independent such strings, you solve a system of linear equations to recover s.

Here is a Simon oracle for s = 110 (a 3-bit period). The oracle maps f(x) = f(x ⊕ 110). One concrete implementation: copy the input to the output register, then XOR the output with s conditioned on the first bit of the input.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator

def simon_circuit(s: str) -> QuantumCircuit:
    """
    Build one round of Simon's algorithm for hidden period s.

    This produces a random string z satisfying z · s = 0 mod 2.
    Multiple rounds and classical post-processing are needed to recover s.

    Args:
        s: The hidden period bit string, e.g. '110'.

    Returns:
        QuantumCircuit for one round of Simon's algorithm.
    """
    n = len(s)
    input_qubits = QuantumRegister(n, name="in")
    output_qubits = QuantumRegister(n, name="out")
    cr = ClassicalRegister(n, name="c")
    qc = QuantumCircuit(input_qubits, output_qubits, cr)

    # Hadamard on input register
    qc.h(input_qubits)
    qc.barrier()

    # Oracle: first copy input to output (CNOT from in_i to out_i)
    for i in range(n):
        qc.cx(input_qubits[i], output_qubits[i])

    # Then XOR output with s, conditioned on input qubit 0.
    # This ensures f(x) = f(x XOR s) for any x.
    for i, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(input_qubits[0], output_qubits[i])

    qc.barrier()

    # Hadamard on input register and measure
    qc.h(input_qubits)
    qc.measure(input_qubits, cr)

    return qc


def run_simon_rounds(s: str = "110", num_rounds: int = 10):
    """Run several rounds of Simon's algorithm and collect results."""
    simulator = AerSimulator()

    print(f"Simon's algorithm for hidden period s = {s}")
    print(f"Any measured z must satisfy z · s = 0 mod 2\n")

    qc = simon_circuit(s)
    job = simulator.run(qc, shots=num_rounds)
    counts = job.result().get_counts()

    n = len(s)
    for z, count in sorted(counts.items()):
        # Verify z · s = 0 mod 2
        dot_product = sum(int(z[i]) * int(s[i]) for i in range(n)) % 2
        print(f"  z = {z}  (count: {count})  z · s mod 2 = {dot_product}")


if __name__ == "__main__":
    run_simon_rounds()

Every measured string z satisfies z · s = 0 mod 2. For s = 110, the valid outputs are z such that z_0 * 1 + z_1 * 1 + z_2 * 0 = 0 mod 2, meaning z_0 = z_1. The possible outcomes are 000, 001, 110, and 111.

Simon’s algorithm matters historically because Peter Shor saw it in 1994 and realized a similar structure could be used for factoring, leading to Shor’s algorithm. The line from Deutsch-Jozsa to Simon to Shor is the intellectual backbone of quantum computing.

Noise Sensitivity Analysis

On real hardware, gates are imperfect. Depolarizing noise randomly applies Pauli errors after each gate operation. For the Deutsch-Jozsa algorithm with a constant oracle, the ideal outcome is all zeros with probability 1. Under noise, this probability degrades.

The following code simulates the algorithm under depolarizing noise for n = 3 at various noise rates:

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel, depolarizing_error

def noise_analysis(n: int = 3, shots: int = 10000):
    """
    Measure the probability of getting all-zeros for the constant_0 oracle
    under depolarizing noise at various error rates.
    """
    noise_rates = [0.0, 0.001, 0.005, 0.01, 0.02, 0.05, 0.1]

    print(f"Deutsch-Jozsa noise analysis (n={n}, constant_0 oracle)")
    print(f"{'Noise rate p':>14s} | {'P(all zeros)':>14s} | {'Correct?':>10s}")
    print("-" * 46)

    for p in noise_rates:
        # Build the circuit
        input_qubits = QuantumRegister(n, name="x")
        ancilla = QuantumRegister(1, name="anc")
        cr = ClassicalRegister(n, name="c")
        qc = QuantumCircuit(input_qubits, ancilla, cr)

        qc.x(ancilla[0])
        qc.h(input_qubits)
        qc.h(ancilla[0])
        qc.barrier()
        # constant_0 oracle: identity
        qc.barrier()
        qc.h(input_qubits)
        qc.measure(input_qubits, cr)

        if p == 0.0:
            # Ideal simulation
            simulator = AerSimulator()
        else:
            # Build noise model: depolarizing error on every single-qubit
            # and two-qubit gate
            noise_model = NoiseModel()
            error_1q = depolarizing_error(p, 1)
            error_2q = depolarizing_error(p, 2)
            noise_model.add_all_qubit_quantum_error(error_1q, ["h", "x"])
            noise_model.add_all_qubit_quantum_error(error_2q, ["cx"])
            simulator = AerSimulator(noise_model=noise_model)

        job = simulator.run(qc, shots=shots)
        counts = job.result().get_counts()

        all_zeros = "0" * n
        prob_all_zeros = counts.get(all_zeros, 0) / shots

        print(f"{p:14.4f} | {prob_all_zeros:14.4f} | "
              f"{'YES' if prob_all_zeros > 0.5 else 'NO':>10s}")


if __name__ == "__main__":
    noise_analysis()

Typical output (exact numbers depend on shot noise):

Deutsch-Jozsa noise analysis (n=3, constant_0 oracle)
    Noise rate p |   P(all zeros) |   Correct?
----------------------------------------------
          0.0000 |         1.0000 |        YES
          0.0010 |         0.9940 |        YES
          0.0050 |         0.9700 |        YES
          0.0100 |         0.9400 |        YES
          0.0200 |         0.8800 |        YES
          0.0500 |         0.7200 |        YES
          0.1000 |         0.5000 |         NO

The algorithm degrades gracefully. At p = 0.01 (typical for current superconducting hardware), the all-zeros probability is still around 94% for n = 3. The circuit is shallow (only two layers of Hadamard and one oracle layer), which makes it relatively noise-tolerant compared to deeper algorithms. As n increases, there are more gates and the fidelity drops faster, but for small n the algorithm remains practical on current devices.

Historical Context and Significance

The intellectual lineage of quantum algorithms follows a clear progression:

1985, Deutsch: David Deutsch posed the question of whether quantum mechanics could provide computational advantages. He constructed a single-qubit problem (now called Deutsch’s problem) where a quantum computer needs one query instead of two. This was the first formal demonstration that quantum interference could be computationally useful.

1992, Deutsch-Jozsa: Deutsch and Jozsa, with later improvements by Cleve, Ekert, and Macchiavello, generalized the problem to n qubits. The result was an exponential separation: 1 quantum query versus 2^(n-1) + 1 deterministic classical queries. This was the first exponential quantum speedup, albeit for a problem with a promise.

1994, Simon: Daniel Simon constructed a problem (finding a hidden period of a two-to-one function) with an exponential quantum speedup even against randomized classical algorithms. This was crucial because it closed the loophole that a randomized classical algorithm could nearly match Deutsch-Jozsa’s performance.

1994, Shor: Peter Shor, directly inspired by Simon’s algorithm, showed that integer factoring and discrete logarithm could be solved in polynomial time on a quantum computer. Shor’s insight was to reformulate factoring as a period-finding problem and adapt Simon’s quantum approach. This is the result that launched quantum computing as a major research field.

The key conceptual contribution of Deutsch-Jozsa is the introduction of interference-based computing. The algorithm showed that you could encode a global property of a function (constant vs. balanced) into quantum phases, and then use interference to extract that property in a single measurement. Every major quantum algorithm since then (Grover, Simon, Shor, quantum walks, QAOA) builds on this same foundation: prepare a superposition, encode information in phases, and use interference to amplify the correct answer.

Common Mistakes

Here are five pitfalls that frequently trip up people implementing Deutsch-Jozsa for the first time.

1. Forgetting to initialize the ancilla to |1⟩

Phase kickback requires the ancilla to be in the |−⟩ = (|0⟩ - |1⟩)/√2 state. To reach |−⟩, you must first apply X to flip the ancilla from |0⟩ to |1⟩, then apply H. If you skip the X gate, the ancilla starts in |+⟩ = (|0⟩ + |1⟩)/√2 instead. With |+⟩, the oracle applies no relative phase at all: U_f |x⟩|+⟩ = |x⟩|(f(x) XOR 0) + (f(x) XOR 1)⟩/√2 = |x⟩|+⟩ regardless of f(x). The algorithm produces random outputs and tells you nothing.

2. Measuring the ancilla qubit

Measuring the ancilla is not wrong, but it is wasteful. The ancilla always returns to |−⟩ after the oracle, regardless of whether f is constant or balanced. Measuring it always gives |1⟩ and provides zero information about the function. Worse, if you accidentally measure it before the final Hadamard on the input register, you could disturb the entanglement structure of the circuit. Best practice: only measure the input register.

3. Confusing constant_1 with the identity oracle

The constant-1 oracle applies an X gate to the ancilla, which adds a global phase of -1 to the entire state. Since the ancilla is in |−⟩, flipping it produces |+⟩, which after phase considerations returns a global phase. This global phase is unobservable, so the measurement outcome is still all zeros, correctly identified as CONSTANT. The mistake is thinking that “applying an X gate means something changed,” and expecting a different measurement result. Both constant oracles give the same output: all zeros.

4. Constructing an oracle that is not truly balanced

If you apply an even number of CNOT gates from the same qubit, they cancel out (CNOT is self-inverse). If your CNOT pattern does not produce a function with exactly 2^{n-1} ones and 2^{n-1} zeros, the promise is violated and the algorithm’s guarantees do not hold. Always verify a new oracle by computing its truth table for small n. For example, a single CNOT from x_0 to the ancilla gives f(x) = x_0, which returns 1 for exactly half the inputs (those with x_0 = 1). That is balanced. But if you accidentally CNOT from x_0 twice, the two CNOTs cancel and you get the identity, which is constant.

5. Thinking Deutsch-Jozsa works for arbitrary functions

The algorithm requires the promise that f is either constant or balanced. If f is neither (for example, f returns 1 on one-third of inputs and 0 on the rest), the algorithm can give any answer. Measuring all zeros does not prove the function is constant, and measuring a non-zero string does not prove it is balanced. Without the promise, you need to query more inputs or use a different algorithm. This is a feature of promise problems in computational complexity: the guarantee on the input is essential for the algorithm’s correctness.

Limitations and What It Actually Proves

Deutsch-Jozsa solves an artificially structured problem with a promise (the function is guaranteed to be constant or balanced). No classical adversary would design their encryption around a promise like this.

The algorithm does not break any real-world cryptography and is not practically useful on its own. What it does is prove, unconditionally and with a clean construction, that quantum computers have a fundamental computational advantage over classical ones for certain query problems. That proof of principle is what makes it historically and pedagogically indispensable.

Every more powerful quantum algorithm (Grover, Simon, Shor) builds on the same core ideas: superposition, phase kickback, and interference. Deutsch-Jozsa is where these tools first appear together in a single circuit.