117
Part Three · B · Algorithms

Quantum walks and element distinctness

A drunkard taking random steps left and right ends up, after a hundred steps, typically about ten steps from where he started: the spread grows as the square root of time. A quantum walker, taking steps in superposition, ends up typically about fifty-four steps away: the spread grows in proportion to time, like a wave. On some specially built graphs the quantum walker reaches the far side exponentially faster than any classical algorithm can. Quantum walks are a second toolbox for algorithms, alongside the Fourier transform.

On the plate: a quantum walk and a classical random walk, starting from the same point.

A coined walk on a line

Give the walker a two-state “coin”. Each step: apply a Hadamard to the coin, then move left if the coin is 0 and right if 1, all in superposition. Paths interfere. Yakir Aharonov, Luiz Davidovich and Nicim Zagury introduced quantum walks in 1993. Run 60 steps. The quantum distribution, amber, has two sharp peaks near ±t/2\pm t/\sqrt2 and a spread of about 0.54t0.54t; the classical one, white, is a bell curve of width t\sqrt t. Quantum walks spread ballistically; random walks diffusively. Established

Continuous time, and an exponential speedup

Edward Farhi and Sam Gutmann defined continuous-time quantum walks in 1998: evolve with the graph’s adjacency matrix as the Hamiltonian, e−iAte^{-iAt}. In 2003 Andrew Childs and colleagues built a graph of two binary trees glued together at their leaves with a random cycle, with entrance and exit at the two roots. A quantum walk from one root reaches the other in time polynomial in the depth. Any classical algorithm, even one allowed to explore the graph cleverly, gets lost in the exponentially many middle vertices. It was an exponential oracle separation from a physical-looking process. Established

Element distinctness

Given NN numbers, are any two equal? Classically you must look at all of them: NN queries. Grover search over pairs gives about N3/4N^{3/4}. Andris Ambainis found in 2004 a quantum walk on a graph whose vertices are subsets of N2/3N^{2/3} elements, giving O(N2/3)O(N^{2/3}) queries, which is optimal. Mario Szegedy’s 2004 framework turns any classical Markov-chain search into a quantum walk with quadratically fewer steps in its spectral gap. Established

What you now have

Discrete-time coined walks and continuous-time walks, ballistic versus diffusive spreading, the glued-trees exponential speedup, Ambainis’s N2/3N^{2/3} algorithm for element distinctness, and Szegedy’s quantization of Markov chains.

· · ·

Three questions to carry with you.

How does a quantum walk’s spread grow?tap
In proportion to t, ballistically; a classical walk spreads as √t.
What makes the glued-trees graph hard classically?tap
The exponentially many middle vertices; a classical walker cannot find the exit efficiently.
How many queries does element distinctness need quantumly?tap
Θ(N^(2/3)), by Ambainis’s quantum walk.

And one to work out. A classical random walk of ±1 steps: what is its spread t\sqrt t after 100 steps?

σ =

Sources: Y. Aharonov, L. Davidovich and N. Zagury, Phys. Rev. A 48, 1687 (1993). E. Farhi and S. Gutmann, Phys. Rev. A 58, 915 (1998). A. M. Childs et al., Proc. 35th ACM STOC, 59 (2003). A. Ambainis, SIAM J. Comput. 37, 210 (2007). M. Szegedy, FOCS 2004, 32. Checked by code: Hadamard walk spread 54.1 after 100 steps (0.541 t), total probability 1; classical spread 10.

Next · Chapter 118
Hamiltonian simulation: Trotter, qDRIFT, LCU, qubitization

This is the reason Feynman proposed quantum computers in the first place.

Turn the page