Deutsch-Jozsa Algorithm Explained: Proof & Qiskit Code

We are given a black-box oracle that computes an unknown Boolean function taking an n-bit string and returning a single bit:

We are promised that f belongs strictly to one of two categories:

• Constant: The function returns the exact same value for all possible inputs (f(x) = 0 for all x, or f(x) = 1 for all x).
• Balanced: The function returns 0 for exactly half of the 2n inputs (2n-1 states) and 1 for the remaining half (2n-1 states).

The Objective: Determine with 100% mathematical certainty whether f is constant or balanced using the absolute minimum number of oracle evaluations.

Classically, if you query the oracle with an input x1 and receive f(x1) = 0, you learn nothing definitive. If your next query x2 yields f(x2) = 1, you immediately know f is balanced (best-case: 2 queries). However, in the worst-case scenario, every input you test continues to return 0.

Because a balanced function has exactly 2n-1 zeros, observing 2n-1 zeros in a row still leaves the possibility that the remaining 2n-1 inputs are all ones (balanced) or all zeros (constant). To be 100% deterministic, a classical computer must evaluate:

Quantum computing solves this in exactly 1 query (O(1)) with 100% certainty:

Note on randomized algorithms: A classical probabilistic algorithm could query k random inputs; if all return 0, the chance of being wrong is (1/2)k-1. While randomized testing is fast, only the quantum algorithm offers deterministic, exact certainty in O(1).

To compute f(x) reversibly, quantum computers use a unitary oracle Uf operating on an input register |x⟩ and an auxiliary target qubit |y⟩:

Rather than preparing the target qubit in |0⟩, we prepare it in the anti-symmetric superposition state |-⟩ = (|0⟩ − |1⟩) / √2 using an X gate followed by a Hadamard H. Watch what happens when Uf evaluates:

In both cases, we can write the result compactly:

The bit f(x) is not written to the target qubit at all—it is kicked back as an eigenvalue phase factor (-1)f(x) directly onto the input register state!

To understand how oracles are physically constructed, let us take a 3-qubit input register (q0, q1, q2) with an auxiliary target qubit (q3). Any Boolean function falls into one of four canonical implementations:

Oracle 1: Constant-0 (f(x) = 0 everywhere)

Because y ⊕ 0 = y, the target qubit is left completely untouched. The circuit is an empty identity wire:

Oracle 1: Identity wire — target qubit q3 remains unchanged.

Oracle 2: Constant-1 (f(x) = 1 everywhere)

Because y ⊕ 1 = ȳ, the target qubit must flip unconditionally for all inputs. We apply a single NOT (X) gate to q3:

Oracle 2: Unconditional X gate on q3 — imparts an unobservable global minus sign.

Oracle 3: Balanced Direct (f(x) = x0 ⊕ x2)

To create a balanced function, we can compute an inner product or parity check. In this example, CNOTs are placed on q0 and q2 targeting q3, leaving q1 unattached:

Oracle 3: CNOT controls on q0 and q2 — evaluates f(x) = x0 ⊕ x2.

Why does skipping q1 still yield a balanced function? Because the function output is determined strictly by x0 ⊕ x2. Across the 8 possible states, exactly 4 combinations give 0 (000, 010, 101, 111) and exactly 4 give 1 (001, 011, 100, 110). A balanced function does not need to depend on every qubit—it only needs an exact 50/50 output split across the 2n state space.

Oracle 4: Balanced Inverted (f(x) = ¬(x0 ⊕ x2) = x0 ⊕ x2 ⊕ 1)

This is the complement of Oracle 3 (inverting all outputs). We place CNOTs on q0 and q2, followed by an X gate on target q3:

Oracle 4: CNOT controls on q0 and q2 followed by NOT on q3.

Oracle Comparison Matrix

Here is the complete end-to-end Deutsch-Jozsa circuit for our 3-qubit balanced function (f(x) = x0 ⊕ x2):

Circuit Architecture: Complete Deutsch-Jozsa Circuit in Qiskit (IBM Quantum styling): State prep, superposition, oracle, interference Hadamards, and measurement.

