Hidden strings, hidden periods, and the first exponential separation.
Simon's 1994 algorithm solves a problem with O(n) quantum queries that needs Ω(2n/2) queries from any classical algorithm, randomized or not. It was the first exponential separation of its kind relative to an oracle, and the direct inspiration for Shor's period-finding algorithm.
What you’ll learn
Prove that Bernstein–Vazirani needs 1 quantum query but n classical ones, randomized included.
Show that each run of Simon's circuit samples y uniformly from s⊥, and bound the number of runs needed.
Prove the Ω(2n/2) randomized lower bound for Simon's problem with a collision argument.
Place both algorithms in the hidden subgroup framework and describe the open non-abelian cases.
Bernstein–Vazirani: learning a linear function
Bernstein and Vazirani also nested the problem, using the answers of one level of instances to define the next (recursive Fourier sampling). This gave a superpolynomial separation between quantum and classical query complexity: the first oracle evidence that BQP may be larger than BPP. Simon made the gap exponential.
Simon's algorithm
DerivationOne run of Simon's circuit
∣0n⟩∣0m⟩H⊗n2n1x∑∣x⟩∣0m⟩Uf2n1x∑∣x⟩∣f(x)⟩
One query to the bit oracle. No ∣−⟩ here: the output register is meant to become entangled.
=2n1v∈imf∑(∣xv⟩+∣xv⊕s⟩)∣v⟩
Group inputs by value: each v in the image has exactly two preimages, xv and xv⊕s (take s=0n).
Sum over the 2n−1 values v. Each run returns yuniformly from s⊥={y:s⋅y=0}, an (n−1)-dimensional subspace of F2n. Measuring the second register first is optional.
Repeat until the samples span s⊥, then solve y(j)⋅s=0 by Gaussian elimination over F2 in O(n3) time: the unique nonzero solution is s. (If the promise allows s=0n, check the candidate s′ with two classical queries: f(0n)=f(s′) holds iff s=s′.)
Check your understanding
A single run of Simon's circuit returns y. What do you know with certainty?
y=s
y⋅s=0(mod2)
y⊕s=0n
y⋅s=1(mod2)
Show the answer
B.y⋅s=0(mod2)
The amplitude of y carries the factor 1+(−1)s⋅y, which vanishes when s⋅y=1. So every outcome is orthogonal to s (mod 2), uniformly so: one linear equation per run.
Brassard and Høyer (1997) later made the algorithm exact, with O(n) queries and zero error, by using amplitude amplification to guarantee that every round yields a new independent equation.
The classical lower bound
Predict before you look
For n=40, a birthday attack needs about 2k classical queries before a collision becomes likely. What is k?
Show the answer
20
A collision becomes likely once q2≈2n, i.e. q≈220≈106 queries. Simon's algorithm needs about 40 runs.
Hidden subgroups, and what comes next
Simon's problem is a hidden subgroup problem (HSP). A function on a group G is constant on the cosets of an unknown subgroup H and distinct on different cosets; find H. Here G=Z2n and H={0n,s}, and Fourier sampling (H⊗n is the Fourier transform of Z2n) returns random elements of H⊥.
Shor's period finding is the same template over Z (or ZN) with H=rZ, with the QFT in place of H⊗n. Every HSP over a finite abelian group can be solved this way with polynomially many queries and efficient processing; see The Hidden Subgroup Problem.
Group G
Hidden subgroup
Problem
Quantum status
Z2n
{0n,s}
Simon
polynomial (1994)
Z or ZN
rZ
period finding, factoring
polynomial (Shor 1994)
Zp−1×Zp−1
the line {(ℓk,k)}
discrete log of gℓ
polynomial (Shor 1994)
dihedral DN
a reflection subgroup
linked to lattice problems (Regev 2004)
2O(logN) (Kuperberg 2005)
symmetric Sn
automorphism subgroups
graph isomorphism
open; single-copy Fourier sampling provably fails
For discrete logarithms, f(a,b)=gax−b with x=gℓ is constant exactly on cosets of the line a≡ℓb.
Key takeaways
Bernstein–Vazirani: one Fourier-sampling query reveals a hidden linear function s⋅x; classical algorithms need n queries because each answer carries one bit.
Simon: each run samples y uniformly from s⊥; n−1+t runs determine s with probability >1−2−t, so O(n) queries versus Θ(2n/2) classically.
The classical bound is a collision argument: without seeing f(x)=f(x⊕s), q queries rule out only O(q2) candidates.
Both are abelian hidden subgroup problems solved by Fourier sampling, the template of Shor's algorithm; non-abelian HSPs (dihedral, symmetric) remain open.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Question 1
Why does every classical algorithm for Bernstein–Vazirani need at least n queries, even with randomness?
Classical computers cannot compute inner products mod 2 efficiently
Each query returns one bit, so q queries distinguish at most 2q of the 2n possible strings s
Because f is balanced for every s=0n
They don't: O(logn) random queries suffice
Show the answer
B. Each query returns one bit, so q queries distinguish at most 2q of the 2n possible strings s
A q-query decision tree has at most 2q leaves, so its success probability on uniform s is at most 2q−n, and randomization only averages over trees. Success 2/3 forces q≥n.
Question 2
What is the randomized classical query complexity of Simon's problem?
Θ(n)
Θ(n2)
Θ(2n/2)
Θ(2n)
Show the answer
C.Θ(2n/2)
Until a collision f(x)=f(x⊕s) is found, the answers reveal almost nothing about s, and q queries find a collision with probability O(q2/2n). The birthday attack matches this, so the complexity is Θ(2n/2).
Question 3
Simon's algorithm with n-bit inputs: after n+9 runs, the probability that the samples fail to determine s is at most about
2−10
21
1/n
2−n
Show the answer
A.2−10
With n−1+t samples the failure probability is below 2−t; here t=10, so it is below 2−10≈0.1%, independent of n.
Question 4
In hidden-subgroup language, Simon's problem is the HSP for which group and subgroup?
ZN with subgroup rZN
The symmetric group Sn with an automorphism subgroup
The dihedral group with a reflection subgroup
Z2n with subgroup {0n,s}
Show the answer
D.Z2n with subgroup {0n,s}
f is constant exactly on the cosets {x,x⊕s} of H={0n,s}≤Z2n, and Fourier sampling over Z2n returns elements of H⊥=s⊥.
Further reading
E. Bernstein & U. Vazirani, "Quantum complexity theory", SIAM J. Comput.26, 1411–1473 (1997); conference version STOC 1993.
D. R. Simon, "On the power of quantum computation", SIAM J. Comput.26, 1474–1483 (1997); conference version FOCS 1994.
A. M. Childs & W. van Dam, "Quantum algorithms for algebraic problems", Rev. Mod. Phys.82, 1 (2010).
G. Kuperberg, "A subexponential-time quantum algorithm for the dihedral hidden subgroup problem", SIAM J. Comput.35, 170–188 (2005).
R. de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415.