Quantum walks: the quantum version of a random walk

Picture a walker who steps left or right on a coin toss. In a quantum walk, interference spreads the walker much faster than in the classical version. Meet the idea behind many search algorithms.

The classical random walk

A walker standing on a line tosses a coin at every step: heads means one step right, tails one step left. Because the steps partly cancel each other, the walker moves away from the start slowly: after t steps the typical distance is only about √t. After 50 steps that is about 7 steps.

The quantum walk

In a quantum walk the coin toss is replaced by a “coin qubit” that gets an H gate at every step. The walker then shifts right or left depending on the value of the coin qubit. Since nothing is measured, the walker moves in a superposition of all paths, and paths that reach the same point interfere.

Interference makes the paths cancel at the points in the middle and reinforce each other at the points near the ends. As a result the walker spreads at a speed proportional to t instead of √t. The code below computes a 50-step quantum walk: the typical distance is about 27 steps instead of the 7 of the classical walk.

import numpy as np

steps = 50
size = 2 * steps + 1
psi = np.zeros((size, 2), dtype=complex)        # position x coin qubit
psi[steps] = [1 / np.sqrt(2), 1j / np.sqrt(2)]  # start in the middle with a balanced coin
H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)

for _ in range(steps):
    psi = psi @ H.T                  # H on the coin qubit
    new = np.zeros_like(psi)
    new[:-1, 0] = psi[1:, 0]         # coin 0: shift left
    new[1:, 1] = psi[:-1, 1]         # coin 1: shift right
    psi = new

prob = (abs(psi) ** 2).sum(axis=1)
x = np.arange(size) - steps
print(np.sqrt((prob * x**2).sum()), np.sqrt(steps))   # about 27.1 and 7.1

What are they good for?

Quantum walks are a building block of many quantum algorithms. Grover search can also be written as a quantum walk on a graph. The algorithm Ambainis found in 2003 decides whether a list contains two equal elements with fewer queries than classical methods. In the same year Childs and colleagues showed that on a specially built graph a quantum walk gets through exponentially faster than any classical method.

Today quantum walks are studied for search, graph problems and the simulation of physical systems; they have also been demonstrated experimentally on photonic devices.

Try it yourself

What spreads a quantum walk is interference. In this example two H gates come one after the other and the two paths to 1 cancel each other: the result is always 0. In a walk, too, the paths to some points cancel like this while those to others reinforce each other.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

In a classical random walk the typical distance grows with √t, in a quantum walk with t.
In a quantum walk the coin qubit is mixed with H and the paths interfere.
After 50 steps a quantum walker is about 27 steps away, a classical walker about 7.
Many search and graph algorithms are based on quantum walks.

Test yourself

In a classical random walk, about how many steps away is the walker after 100 steps?

Show the answer

10. In a classical walk the typical distance is √t: √100 = 10. A quantum walk spreads in proportion to t.

← QAOA: a quantum approach to optimisation problems · Where is the quantum advantage? The big picture of algorithms →