algorithmsAdvancedOracle (query) algorithms

Simon's Algorithm

Simon's algorithm finds the hidden period s of a two-to-one function with O(n) queries, whereas classical randomized algorithms need Ω(2^{n/2}).

The problem

A function $f:\{0,1\}^n\to\{0,1\}^n$ guaranteed to satisfy $f(x)=f(y)\iff y\in\{x,x\oplus s\}$; the task is to find $s\neq0$.

Key idea

Querying a superposition and then applying Hadamards makes every measured outcome $y$ satisfy $y\cdot s=0$; collecting $n-1$ independent equations determines $s$ by linear algebra over $\mathrm{GF}(2)$.

Prerequisites

$2n$ qubits, an oracle that satisfies the promise, and classical processing to solve a linear system over $\mathrm{GF}(2)$.

Steps

  1. Prepare two registers of $n$ qubits in $|0\rangle$.
  2. Apply $H$ to the first register.
  3. Query the oracle: $|x\rangle|0\rangle\mapsto|x\rangle|f(x)\rangle$.
  4. Apply $H$ to the first register and measure it to obtain $y$ with $y\cdot s=0$.
  5. Repeat until you have $n-1$ linearly independent equations.
  6. Solve the system classically by Gaussian elimination over $\mathrm{GF}(2)$.

Simon's algorithm was the first example of an exponential separation in the oracle model between a quantum computer and a randomised classical computer, and it directly inspired Shor's algorithm (Simon 1997).

The problem: a function $f:\{0,1\}^n\to\{0,1\}^n$ with a promise that there is a string $s\neq0$ such that $f(x)=f(y)$ if and only if $y=x$ or $y=x\oplus s$, i.e. the function is two-to-one and periodic under XOR. The task is to find $s$.

Classically, the only approach is to search for a "collision" $f(x)=f(y)$ and then compute $s=x\oplus y$. By the birthday paradox this takes about $2^{n/2}$ queries, and it has been proved that any randomised algorithm needs $\Omega(2^{n/2})$.

Quantumly we use two registers of $n$ qubits. We put the first in a full superposition, query the oracle $|x\rangle|0\rangle\mapsto|x\rangle|f(x)\rangle$, and then ignore (or measure) the second register. The first register is left in $\frac{1}{\sqrt2}(|x_0\rangle+|x_0\oplus s\rangle)$ for a random value $x_0$. After the Hadamards the amplitude of each $y$ is proportional to $(-1)^{x_0\cdot y}\big(1+(-1)^{s\cdot y}\big)$, so only values $y$ satisfying $y\cdot s=0 \pmod 2$ appear, uniformly distributed among them. Each run gives one linear equation in $s$. After about $n-1$ linearly independent equations (usually $O(n)$ runs) we solve the system by Gaussian elimination over the field $\mathrm{GF}(2)$ and obtain the unique non-zero $s$.

Building the oracle in the lab: copy the first register into the second with CNOTs ($f(x)=x$); then, if $j$ is the lowest bit of $s$ equal to 1, add a CNOT from qubit $j$ to every qubit $n+i$ with $s_i=1$. The result is $f(x)=x\oplus x_j s$, which indeed satisfies $f(x)=f(x\oplus s)$ and is two-to-one. By default the lab takes $3n+4$ samples, checks that every measured $y$ satisfies $y\cdot s=0$, and solves the system classically.

The honest comparison: the exponential separation is proved only in the oracle model, and no known practical problem is solved directly by Simon's algorithm. The classical part (Gaussian elimination) is an essential part of the algorithm, which is hybrid by nature.

$$H^{\otimes n}\tfrac{1}{\sqrt2}\big(|x_0\rangle+|x_0\oplus s\rangle\big)=\frac{1}{\sqrt{2^{n+1}}}\sum_{y}(-1)^{x_0\cdot y}\big(1+(-1)^{s\cdot y}\big)|y\rangle$$

Interactive simulation and results

Loading the simulator…

Comparison with the classical solution

Classically$\Theta(2^{n/2})$ queries
Quantum$O(n)$ queries, $2n$ qubits, and $O(n^3)$ classical operations for Gaussian elimination

Any randomised classical algorithm needs $\Omega(2^{n/2})$ queries (collision search). The quantum one needs $O(n)$ queries with polynomial classical post-processing: a proven exponential separation in the oracle model.

Limitations of the algorithm and the simulation

The separation is proved in the oracle model, not for a practical problem. The lab's oracle is one special kind of periodic function ($f(x)=x\oplus x_j s$), built with knowledge of $s$. The default of $3n+4$ samples may occasionally not be enough to determine $s$ uniquely (the lab reports the rank of the system and the candidates). The simulation needs $2^{2n}$ amplitudes.

Qiskit code

Qiskit ≥ 1.0
# Tested with Qiskit 2.6.2 / qiskit-aer 0.18.4; output shown was produced with: StatevectorSampler(seed=3)
from itertools import product
from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

s = "110"                       # hidden period, printed q2 q1 q0
n = len(s)
sb = [int(b) for b in reversed(s)]          # sb[i] = bit of qubit i

# Oracle f(x) = x XOR (x_j * s), j = lowest set bit of s  ->  f(x) = f(x XOR s)
qc = QuantumCircuit(2 * n, n)
qc.h(range(n))
qc.barrier()
for i in range(n):
    qc.cx(i, n + i)
j = sb.index(1)
for i in range(n):
    if sb[i]:
        qc.cx(j, n + i)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))

counts = StatevectorSampler(seed=3).run([qc], shots=12).result()[0].data.c.get_counts()
print("measured y:", counts)

dot = lambda a, b: sum(int(x) * int(y) for x, y in zip(a, b)) % 2
print("all y satisfy y.s = 0 (mod 2):", all(dot(y, s) == 0 for y in counts))
# classical post-processing: non-zero candidates orthogonal to every observed y
cands = ["".join(c) for c in product("01", repeat=n) if "1" in c and all(dot(y, "".join(c)) == 0 for y in counts)]
print("candidates for s:", cands)

Actual output when run

measured y: {'000': 5, '111': 1, '110': 3, '001': 3}
all y satisfy y.s = 0 (mod 2): True
candidates for s: ['110']

Runs on your machine after pip install qiskit qiskit-aer; it is not executed inside WordPress.

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. Daniel R. Simon (1997). On the Power of Quantum Computation. SIAM J. Comput. 26(5):1474–1483 doi:10.1137/S0097539796298637
  2. Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
  3. John Watrous / IBM Quantum (2025). Fundamentals of Quantum Algorithms (course). IBM Quantum Learning quantum.cloud.ibm.com