Oracle Algorithms

Deutsch-Jozsa Algorithm

Determining if a Function is Constant or Balanced

The Deutsch-Jozsa algorithm was one of the first quantum algorithms to demonstrate an exponential speedup over any deterministic classical algorithm. Given a black-box function promised to be either constant (same output for all inputs) or balanced (outputs 0 for half the inputs and 1 for the other half), it determines which with just a single query.

The Problem Statement

Consider a function f: {0,1}^n → {0,1} that is accessed only through an oracle — a black box that computes f(x) for any input x. We are promised that f is either constant, meaning f(x) = c for all x and some fixed c ∈ {0,1}, or balanced, meaning f(x) = 0 for exactly half of all possible inputs and f(x) = 1 for the other half.

Classically, determining whether f is constant or balanced requires evaluating the function on multiple inputs. In the worst case, a deterministic classical algorithm must query the oracle 2^(n-1) + 1 times: if it sees the same output for the first half of all possible inputs, the next query is needed to confirm the function is not balanced. Probabilistically, a constant number of queries suffices to succeed with high probability, but the Deutsch-Jozsa algorithm solves the problem deterministically with absolute certainty using only one quantum query.

f: \{0,1\}^n \rightarrow \{0,1\}

Function domain

\text{Constant: } f(x) = c \quad \text{or} \quad \text{Balanced: } |\{x : f(x) = 0\}| = |\{x : f(x) = 1\}| = 2^{n-1}

Promise

•Promise: The function is guaranteed to be either constant or balanced — no other possibility is allowed.
•Classical Complexity: Deterministic classical algorithms require O(2^n) queries in the worst case to distinguish the two cases with certainty.
•Quantum Complexity: The Deutsch-Jozsa algorithm solves the problem with exactly 1 quantum query, independent of n.
•Historical Importance: It was the first algorithm to prove an exponential quantum advantage over deterministic classical computation.

Quantum Solution

The algorithm begins by preparing an (n+1)-qubit register. The first n qubits are initialized to |0⟩, while the last qubit — the ancilla — is initialized to |1⟩. Applying a Hadamard gate to every qubit creates an equal superposition over all possible inputs on the first register and a superposition (|0⟩ - |1⟩)/√2 on the ancilla. This particular ancilla state is crucial because it enables phase kickback.

The oracle U_f is defined by its action U_f|x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩. When applied to our superposition, the ancilla's state causes the oracle to encode f(x) into a phase factor (-1)^f(x) on each component of the input register. This is the phase kickback effect: the oracle does not explicitly write f(x) anywhere, but it flips the phase of every basis state |x⟩ for which f(x) = 1.

After the oracle, applying Hadamard gates again to the first n qubits interferes all the superposed amplitudes. For a constant function, all phases are identical (either all +1 or all -1), so the interference is constructive only for the state |0⟩^⊗n. For a balanced function, the positive and negative phases cancel out at |0⟩^⊗n because exactly half the terms contribute +1 and half contribute -1. Measuring the first register therefore yields all zeros if and only if the function is constant.

|\psi_0\rangle = |0\rangle^{\otimes n} |1\rangle

Initial state

|\psi_1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}

After first Hadamards

|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} (-1)^{f(x)} |x\rangle \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}

After oracle

\text{If } f \text{ constant: } |\psi_3\rangle = \pm |0\rangle^{\otimes n} \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}

Final interference

•Initialization: Prepare |0⟩^⊗n|1⟩, then apply H^⊗(n+1) to create uniform superposition.
•Phase Kickback: The oracle U_f imparts a phase (-1)^f(x) to each basis state |x⟩ through the specially prepared ancilla.
•Interference: Hadamard gates on the input register create interference that concentrates amplitude at |0⟩^⊗n for constant functions.
•Measurement: If the measurement yields all zeros, f is constant; any other result proves f is balanced.

Significance and Extensions

Although the Deutsch-Jozsa problem is contrived and of limited practical value on its own, the algorithm introduced several techniques that underpin nearly all quantum query algorithms: the Hadamard transform to create uniform superposition, oracle-induced phase kickback, and final interference to extract global properties of a function. These same ideas appear in Bernstein-Vazirani, Simon's algorithm, and even Shor's period-finding subroutine.

