Algorithm Zoo · Search
Simon's Algorithm
First described: Daniel Simon, 1994
The problem
Given f : {0,1}^n → {0,1}^n with the promise f(x) = f(x ⊕ s) for some hidden s, find s.
Inspired Shor's algorithm. Provable exponential separation against randomized classical algorithms in the oracle model. Period-finding for an XOR-period — Shor's is the multiplicative-group analog.
Best classical
Θ(2^{n/2}) queries (birthday bound).
Quantum complexity
O(n) queries.
Our verdict
The structural ancestor of Shor's algorithm and the only oracle-separation classic that has plausible cryptanalytic applications (key-recovery on certain block-cipher modes). Important historically and as a stepping stone.
When to use it
- Teaching the mechanism behind Shor.
- Cryptanalysis of certain symmetric primitives (block-cipher key recovery via Simon's structure — see Kuwakado-Morii 2010, Bonnetain et al.).
When not to use it
- Anything else — the f promise is too specific to arise naturally.
Classical baseline
Birthday-attack-style collision finding — 2^{n/2} queries.
Hardware cost
2n qubits, O(n) oracle queries, post-processing solves linear system over F₂.
Key papers
- On the Power of Quantum Computation ↗
Simon · 1994 · FOCS
Deep-dive tutorials
Last verified: 2026-05-24