Each run of Simon's quantum subroutine produces a uniformly random string y satisfying y dot s = 0 (mod 2). How many runs are needed to determine s with high probability?
A1 run
Bn runs (to get n-1 linearly independent constraints plus confirmation)
C2^n runs
Dsqrt(2^n) runs
Each query produces a random y from the (n-1)-dimensional subspace orthogonal to s. After O(n) queries, you expect to have n-1 linearly independent vectors, which define s (up to the trivial solution 0) via Gaussian elimination. The probability of getting n-1 independent vectors in cn runs (for a small constant c > 1) is high. This is polynomially many queries — exponentially better than the classical O(2^(n/2)).
Question 2 True / False
Simon's algorithm achieves its speedup by using quantum parallelism to evaluate f on all inputs simultaneously, then directly reading off the period s.
TTrue
FFalse
Answer: False
Quantum parallelism evaluates f on all inputs in superposition, but measurement does not directly reveal s. Instead, measuring the output register collapses the input register to a uniform superposition of two values x and x xor s. Applying Hadamard to the input register and measuring produces a random y with y dot s = 0. The period is recovered indirectly by collecting enough such constraints and solving a linear system classically. The quantum speedup comes from generating these constraints efficiently, not from reading the answer directly.
Question 3 Short Answer
Why was Simon's algorithm historically significant for the development of quantum computing, beyond the specific problem it solves?
Think about your answer, then reveal below.
Model answer: Simon's algorithm was the first to prove an exponential quantum speedup over all classical algorithms, including probabilistic ones — not just deterministic ones as in Deutsch-Jozsa. More importantly, it directly inspired Shor's factoring algorithm. Shor adapted Simon's approach of using quantum Fourier sampling to find hidden periodicity, replacing the Z_2^n group structure with modular arithmetic and the quantum Fourier transform over Z_N.
Simon's problem is a 'hidden subgroup problem' over the group Z_2^n. Shor's factoring algorithm is conceptually the same pattern applied to the cyclic group Z_N: use quantum parallelism to create a periodic superposition, then use a Fourier transform to extract the period. Simon's algorithm showed that this general strategy could yield exponential speedups, which motivated the search for analogous algorithms over other groups.