Deutsch-Jozsa Algorithm — First Quantum Speedup

Deutsch-Jozsa (1992) is historically significant as the first quantum algorithm that demonstrated an exponential speedup over the best classical algorithm. The problem it solves is artificial — no practical application uses it — but the techniques it introduces (quantum oracles, phase kickback, Hadamard interference) appear in Grover's search, Shor's algorithm, and quantum machine learning.

Understanding Deutsch-Jozsa is understanding how quantum computers use interference to extract global properties of a function with a single query. This is the fundamental mechanism of quantum speedup.

The Problem

Given a function f: {0,1}^n → {0,1}, promised to be either: - Constant: f(x) = 0 for all x, or f(x) = 1 for all x - Balanced: f(x) = 0 for exactly half the inputs, f(x) = 1 for the other half

Classical deterministic: need up to 2^(n-1)+1 queries to guarantee an answer. Quantum (Deutsch-Jozsa): 1 oracle query always suffices.

The Algorithm

1. Prepare n+1 qubits: n query qubits in |0⟩, 1 output qubit in |1⟩
2. Apply Hadamard to all qubits: creates superposition of all inputs
3. Query the oracle: applies phase kickback
4. Apply Hadamard to query qubits again: interferes amplitudes
5. Measure query qubits: all-zeros = constant, any nonzero = balanced

import numpy as np

def deutsch_jozsa_sim(oracle_matrix, n):
    """
    Simulates Deutsch-Jozsa for n-qubit oracle.
    Returns 'constant' or 'balanced'.
    """
    N = 2**n
    # Initial state |0...0>|1> after Hadamards
    # In phase kickback formulation:
    # After oracle: amplitude of |0...0> is 1/N * sum_x (-1)^f(x)
    # If constant: sum = +/-N -> amplitude = +/-1 -> all-zero measurement certain
    # If balanced: sum = 0 -> amplitude = 0 -> all-zero measurement impossible

    # Simplified: directly check via oracle
    values = [oracle_matrix[x] for x in range(N)]
    if len(set(values)) == 1:
        return 'constant'
    elif sum(values) == N // 2:
        return 'balanced'
    else:
        return 'neither (oracle not valid)'

# Test with n=3 (8 inputs)
n = 3
N = 2**n
constant_oracle = {x: 1 for x in range(N)}  # f(x) = 1 always
balanced_oracle  = {x: 0 if x < N//2 else 1 for x in range(N)}

print(f'Constant oracle: {deutsch_jozsa_sim(constant_oracle, n)}')
print(f'Balanced oracle: {deutsch_jozsa_sim(balanced_oracle, n)}')

Why It Works — Interference

The key is the Hadamard-oracle-Hadamard sandwich:

After the second Hadamard, the amplitude of measuring |0...0⟩ is (1/2^n) × Σₓ (-1)^f(x).

• Constant f: all terms (+1) or all terms (-1). Sum = ±2^n. Amplitude = ±1. Measure |0...0⟩ with probability 1.
• Balanced f: half (+1) and half (-1) terms cancel. Sum = 0. Amplitude = 0. Never measure |0...0⟩.

The quantum computer computed all 2^n values simultaneously and their sum via interference — in one oracle query. This is quantum parallelism + interference working together.

Frequently Asked Questions