Oracle Algorithms

Simon's Algorithm

Finding a Hidden Period of a Function

Simon's algorithm finds a hidden period s of a function f: {0,1}^n → {0,1}^n promised to be periodic under bitwise XOR. It runs in polynomial time on a quantum computer, while the best classical algorithms require exponentially many queries. Simon's algorithm was a direct precursor to Shor's factoring algorithm.

The Period-Finding Problem

We are given a function f: {0,1}^n → {0,1}^n with the promise that there exists a secret string s ∈ {0,1}^n such that f(x) = f(y) if and only if y = x or y = x ⊕ s. In other words, the function is two-to-one and periodic under bitwise XOR with period s. If s = 0, the function is one-to-one. The goal is to determine s.

Classically, finding s is hard because evaluating f on random inputs produces collisions only with low probability. The birthday paradox suggests you need about 2^(n/2) queries to find a collision, and each collision gives only partial information about s. The best classical algorithms therefore require exponential time in n.

f(x) = f(x \oplus s) \quad \text{for all } x \in \{0,1\}^n

Periodicity condition

\text{Find the non-zero period } s \in \{0,1\}^n \text{ given oracle access to } f

Goal

•Promise: f(x) = f(y) iff y = x or y = x ⊕ s for some hidden period s.
•Classical Complexity: Ω(2^(n/2)) queries are required classically to find the period with high probability.
•Quantum Complexity: Simon's algorithm requires O(n) quantum queries and O(n^3) classical post-processing.
•Connection to Shor: The quantum period-finding subroutine in Shor's algorithm is a direct generalization of Simon's approach.

Quantum Approach

The algorithm uses two quantum registers, each of n qubits. First, it creates a uniform superposition over all inputs x in the first register by applying Hadamard gates. Then it queries the oracle U_f, which maps |x⟩|0⟩ to |x⟩|f(x)⟩. After the oracle, the two registers are entangled: each value of f(x) in the second register is correlated with a superposition of the two preimages x and x ⊕ s in the first register.

Measuring the second register collapses it to some value f(x0). Due to entanglement, the first register collapses to the superposition (|x0⟩ + |x0 ⊕ s⟩)/√2. Applying Hadamard gates to this state produces an interference pattern: only basis states |y⟩ that satisfy y · s = 0 (mod 2) have non-zero amplitude. Measuring the first register therefore yields a random string y orthogonal to s.

Each run of the circuit produces one such y. After O(n) independent runs, we collect enough linearly independent equations y^(i) · s = 0 to solve for s using Gaussian elimination over the field GF(2). The entire process is efficient: the quantum part requires only O(n) queries, and the classical post-processing takes polynomial time.

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

After oracle

|\phi\rangle = \frac{1}{\sqrt{2}} \left( |x_0\rangle + |x_0 \oplus s\rangle \right)

After measuring output register

H^{\otimes n}|\phi\rangle = \frac{1}{\sqrt{2^{n-1}}} \sum_{y: y \cdot s = 0} (-1)^{x_0 \cdot y} |y\rangle

After Hadamard transform

•Superposition: Create an equal superposition over all 2^n inputs in the first register.
•Oracle: Query U_f to entangle the input register with f(x) in the output register.
•Measurement: Measure the output register, then apply H^⊗n to the input register.
•Post-Processing: Solve the linear system {y^(i) · s = 0} over GF(2) using Gaussian elimination.

Exponential Separation

Simon's algorithm provided the first example of an exponential separation between quantum and probabilistic classical query complexity for a natural algebraic problem. This result was surprising because it did not rely on unproven complexity assumptions like factoring — the speedup was unconditional.

The algorithm also has practical implications for cryptography. Simon's algorithm can be used to break certain symmetric ciphers that rely on hidden periodic structures. More importantly, it served as the intellectual bridge from simple oracle algorithms like Deutsch-Jozsa to the transformative power of Shor's algorithm for integer factorization.

•Provable Speedup: The exponential gap does not depend on any unproven complexity assumptions.
•Cryptanalysis: Simons algorithm breaks certain block cipher modes and MAC constructions.
•Bridge to Shor: The quantum Fourier transform generalizes the H^⊗n step to continuous groups.

Code in Action

Runnable implementations you can copy and experiment with.

Simon's Algorithm with Qiskit

A 2-qubit Simon circuit with hidden period s = '11'. The measurement yields only strings y satisfying y · s = 0.

simons_qiskit.py

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

n = 2
circuit = QuantumCircuit(2 * n, n)

# Superposition on first register
circuit.h(range(n))

# Oracle for period s = 11
# f(x) = [x0 XOR x1, 0]
circuit.barrier()
circuit.cx(0, n)    # y0 XOR= x0
circuit.cx(1, n)    # y0 XOR= x1
circuit.barrier()

# Hadamard on first register
circuit.h(range(n))

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

# Execute
simulator = AerSimulator()
job = simulator.run(circuit, shots=2048)
counts = job.result().get_counts()
print(counts)

# Expected: only 00 and 11 (since y·11 = 0 means y0 = y1)

Simon's Algorithm with PennyLane

PennyLane implementation returning measurement counts for the first register.

simons_pennylane.py

import pennylane as qml

n = 2
dev = qml.device("default.qubit", wires=2 * n)

@qml.qnode(dev)
def simon_algorithm():
    # Superposition on first register
    for i in range(n):
        qml.Hadamard(wires=i)
    
    # Oracle: f(x) = [x0 XOR x1, 0]
    qml.CNOT(wires=[0, n])
    qml.CNOT(wires=[1, n])
    
    # Hadamard on first register
    for i in range(n):
        qml.Hadamard(wires=i)
    
    return qml.counts(wires=range(n))

counts = simon_algorithm(shots=1024)
print(counts)

# Expected: only 00 and 11 appear

Explore next

Shor's Algorithm

Explore next

Grover's Algorithm

from qiskit import QuantumCircuit from qiskit_aer import AerSimulator n = 2 circuit = QuantumCircuit(2 * n, n) # Superposition on first register circuit.h(range(n)) # Oracle for period s = 11 # f(x) = [x0 XOR x1, 0] circuit.barrier() circuit.cx(0, n) # y0 XOR= x0 circuit.cx(1, n) # y0 XOR= x1 circuit.barrier() # Hadamard on first register circuit.h(range(n)) # Measure first register circuit.measure(range(n), range(n)) # Execute simulator = AerSimulator() job = simulator.run(circuit, shots=2048) counts = job.result().get_counts() print(counts) # Expected: only 00 and 11 (since y·11 = 0 means y0 = y1)

import pennylane as qml n = 2 dev = qml.device("default.qubit", wires=2 * n) @qml.qnode(dev) def simon_algorithm(): # Superposition on first register for i in range(n): qml.Hadamard(wires=i) # Oracle: f(x) = [x0 XOR x1, 0] qml.CNOT(wires=[0, n]) qml.CNOT(wires=[1, n]) # Hadamard on first register for i in range(n): qml.Hadamard(wires=i) return qml.counts(wires=range(n)) counts = simon_algorithm(shots=1024) print(counts) # Expected: only 00 and 11 appear