ExperimentAdvancedInteractive experiment

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

  1. Enter $s=110$ and run.
  2. Record the outcomes that appear.
  3. Check $y\cdot s=0$ for each outcome.
  4. Solve the system and extract $s$.
Loading the simulator…
What theory predicts

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

  1. Daniel R. Simon (1997). On the Power of Quantum Computation. SIAM J. Comput. 26(5):1474–1483 doi:10.1137/S0097539796298637
  2. 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.