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 and a spread of about ; the classical one, white, is a bell curve of width . 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, . 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 numbers, are any two equal? Classically you must look at all of them: queries. Grover search over pairs gives about . Andris Ambainis found in 2004 a quantum walk on a graph whose vertices are subsets of elements, giving 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 algorithm for element distinctness, and Szegedy’s quantization of Markov chains.
· · ·
Three questions to carry with you.
And one to work out. A classical random walk of ±1 steps: what is its spread 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.