Simon's Algorithm with s = 110
Every outcome y satisfies y·s = 0 mod 2; for s = 110 only 000, 001, 110, 111 appear (1/4 each), and s follows by Gaussian elimination.
Goal
See how each shot gives a linear equation about $s$.
Approximate duration: 5 minutes
Steps
- Enter $s=110$ and run.
- Record the outcomes that appear.
- Check $y\cdot s=0$ for each outcome.
- Solve the system and extract $s$.
Theory predicts only four outcomes: 000, 001, 110 and 111, each with probability $0.25$, and all satisfy $y\cdot s=0$. Two independent non-zero outcomes (such as 001 and 110) suffice to determine $s=110$.
In Simon's problem, a function $f$ satisfies $f(x)=f(x')$ if and only if $x'=x\oplus s$. The algorithm prepares a superposition, calls the oracle, implicitly measures the output register, then applies H to the input register; this produces a uniformly random value $y$ from the solutions orthogonal to $s$. After about $n$ linearly independent repetitions, the system $y\cdot s=0$ over the field $GF(2)$ is solved classically.
Simon proved an exponential separation in the number of queries compared with probabilistic classical algorithms in the oracle model; its idea inspired Shor's algorithm. This does not imply a speed-up for any particular practical problem.
Test your understanding
The quiz needs JavaScript.
Related topics
References
- Daniel R. Simon (1997). On the Power of Quantum Computation. SIAM J. Comput. 26(5):1474–1483 doi:10.1137/S0097539796298637
- 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.