The Mathematical Interference:

Before the final Hadamard transform, the input register is in the state (1/√2n) Σx (-1)f(x) |x⟩. Applying the Walsh-Hadamard transform H⊗n maps each basis state |x⟩ to (1/√2n) Σz (-1)x⋅z |z⟩. The total state becomes:

When we measure, consider the probability amplitude of measuring the all-zero state |00…0⟩ (where z = 00…0 ⇒ x⋅z = 0):

• If f is Constant: All (-1)f(x) have the same sign (±1). The sum adds constructively: α00…0 = (1/2n)(±2n) = ±1. The measurement probability is |±1|2 = 100%. You will measure `00…0` every single time.
• If f is Balanced: Exactly 2n-1 inputs yield +1 and 2n-1 yield -1. The sum cancels out completely: α00…0 = (1/2n)(2n-1 − 2n-1) = 0. The probability of measuring all zeros is strictly 0%! Any non-zero bitstring confirms f is balanced.

The script below builds, executes, and verifies all 4 oracles using modern Qiskit 2.x primitives (StatevectorSampler):

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

def create_oracle(oracle_type: str) -> QuantumCircuit:
    """Builds one of the 4 canonical oracles on 4 qubits (q0, q1, q2 input; q3 target)."""
    oracle = QuantumCircuit(4, name=oracle_type)
    
    if oracle_type == "constant_0":
        # Type 1: f(x) = 0 (Identity wire)
        pass
    elif oracle_type == "constant_1":
        # Type 2: f(x) = 1 (Unconditional target flip)
        oracle.x(3)
    elif oracle_type == "balanced_direct":
        # Type 3: f(x) = x0 ^ x2 (CNOT parity on q0 and q2)
        oracle.cx(0, 3)
        oracle.cx(2, 3)
    elif oracle_type == "balanced_inverted":
        # Type 4: f(x) = ~(x0 ^ x2) (CNOT parity + NOT gate)
        oracle.cx(0, 3)
        oracle.cx(2, 3)
        oracle.x(3)
    else:
        raise ValueError(f"Unknown oracle type: {oracle_type}")
        
    return oracle

def run_deutsch_jozsa(oracle_circuit: QuantumCircuit):
    """Wraps an oracle inside the full Deutsch-Jozsa algorithm and measures."""
    qc = QuantumCircuit(4, 3)
    
    # 1. State preparation: target qubit to |->
    qc.x(3)
    qc.h(range(4))
    qc.barrier()
    
    # 2. Insert the oracle
    qc.compose(oracle_circuit, inplace=True)
    qc.barrier()
    
    # 3. Interference decoding
    qc.h(range(3))
    
    # 4. Measure input register
    qc.measure([0, 1, 2], [0, 1, 2])
    
    # Execute on StatevectorSampler
    sampler = StatevectorSampler()
    result = sampler.run([qc], shots=100).result()
    counts = result[0].data.c.get_counts()
    verdict = "CONSTANT" if list(counts.keys()) == ['000'] else "BALANCED"
    
    return qc, counts, verdict

# Execute and compare all 4 canonical oracles
oracles = ["constant_0", "constant_1", "balanced_direct", "balanced_inverted"]

print(f"{'Oracle Type':<20} | {'Measurement':<12} | {'Decision':<10}")
print("-" * 50)
for o_name in oracles:
    oracle_qc = create_oracle(o_name)
    full_qc, counts, verdict = run_deutsch_jozsa(oracle_qc)
    print(f"{o_name:<20} | {str(counts):<12} | {verdict:<10}")

Execution Output:

Oracle Type          | Measurement  | Decision  
--------------------------------------------------
constant_0           | {'000': 100} | CONSTANT  
constant_1           | {'000': 100} | CONSTANT  
balanced_direct      | {'101': 100} | BALANCED  
balanced_inverted    | {'101': 100} | BALANCED  

Deepen your quantum intuition with our step-by-step mathematical and circuit guides: