Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 39 ยท Projects and Practice

Project: A Quantum Walk Simulator

Build a discrete-time quantum walk on a line: coin and shift operators, ballistic spreading, interference patterns, and decoherence turning it classical.

A random walk is the process behind diffusion, Brownian motion and many algorithms: at each step you flip a coin and move left or right. After t steps, the walker is typically about sqrt(t) away from the start. A quantum walk replaces the coin flip with a quantum coin in superposition and lets the paths interfere. The walker then spreads linearly with time, a quadratic speed-up in spreading, and that idea underlies quantum search algorithms and universal quantum computation models.

In this project you build a discrete-time quantum walk on a line from scratch, measure its spreading against the classical walk, look at the interference pattern, and then add decoherence to watch the walk turn classical.

The model

The state lives on two quantum systems:

  • a coin qubit with basis states |L> and |R>, and
  • a position register with states |x>, x an integer on the line.

One step is two operations:

  1. Coin flip: apply a unitary C to the coin, usually the Hadamard gate.
  2. Conditional shift: if the coin says R, move x -> x + 1; if L, move x -> x - 1.

The state is an array psi[position, coin] of complex amplitudes. The probability of finding the walker at x is |psi[x, 0]|^2 + |psi[x, 1]|^2. There is no randomness during the evolution, only at the final measurement.

Build the simulator

Python Hadamard walk vs classical random walk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The quantum standard deviation grows proportionally to t (about 0.46 t for the Hadamard walk from a definite coin state; the root-mean-square distance from the origin is 0.54 t), the classical one only as sqrt(t). The probabilities add up to 1 at all times, since the evolution is unitary.

The asymmetry and the interference pattern

Look at the distribution after 30 steps. The picture is not a bell curve: it has strong peaks near +-t/sqrt(2) and a dip at the center. It is also asymmetric when the initial coin is |0> (L), because the Hadamard gate treats |0> and |1> differently, so left-moving and right-moving paths interfere differently.

Python The walk's interference pattern as text bars

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Starting in |L> pushes most of the probability to the left, starting in |R> to the right, and the symmetric initial coin gives a mirror-symmetric pattern. The walk is a good example of quantum interference doing computational work: amplitudes of different paths into the same position cancel or reinforce.

Decoherence: from quantum to classical

Real devices suffer from noise and decoherence. If the coin is measured (or dephased) with some probability after each step, interference between paths is destroyed. At full decoherence you get the classical random walk and its sqrt(t) spreading.

To model this, use the density matrix of the coin at each position, or simply an ensemble average over runs where each step, with probability p, the coin is measured (collapsed to |L> or |R> with its Born probabilities). The ensemble is easy to simulate exactly by tracking the density matrix rho[x, c, c'] for the coin at each position:

Python Decoherence turns the quantum walk into a classical one

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

As the dephasing probability grows from 0 to 1, the standard deviation shrinks from about 0.46 t to the classical sqrt(t). The transition happens quickly even for small noise at larger t, which is why quantum walk advantages demand good coherence.

Why quantum walks matter

  • Spatial search. A quantum walk on a grid or hypercube can find a marked vertex in O(sqrt(N)) steps, like Grover's algorithm (Grover's search), for graphs where classical random walks need O(N).
  • Universal computation. Continuous-time and discrete quantum walks on suitable graphs can implement any quantum algorithm.
  • Exponential speed-ups. There are graph traversal problems ("glued trees") where quantum walks beat any classical algorithm exponentially.
  • Physics models. Quantum walks simulate transport in photosynthesis models, topological phases, and Dirac-like particles.

Extensions

  1. Different coins. Use the Grover coin on more than 2 directions, or a rotation [[cos a, sin a], [-sin a, cos a]], and study how the spreading speed depends on the angle.
  2. Walk on a cycle. Make positions wrap around and study the mixing time against the classical O(N^2).
  3. Absorbing boundary. Remove probability that reaches the ends and compute the hitting probability.
  4. 2D lattice with a 4-state coin: check how the distribution spreads.
  5. Compile to gates. Write the shift as an incrementer (Toffoli and CNOT gates) acting on a binary position register.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does the spread of a Hadamard quantum walk scale with the number of steps t?

    The standard deviation grows proportionally to t, a quadratic improvement over sqrt(t).
  2. 2. Which two operations make up one step of the discrete quantum walk?

    The coin creates a superposition of directions; the shift moves each component accordingly.
  3. 3. What happens to the walk if the coin is measured after every step?

    Measurement destroys the interference between paths, leaving classical randomness.
  4. 4. Why is the Hadamard walk from |L> asymmetric?

    A symmetric initial coin such as (|L> + i|R>)/sqrt(2) gives a symmetric distribution.

Summary

  • A discrete quantum walk alternates a coin unitary and a conditional shift on a coin-plus-position state.
  • Interference makes the walker spread linearly in time with a characteristic double-peaked distribution; classical walks spread as sqrt(t).
  • Decoherence interpolates between the two behaviors.
  • Quantum walks underlie spatial search algorithms and are a universal model of quantum computation.

Next: Practice Problems with Worked Solutions