Curriculum / Quantum Algorithms / Quantum Walks
Quantum Walks
Understand discrete quantum walks and how they power search algorithms.
Quantum Walks
A quantum walk is the quantum analogue of a classical random walk. Where a classical walker randomly steps left or right, a quantum walker maintains superposition over all paths simultaneously: and the interference between paths creates dramatically different behavior.
Classical vs quantum walk:
A classical random walk on a line spreads out as √t after t steps (standard deviation σ = √t). A quantum walk spreads as t: quadratically faster. This is not just a speed improvement; the entire probability distribution is different.
| Property | Classical random walk | Quantum walk |
|---|---|---|
| Spread after t steps | σ = √t | σ = t |
| Distribution shape | Gaussian (bell curve) | Bimodal (peaks at ±t) |
| Interference | No | Yes (key to speedup) |
| Applications | Brownian motion, diffusion | Element distinctness, graph search |
The coin-and-shift model:
A discrete quantum walk uses:
- 1.Coin qubit: determines direction of movement (left=|0⟩, right=|1⟩)
- 2.Position register: the current location on the graph
- 3.Coin operation: applies a Hadamard to the coin qubit (both directions in superposition)
- 4.Shift operation: moves the walker: if coin=|0⟩ move left, if coin=|1⟩ move right
The quantum walker accumulates phases and interferes with itself: leading to concentration at the edges rather than the center of the distribution.
Starting in |coin=0, position=0⟩, the first coin flip gives (|0⟩+|1⟩)/√2 ⊗ |0⟩. The shift then moves the walker to (|0⟩|left⟩ + |1⟩|right⟩)/√2. Recombining paths pick up relative phases, but for the first two steps the position statistics still match a classical walk exactly; the two-step walk you build in this lesson's editor shows exactly that 50/50 result. From step 3 onward the phases stop cancelling: interference suppresses the center, and after many steps probability concentrates near ±t instead of 0. That is the quantum speedup, linear vs square-root spread, visible once the position register is big enough to hold it.
This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.
How this lesson works
A hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.
Part of: Quantum Algorithms
Learn the algorithms that make quantum computers powerful.
This lesson is part of Pro
Unlock Quantum Algorithms and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.