Simon's Algorithm

Simon's algorithm finds a hidden period of a 2-to-1 function exponentially faster than any classical method — the direct inspiration for Shor.

Speedup

exponential (oracle model)

Output

hidden string s via linear system

Legacy

blueprint for Shor's period-finding

What it does

Simon's problem: f(x)=f(x⊕s). Each run yields a random bit-string y orthogonal to s. After ~n runs, solve the linear system over GF(2) to recover s. It was the first problem with a proven exponential quantum speedup in the query model.

Where it's used

Historically pivotal — it showed exponential separation and led Shor to reframe factoring as period-finding.

In code (Qiskit)

# Repeat: prepare, apply oracle, Hadamard, measure -> y with y.s=0
# Solve linear system over GF(2) for s