The exponential separation between quantum and deterministic classical query complexity was historically important because it provided the first rigorous proof that quantum computers could solve certain problems exponentially faster than any classical computer without error. While randomized classical algorithms can solve the problem efficiently with small error probability, the deterministic speedup remains a cornerstone of quantum complexity theory.

•Template for Query Algorithms: The structure H → Oracle → H → Measure appears in many quantum algorithms.
•Phase Kickback: Converting an oracle from computing values to encoding phases is a universal quantum technique.
•Query Complexity: It established quantum query complexity as a rigorous framework for proving speedups.

Code in Action

Runnable implementations you can copy and experiment with.

Deutsch-Jozsa with Qiskit

A 3-qubit Deutsch-Jozsa circuit with a balanced oracle (f(x) = x0 ⊕ x1). The measurement should never return 000.

deutsch_jozsa_qiskit.py

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

n = 3
circuit = QuantumCircuit(n + 1, n)

# Initialize ancilla to |1>
circuit.x(n)

# Apply Hadamard to all qubits
circuit.h(range(n + 1))

# Balanced oracle: f(x) = x0 XOR x1
circuit.cx(0, n)
circuit.cx(1, n)

# Apply Hadamard to input register
circuit.h(range(n))

# Measure input register
circuit.measure(range(n), range(n))

# Execute
simulator = AerSimulator()
job = simulator.run(circuit, shots=1024)
counts = job.result().get_counts()
print("Measurement results:", counts)

# For a balanced function, the probability of measuring |000> is zero

Deutsch-Jozsa with PennyLane

The same algorithm implemented in PennyLane, returning the probability distribution over the input register.

deutsch_jozsa_pennylane.py

import pennylane as qml
import numpy as np

n = 3
dev = qml.device("default.qubit", wires=n + 1)

def balanced_oracle():
    qml.CNOT(wires=[0, n])
    qml.CNOT(wires=[1, n])

@qml.qnode(dev)
def deutsch_jozsa():
    # Initialize ancilla to |1>
    qml.PauliX(wires=n)
    # Hadamard on all qubits
    for i in range(n + 1):
        qml.Hadamard(wires=i)
    # Apply oracle
    balanced_oracle()
    # Hadamard on input register
    for i in range(n):
        qml.Hadamard(wires=i)
    return qml.probs(wires=range(n))

probs = deutsch_jozsa()
print("Probability of |000>:", probs[0])
print("All probabilities:", probs)

# For a balanced function, probs[0] should be approximately 0

Explore next

Bernstein-Vazirani Algorithm

Explore next

Simon's Algorithm

from qiskit import QuantumCircuit from qiskit_aer import AerSimulator n = 3 circuit = QuantumCircuit(n + 1, n) # Initialize ancilla to |1> circuit.x(n) # Apply Hadamard to all qubits circuit.h(range(n + 1)) # Balanced oracle: f(x) = x0 XOR x1 circuit.cx(0, n) circuit.cx(1, n) # Apply Hadamard to input register circuit.h(range(n)) # Measure input register circuit.measure(range(n), range(n)) # Execute simulator = AerSimulator() job = simulator.run(circuit, shots=1024) counts = job.result().get_counts() print("Measurement results:", counts) # For a balanced function, the probability of measuring |000> is zero

import pennylane as qml import numpy as np n = 3 dev = qml.device("default.qubit", wires=n + 1) def balanced_oracle(): qml.CNOT(wires=[0, n]) qml.CNOT(wires=[1, n]) @qml.qnode(dev) def deutsch_jozsa(): # Initialize ancilla to |1> qml.PauliX(wires=n) # Hadamard on all qubits for i in range(n + 1): qml.Hadamard(wires=i) # Apply oracle balanced_oracle() # Hadamard on input register for i in range(n): qml.Hadamard(wires=i) return qml.probs(wires=range(n)) probs = deutsch_jozsa() print("Probability of |000>:", probs[0]) print("All probabilities:", probs) # For a balanced function, probs[0] should be approximately 0