Simon's algorithm is to be simulated for qubits with a hidden string chosen uniformly…
PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms
Quantum Information and Technology, Ch Oracles, quantum parallelism and the first algorithms
Problem
Simon's algorithm is to be simulated for n=6 qubits with a hidden string s chosen uniformly at random from the 26−1=63 non-zero six-bit strings. Each run of the quantum circuit (uniform superposition, query, second-register measurement or implicit measurement, Hadamards on the first register, measurement) is modelled classically as returning a string y∈{0,1}6 drawn uniformly at random from the 2n−1=32 strings satisfying y⋅s=0(mod2), as derived for a single Simon round. The simulation keeps running the circuit and keeps every distinct outcome y until it has collected 5 linearly independent vectors over {0,1} (the all-zero outcome y=000000 is a valid draw but is always dependent, so it wastes a run). Once 5 independent vectors are in hand, elimination mod 2 pins down s uniquely, since {y:y⋅s=0} is a 5-dimensional subspace of {0,1}6.
((a)) Explain why, once k independent vectors have been collected (spanning a subspace of size 2k inside the 32-element space), the number of further runs needed to obtain the (k+1)-th independent vector is a geometric random variable, and state its success probability pk.
((b)) Calculate the expected total number of runs N needed to reach 5 independent vectors.
((c)) Calculate the variance and standard deviation of N, stating which property of the stages lets their variances add.
((d)) If the whole procedure (fresh random s, fresh runs) is repeated for 1000 independent trials, predict the expected sample mean number of runs and its standard error, and give the interval, mean plus or minus two standard errors, within which a correctly written simulation's reported mean should fall with probability about 0.95.