Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Bernstein–Vazirani & Simon's Algorithm

Hidden strings, hidden periods, and the first exponential separation.

Simon's 1994 algorithm solves a problem with O(n)O(n) quantum queries that needs Ω(2n/2)\Omega(2^{n/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 11 quantum query but nn classical ones, randomized included.
  • Show that each run of Simon's circuit samples yy uniformly from s⊥s^\perp, and bound the number of runs needed.
  • Prove the Ω(2n/2)\Omega(2^{n/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
  1. ∣0n⟩∣0m⟩→ H⊗n 12n∑x∣x⟩∣0m⟩→ Uf 12n∑x∣x⟩∣f(x)⟩\ket{0^n}\ket{0^m}\xrightarrow{\,H^{\otimes n}\,}\frac{1}{\sqrt{2^n}}\sum_x\ket{x}\ket{0^m}\xrightarrow{\,U_f\,}\frac{1}{\sqrt{2^n}}\sum_x\ket{x}\ket{f(x)}

    One query to the bit oracle. No ∣−⟩\ket{-} here: the output register is meant to become entangled.

  2. =12n∑v∈im⁡f(∣xv⟩+∣xv⊕s⟩)∣v⟩=\frac{1}{\sqrt{2^n}}\sum_{v\in\operatorname{im}f}\big(\ket{x_v}+\ket{x_v\oplus s}\big)\ket{v}

    Group inputs by value: each vv in the image has exactly two preimages, xvx_v and xv⊕sx_v\oplus s (take s≠0ns\ne0^n).

  3. H⊗n(∣xv⟩+∣xv⊕s⟩)=12n∑y(−1)xv⋅y(1+(−1)s⋅y)∣y⟩H^{\otimes n}\big(\ket{x_v}+\ket{x_v\oplus s}\big)=\frac{1}{\sqrt{2^n}}\sum_y(-1)^{x_v\cdot y}\big(1+(-1)^{s\cdot y}\big)\ket{y}

    Hadamard identity, using (xv⊕s)⋅y=xv⋅y⊕s⋅y(x_v\oplus s)\cdot y = x_v\cdot y\oplus s\cdot y.

  4. Pr⁡[y]=∑v∣12n(−1)xv⋅y(1+(−1)s⋅y)∣2={2−(n−1)s⋅y=00s⋅y=1\Pr[y] = \sum_{v}\Big|\tfrac{1}{2^n}(-1)^{x_v\cdot y}\big(1+(-1)^{s\cdot y}\big)\Big|^2 = \begin{cases}2^{-(n-1)} & s\cdot y=0\\ 0 & s\cdot y=1\end{cases}

    Sum over the 2n−12^{n-1} values vv. Each run returns yy uniformly from s⊥={y:s⋅y=0}s^\perp=\{y: s\cdot y=0\}, an (n−1)(n-1)-dimensional subspace of F2n\mathbb{F}_2^n. Measuring the second register first is optional.

Repeat until the samples span s⊥s^\perp, then solve y(j)⋅s=0y^{(j)}\cdot s=0 by Gaussian elimination over F2\mathbb{F}_2 in O(n3)O(n^3) time: the unique nonzero solution is ss. (If the promise allows s=0ns=0^n, check the candidate s′s' with two classical queries: f(0n)=f(s′)f(0^n)=f(s') holds iff s=s′s=s'.)

Check your understanding

A single run of Simon's circuit returns yy. What do you know with certainty?

  1. y=sy = s
  2. y⋅s=0(mod2)y\cdot s = 0 \pmod 2
  3. y⊕s=0ny\oplus s = 0^n
  4. y⋅s=1(mod2)y\cdot s = 1 \pmod 2
Show the answer

B. y⋅s=0(mod2)y\cdot s = 0 \pmod 2

The amplitude of yy carries the factor 1+(−1)s⋅y1+(-1)^{s\cdot y}, which vanishes when s⋅y=1s\cdot y=1. So every outcome is orthogonal to ss (mod 2), uniformly so: one linear equation per run.

Brassard and Høyer (1997) later made the algorithm exact, with O(n)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=40n=40, a birthday attack needs about 2k2^k classical queries before a collision becomes likely. What is kk?

Show the answer

20

A collision becomes likely once q2≈2nq^2\approx 2^n, i.e. q≈220≈106q\approx 2^{20}\approx 10^6 queries. Simon's algorithm needs about 4040 runs.

Hidden subgroups, and what comes next

Simon's problem is a hidden subgroup problem (HSP). A function on a group GG is constant on the cosets of an unknown subgroup HH and distinct on different cosets; find HH. Here G=Z2nG=\mathbb{Z}_2^n and H={0n,s}H=\{0^n,s\}, and Fourier sampling (H⊗nH^{\otimes n} is the Fourier transform of Z2n\mathbb{Z}_2^n) returns random elements of H⊥H^\perp.

Shor's period finding is the same template over Z\mathbb{Z} (or ZN\mathbb{Z}_N) with H=rZH=r\mathbb{Z}, with the QFT in place of H⊗nH^{\otimes 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 GGHidden subgroupProblemQuantum status
Z2n\mathbb{Z}_2^n{0n,s}\{0^n,s\}Simonpolynomial (1994)
Z\mathbb{Z} or ZN\mathbb{Z}_NrZr\mathbb{Z}period finding, factoringpolynomial (Shor 1994)
Zp−1×Zp−1\mathbb{Z}_{p-1}\times\mathbb{Z}_{p-1}the line {(ℓk, k)}\{(\ell k,\,k)\}discrete log of gℓg^\ellpolynomial (Shor 1994)
dihedral DND_Na reflection subgrouplinked to lattice problems (Regev 2004)2O(log⁡N)2^{O(\sqrt{\log N})} (Kuperberg 2005)
symmetric SnS_nautomorphism subgroupsgraph isomorphismopen; single-copy Fourier sampling provably fails
For discrete logarithms, f(a,b)=gax−bf(a,b)=g^{a}x^{-b} with x=gℓx=g^\ell is constant exactly on cosets of the line a≡ℓba\equiv\ell b.

Key takeaways

  • Bernstein–Vazirani: one Fourier-sampling query reveals a hidden linear function s⋅xs\cdot x; classical algorithms need nn queries because each answer carries one bit.
  • Simon: each run samples yy uniformly from s⊥s^\perp; n−1+tn-1+t runs determine ss with probability >1−2−t>1-2^{-t}, so O(n)O(n) queries versus Θ(2n/2)\Theta(2^{n/2}) classically.
  • The classical bound is a collision argument: without seeing f(x)=f(x⊕s)f(x)=f(x\oplus s), qq queries rule out only O(q2)O(q^2) 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 nn queries, even with randomness?

  1. Classical computers cannot compute inner products mod 2 efficiently
  2. Each query returns one bit, so qq queries distinguish at most 2q2^q of the 2n2^n possible strings ss
  3. Because ff is balanced for every s≠0ns\ne0^n
  4. They don't: O(log⁡n)O(\log n) random queries suffice
Show the answer

B. Each query returns one bit, so qq queries distinguish at most 2q2^q of the 2n2^n possible strings ss

A qq-query decision tree has at most 2q2^q leaves, so its success probability on uniform ss is at most 2q−n2^{q-n}, and randomization only averages over trees. Success 2/32/3 forces q≥nq\ge n.

Question 2

What is the randomized classical query complexity of Simon's problem?

  1. Θ(n)\Theta(n)
  2. Θ(n2)\Theta(n^2)
  3. Θ(2n/2)\Theta(2^{n/2})
  4. Θ(2n)\Theta(2^n)
Show the answer

C. Θ(2n/2)\Theta(2^{n/2})

Until a collision f(x)=f(x⊕s)f(x)=f(x\oplus s) is found, the answers reveal almost nothing about ss, and qq queries find a collision with probability O(q2/2n)O(q^2/2^n). The birthday attack matches this, so the complexity is Θ(2n/2)\Theta(2^{n/2}).

Question 3

Simon's algorithm with nn-bit inputs: after n+9n+9 runs, the probability that the samples fail to determine ss is at most about

  1. 2−102^{-10}
  2. 12\tfrac12
  3. 1/n1/n
  4. 2−n2^{-n}
Show the answer

A. 2−102^{-10}

With n−1+tn-1+t samples the failure probability is below 2−t2^{-t}; here t=10t=10, so it is below 2−10≈0.1%2^{-10}\approx 0.1\%, independent of nn.

Question 4

In hidden-subgroup language, Simon's problem is the HSP for which group and subgroup?

  1. ZN\mathbb{Z}_N with subgroup rZNr\mathbb{Z}_N
  2. The symmetric group SnS_n with an automorphism subgroup
  3. The dihedral group with a reflection subgroup
  4. Z2n\mathbb{Z}_2^n with subgroup {0n,s}\{0^n, s\}
Show the answer

D. Z2n\mathbb{Z}_2^n with subgroup {0n,s}\{0^n, s\}

ff is constant exactly on the cosets {x,x⊕s}\{x, x\oplus s\} of H={0n,s}≤Z2nH=\{0^n,s\}\le\mathbb{Z}_2^n, and Fourier sampling over Z2n\mathbb{Z}_2^n returns elements of H⊥=s⊥H^\perp = s^\perp.

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.