111
Part Three · B · Algorithms

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 nn queries and any classical computer, even one allowed to guess, needs about 2n/22^{n/2}. 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 ff on nn-bit strings is promised to satisfy f(x)=f(y)f(x) = f(y) if and only if y=xy = x or y=x⊕sy = x\oplus s, for some unknown nonzero ss. Find ss. Classically you must find a collision, two inputs with the same output, and by the birthday paradox that takes about 2n/22^{n/2} queries. Simon proved no classical algorithm does fundamentally better. Established

The quantum algorithm

Prepare the uniform superposition, compute ff into a second register, and measure that register. The first register collapses to (∣x0⟩+∣x0⊕s⟩)/2(|x_0\rangle + |x_0\oplus s\rangle)/\sqrt2 for a random x0x_0. Apply Hadamards and measure: you get a random yy with y⋅s=0(mod2)y\cdot s = 0 \pmod 2, every such yy equally likely. Each run gives one linear equation for ss. Hide 11 (four bits) and a few times, or . Once you have n−1n - 1 independent equations, Gaussian elimination over GF(2) leaves a single nonzero solution: ss. About nn 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 HH of a group GG and different on different cosets; find HH. For Simon, GG is bit strings under XOR and H={0,s}H = \{0, s\}. For Shor, GG is the integers and HH the multiples of a period. Whenever GG is abelian, the Fourier transform over GG 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 2n/22^{n/2} 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.

What does each quantum run of Simon’s algorithm give?tap
A random y with y · s = 0 mod 2: one linear equation.
Why does classical search need about 2^(n/2) queries?tap
It must find a collision, which by the birthday paradox takes about the square root of the space.
Which HSP relates to lattice problems?tap
The dihedral hidden subgroup problem.

And one to work out. For n=40n = 40, about how many classical queries does finding a collision take, 2n/22^{n/2}?

queries ≈

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.

Next · Chapter 112
Quantum Fourier transform

The QFT performs an exponentially large Fourier transform in n² gates, but you can't read the output out.

Turn the page