Simon's algorithm and the hidden subgroup problem
In 1994 Daniel Simon, then at the Université de Montréal, found a problem that a quantum computer solves with about queries and any classical computer, even one allowed to guess, needs about . It was the first exponential separation against randomized classical algorithms, and its structure, a hidden period revealed by Fourier sampling, was exactly what Peter Shor needed. Weeks after reading Simon’s paper, Shor had his factoring algorithm.
On the plate: equations collected from quantum queries, solved by Gaussian elimination.
The problem
A function on -bit strings is promised to satisfy if and only if or , for some unknown nonzero . Find . Classically you must find a collision, two inputs with the same output, and by the birthday paradox that takes about queries. Simon proved no classical algorithm does fundamentally better. Established
The quantum algorithm
Prepare the uniform superposition, compute into a second register, and measure that register. The first register collapses to for a random . Apply Hadamards and measure: you get a random with , every such equally likely. Each run gives one linear equation for . Hide 11 (four bits) and a few times, or . Once you have independent equations, Gaussian elimination over GF(2) leaves a single nonzero solution: . About runs suffice on average.
The hidden subgroup problem
Simon’s, Deutsch–Jozsa’s and Shor’s problems are all instances of one pattern: a function is constant on the cosets of a hidden subgroup of a group and different on different cosets; find . For Simon, is bit strings under XOR and . For Shor, is the integers and the multiples of a period. Whenever is abelian, the Fourier transform over solves the problem efficiently, as Alexei Kitaev showed in 1995. Established
Where it gets hard
For non-abelian groups the story changes. The symmetric group’s HSP would solve graph isomorphism; the dihedral group’s HSP is closely related, as Oded Regev showed in 2002, to finding short vectors in lattices, the problem behind post-quantum cryptography (Chapter 133). Greg Kuperberg found a subexponential quantum algorithm for the dihedral case in 2003, but no polynomial one is known. That gap is part of why lattice cryptography is trusted to resist quantum computers. Debated whether efficient algorithms exist.
What you now have
Simon’s problem and its classical lower bound, the quantum algorithm and GF(2) elimination, the hidden subgroup framework that unites Simon and Shor, and why non-abelian cases connect to lattice cryptography.
· · ·
Three questions to carry with you.
And one to work out. For , about how many classical queries does finding a collision take, ?
Sources: D. R. Simon, SIAM J. Comput. 26, 1474 (1997) (FOCS 1994). P. W. Shor, SIAM J. Comput. 26, 1484 (1997). A. Yu. Kitaev, arXiv:quant-ph/9511026 (1995). O. Regev, FOCS 2002, 520. G. Kuperberg, SIAM J. Comput. 35, 170 (2005). A. M. Childs and W. van Dam, Rev. Mod. Phys. 82, 1 (2010). Checked by code: for n = 4, exactly 2^(n−1) strings y satisfy y·s = 0; elimination recovers s from n − 1 independent samples.