The Real Complexity of Quantum Walks

Introduction

Flip a coin. Heads: step right. Tails: step left. Repeat a thousand times. This is the random walk — one of the most studied objects in mathematics, and the engine behind diffusion, Brownian motion and countless algorithms.

Now replace the coin with a quantum coin. The walker no longer steps definitively left or right; it steps both ways at once, holding a superposition of positions. After T steps the quantum walk's probability distribution looks nothing like the classical bell curve centred at the origin — it forms two sharp peaks racing outward, with the walker reaching distance $O(T)$ instead of the classical $O(\sqrt{T})$ .

That quadratic difference — from √T to T — is not a rounding error. It is the heart of a family of quantum algorithms that find a marked item in a haystack of N elements in $O(\sqrt{N})$ steps, where any classical algorithm needs Ω(N). Quantum walks power Grover's search, the element-distinctness algorithm (Ambainis, 2003), and quantum simulations of physical systems.

The concept was formalised independently by Aharonov, Ambainis, Kempe and Vazirani (2001) and by Farhi and Gutmann (1998). It sits at the intersection of quantum information theory, graph theory and algorithm design — a deceptively simple modification to a centuries-old idea that unlocks genuine computational power.

Try It: Walk the Line

Use the controls below to run a discrete-time quantum walk on a line of positions. The quantum walker starts at position 0 with the coin in state |↑⟩. The classical walker starts at 0 and flips a fair coin each step. Adjust T (number of steps) and press Run to see both distributions side by side.

<p class="hint">A <b>discrete-time quantum walk</b> on a line uses a Hadamard coin.
    Set the number of steps T and press <b>Run</b> to see both distributions.</p>
<div class="controls">
  <label>Steps T: <span id="tval">40</span>
    <input type="range" id="tslider" min="10" max="80" step="5" value="40">
  </label>
  <button id="runbtn" type="button">Run</button>
  <button id="resetbtn" type="button" class="ghost">Reset</button>
</div>
<canvas id="chart" width="560" height="300"></canvas>
<div class="legend">
  <span class="dot q"></span><span>Quantum (|ψ|²)</span>
  <span class="dot c"></span><span>Classical (prob)</span>
</div>
<div class="stats" id="stats"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.controls { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap; margin-bottom: .8rem; }
label { font-size: .9rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 130px; cursor: pointer; }
button { font: 600 14px system-ui; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; max-width: 100%; border: 1px solid #dde3e9; border-radius: 8px; background: #fafbfc; }
.legend { display: flex; gap: 1rem; align-items: center; margin-top: .5rem; font-size: .85rem; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%; }
.dot.q { background: #e63946; }
.dot.c { background: #457b9d; }
.stats { font-size: .85rem; color: #555; margin-top: .4rem; min-height: 1.2em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Discrete-time quantum walk on a line with Hadamard coin.
// State: amplitudes psi[pos][spin] where spin 0=up, 1=down, pos in [-T..T].
// Hadamard coin: H|up> = (|up>+|down>)/√2, H|down> = (|up>-|down>)/√2
// Shift: |up,pos> -> |up,pos+1>; |down,pos> -> |down,pos-1>
// Initial state: |pos=0, spin=up>

const slider = document.getElementById('tslider');
const tval   = document.getElementById('tval');
const stats  = document.getElementById('stats');
const canvas = document.getElementById('chart');
const ctx    = canvas.getContext('2d');

slider.addEventListener('input', () => { tval.textContent = slider.value; });
document.getElementById('runbtn').addEventListener('click', runWalk);
document.getElementById('resetbtn').addEventListener('click', () => {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  stats.textContent = '';
});

function runWalk() {
  const T = parseInt(slider.value);
  const SIZE = 2 * T + 1; // positions -T..T
  const OFF = T;           // index offset so pos p -> index p+OFF

  // Quantum walk: psi[pos][spin], complex numbers as [re, im]
  // Flatten to two arrays: re[pos][spin], im[pos][spin]
  const re = Array.from({length: SIZE}, () => [0, 0]);
  const im = Array.from({length: SIZE}, () => [0, 0]);
  // Initial: pos=0 (index OFF), spin=up (0), amplitude 1
  re[OFF][0] = 1;

  for (let t = 0; t < T; t++) {
    const re2 = Array.from({length: SIZE}, () => [0, 0]);
    const im2 = Array.from({length: SIZE}, () => [0, 0]);
    const H = 1 / Math.SQRT2;
    for (let p = 0; p < SIZE; p++) {
      // Apply Hadamard to spin, then shift
      // H|up>  = H*(|up>+|down>)
      // H|down> = H*(|up>-|down>)
      // After coin: new_up = H*(old_up + old_down), new_down = H*(old_up - old_down)
      const rUp  = H * (re[p][0] + re[p][1]);
      const iUp  = H * (im[p][0] + im[p][1]);
      const rDn  = H * (re[p][0] - re[p][1]);
      const iDn  = H * (im[p][0] - im[p][1]);
      // Shift: up goes right (+1), down goes left (-1)
      if (p + 1 < SIZE) { re2[p + 1][0] += rUp; im2[p + 1][0] += iUp; }
      if (p - 1 >= 0)   { re2[p - 1][1] += rDn; im2[p - 1][1] += iDn; }
    }
    for (let p = 0; p < SIZE; p++) { re[p] = re2[p]; im[p] = im2[p]; }
  }

  // Quantum probability: |psi_up|^2 + |psi_down|^2 per position
  const qProb = new Array(SIZE).fill(0);
  for (let p = 0; p < SIZE; p++) {
    qProb[p] = re[p][0]**2 + im[p][0]**2 + re[p][1]**2 + im[p][1]**2;
  }

  // Classical random walk: exact distribution via binomial
  // After T steps on a line, prob(pos=k) = C(T,(T+k)/2) / 2^T if T+k even else 0
  const cProb = new Array(SIZE).fill(0);
  const logHalf = Math.log(0.5);
  // Use log-space to avoid overflow
  function logBinom(n, k) {
    if (k < 0 || k > n) return -Infinity;
    let r = 0;
    for (let i = 0; i < k; i++) r += Math.log(n - i) - Math.log(i + 1);
    return r;
  }
  for (let p = 0; p < SIZE; p++) {
    const pos = p - OFF; // position in -T..T
    const steps = (T + pos);
    if (steps % 2 !== 0 || steps < 0 || steps > 2 * T) continue;
    const rightSteps = steps / 2;
    const logP = logBinom(T, rightSteps) + T * logHalf;
    cProb[p] = Math.exp(logP);
  }

  // Compute stats
  let qStd = 0, cStd = 0;
  for (let p = 0; p < SIZE; p++) {
    const pos = p - OFF;
    qStd += pos * pos * qProb[p];
    cStd += pos * pos * cProb[p];
  }
  qStd = Math.sqrt(qStd); cStd = Math.sqrt(cStd);

  drawChart(T, qProb, cProb, OFF);
  stats.textContent =
    fmt('Quantum std dev ≈ %qStd% ≈ 0.54·T = %v%  |  Classical std dev ≈ %cStd% ≈ √T = %sqrt%  |  Speedup factor ≈ %v2%x', { qStd: qStd.toFixed(1), v: (0.5413 * T).toFixed(1), cStd: cStd.toFixed(1), sqrt: Math.sqrt(T).toFixed(1), v2: (qStd / cStd).toFixed(2) });
}

function drawChart(T, qProb, cProb, OFF) {
  const W = canvas.width, H = canvas.height;
  const pad = { l: 36, r: 10, t: 18, b: 28 };
  const plotW = W - pad.l - pad.r;
  const plotH = H - pad.t - pad.b;
  ctx.clearRect(0, 0, W, H);

  // Find max probability for scaling
  const maxProb = Math.max(...qProb, ...cProb, 0.01);

  // Axes
  ctx.strokeStyle = '#aaa'; ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(pad.l, pad.t); ctx.lineTo(pad.l, pad.t + plotH);
  ctx.lineTo(pad.l + plotW, pad.t + plotH);
  ctx.stroke();

  // Axis labels
  ctx.fillStyle = '#666'; ctx.font = '11px system-ui'; ctx.textAlign = 'center';
  const labelStep = T <= 20 ? 5 : T <= 40 ? 10 : 20;
  for (let pos = -T; pos <= T; pos += labelStep) {
    const x = pad.l + ((pos + T) / (2 * T)) * plotW;
    ctx.fillText(pos, x, H - 6);
  }
  ctx.textAlign = 'right';
  ctx.fillText('0', pad.l - 4, pad.t + plotH + 4);

  // Y axis ticks
  for (let tick = 0; tick <= 4; tick++) {
    const yVal = (maxProb * tick / 4);
    const y = pad.t + plotH - (yVal / maxProb) * plotH;
    ctx.fillStyle = '#aaa'; ctx.textAlign = 'right';
    ctx.fillText(yVal.toFixed(3), pad.l - 4, y + 4);
    ctx.strokeStyle = '#eee'; ctx.beginPath(); ctx.moveTo(pad.l, y); ctx.lineTo(pad.l + plotW, y); ctx.stroke();
  }

  const SIZE = 2 * T + 1;

  // Draw classical (blue bars, behind)
  ctx.fillStyle = 'rgba(69,123,157,0.45)';
  const barW = Math.max(1, plotW / SIZE - 1);
  for (let p = 0; p < SIZE; p++) {
    if (cProb[p] < 1e-12) continue;
    const x = pad.l + (p / SIZE) * plotW;
    const h = (cProb[p] / maxProb) * plotH;
    ctx.fillRect(x, pad.t + plotH - h, barW, h);
  }

  // Draw quantum (red line)
  ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2;
  ctx.beginPath();
  for (let p = 0; p < SIZE; p++) {
    const x = pad.l + ((p + 0.5) / SIZE) * plotW;
    const y = pad.t + plotH - (qProb[p] / maxProb) * plotH;
    p === 0 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
  }
  ctx.stroke();

  // Title
  ctx.fillStyle = '#333'; ctx.font = '12px system-ui'; ctx.textAlign = 'center';
  ctx.fillText(fmt('Position distribution after T=%T% steps', { T: T }), pad.l + plotW / 2, pad.t - 4);
}

// Run on load with default T=40
runWalk();

<p class="hint">A <b>discrete-time quantum walk</b> on a line uses a Hadamard coin.
    Set the number of steps T and press <b>Run</b> to see both distributions.</p>
<div class="controls">
  <label>Steps T: <span id="tval">40</span>
    <input type="range" id="tslider" min="10" max="80" step="5" value="40">
  </label>
  <button id="runbtn" type="button">Run</button>
  <button id="resetbtn" type="button" class="ghost">Reset</button>
</div>
<canvas id="chart" width="560" height="300"></canvas>
<div class="legend">
  <span class="dot q"></span><span>Quantum (|ψ|²)</span>
  <span class="dot c"></span><span>Classical (prob)</span>
</div>
<div class="stats" id="stats"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.controls { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap; margin-bottom: .8rem; }
label { font-size: .9rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 130px; cursor: pointer; }
button { font: 600 14px system-ui; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; max-width: 100%; border: 1px solid #dde3e9; border-radius: 8px; background: #fafbfc; }
.legend { display: flex; gap: 1rem; align-items: center; margin-top: .5rem; font-size: .85rem; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%; }
.dot.q { background: #e63946; }
.dot.c { background: #457b9d; }
.stats { font-size: .85rem; color: #555; margin-top: .4rem; min-height: 1.2em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Discrete-time quantum walk on a line with Hadamard coin.
// State: amplitudes psi[pos][spin] where spin 0=up, 1=down, pos in [-T..T].
// Hadamard coin: H|up> = (|up>+|down>)/√2, H|down> = (|up>-|down>)/√2
// Shift: |up,pos> -> |up,pos+1>; |down,pos> -> |down,pos-1>
// Initial state: |pos=0, spin=up>

const slider = document.getElementById('tslider');
const tval   = document.getElementById('tval');
const stats  = document.getElementById('stats');
const canvas = document.getElementById('chart');
const ctx    = canvas.getContext('2d');

slider.addEventListener('input', () => { tval.textContent = slider.value; });
document.getElementById('runbtn').addEventListener('click', runWalk);
document.getElementById('resetbtn').addEventListener('click', () => {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  stats.textContent = '';
});

function runWalk() {
  const T = parseInt(slider.value);
  const SIZE = 2 * T + 1; // positions -T..T
  const OFF = T;           // index offset so pos p -> index p+OFF

  // Quantum walk: psi[pos][spin], complex numbers as [re, im]
  // Flatten to two arrays: re[pos][spin], im[pos][spin]
  const re = Array.from({length: SIZE}, () => [0, 0]);
  const im = Array.from({length: SIZE}, () => [0, 0]);
  // Initial: pos=0 (index OFF), spin=up (0), amplitude 1
  re[OFF][0] = 1;

  for (let t = 0; t < T; t++) {
    const re2 = Array.from({length: SIZE}, () => [0, 0]);
    const im2 = Array.from({length: SIZE}, () => [0, 0]);
    const H = 1 / Math.SQRT2;
    for (let p = 0; p < SIZE; p++) {
      // Apply Hadamard to spin, then shift
      // H|up>  = H*(|up>+|down>)
      // H|down> = H*(|up>-|down>)
      // After coin: new_up = H*(old_up + old_down), new_down = H*(old_up - old_down)
      const rUp  = H * (re[p][0] + re[p][1]);
      const iUp  = H * (im[p][0] + im[p][1]);
      const rDn  = H * (re[p][0] - re[p][1]);
      const iDn  = H * (im[p][0] - im[p][1]);
      // Shift: up goes right (+1), down goes left (-1)
      if (p + 1 < SIZE) { re2[p + 1][0] += rUp; im2[p + 1][0] += iUp; }
      if (p - 1 >= 0)   { re2[p - 1][1] += rDn; im2[p - 1][1] += iDn; }
    }
    for (let p = 0; p < SIZE; p++) { re[p] = re2[p]; im[p] = im2[p]; }
  }

  // Quantum probability: |psi_up|^2 + |psi_down|^2 per position
  const qProb = new Array(SIZE).fill(0);
  for (let p = 0; p < SIZE; p++) {
    qProb[p] = re[p][0]**2 + im[p][0]**2 + re[p][1]**2 + im[p][1]**2;
  }

  // Classical random walk: exact distribution via binomial
  // After T steps on a line, prob(pos=k) = C(T,(T+k)/2) / 2^T if T+k even else 0
  const cProb = new Array(SIZE).fill(0);
  const logHalf = Math.log(0.5);
  // Use log-space to avoid overflow
  function logBinom(n, k) {
    if (k < 0 || k > n) return -Infinity;
    let r = 0;
    for (let i = 0; i < k; i++) r += Math.log(n - i) - Math.log(i + 1);
    return r;
  }
  for (let p = 0; p < SIZE; p++) {
    const pos = p - OFF; // position in -T..T
    const steps = (T + pos);
    if (steps % 2 !== 0 || steps < 0 || steps > 2 * T) continue;
    const rightSteps = steps / 2;
    const logP = logBinom(T, rightSteps) + T * logHalf;
    cProb[p] = Math.exp(logP);
  }

  // Compute stats
  let qStd = 0, cStd = 0;
  for (let p = 0; p < SIZE; p++) {
    const pos = p - OFF;
    qStd += pos * pos * qProb[p];
    cStd += pos * pos * cProb[p];
  }
  qStd = Math.sqrt(qStd); cStd = Math.sqrt(cStd);

  drawChart(T, qProb, cProb, OFF);
  stats.textContent =
    fmt('Quantum std dev ≈ %qStd% ≈ 0.54·T = %v%  |  Classical std dev ≈ %cStd% ≈ √T = %sqrt%  |  Speedup factor ≈ %v2%x', { qStd: qStd.toFixed(1), v: (0.5413 * T).toFixed(1), cStd: cStd.toFixed(1), sqrt: Math.sqrt(T).toFixed(1), v2: (qStd / cStd).toFixed(2) });
}

function drawChart(T, qProb, cProb, OFF) {
  const W = canvas.width, H = canvas.height;
  const pad = { l: 36, r: 10, t: 18, b: 28 };
  const plotW = W - pad.l - pad.r;
  const plotH = H - pad.t - pad.b;
  ctx.clearRect(0, 0, W, H);

  // Find max probability for scaling
  const maxProb = Math.max(...qProb, ...cProb, 0.01);

  // Axes
  ctx.strokeStyle = '#aaa'; ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(pad.l, pad.t); ctx.lineTo(pad.l, pad.t + plotH);
  ctx.lineTo(pad.l + plotW, pad.t + plotH);
  ctx.stroke();

  // Axis labels
  ctx.fillStyle = '#666'; ctx.font = '11px system-ui'; ctx.textAlign = 'center';
  const labelStep = T <= 20 ? 5 : T <= 40 ? 10 : 20;
  for (let pos = -T; pos <= T; pos += labelStep) {
    const x = pad.l + ((pos + T) / (2 * T)) * plotW;
    ctx.fillText(pos, x, H - 6);
  }
  ctx.textAlign = 'right';
  ctx.fillText('0', pad.l - 4, pad.t + plotH + 4);

  // Y axis ticks
  for (let tick = 0; tick <= 4; tick++) {
    const yVal = (maxProb * tick / 4);
    const y = pad.t + plotH - (yVal / maxProb) * plotH;
    ctx.fillStyle = '#aaa'; ctx.textAlign = 'right';
    ctx.fillText(yVal.toFixed(3), pad.l - 4, y + 4);
    ctx.strokeStyle = '#eee'; ctx.beginPath(); ctx.moveTo(pad.l, y); ctx.lineTo(pad.l + plotW, y); ctx.stroke();
  }

  const SIZE = 2 * T + 1;

  // Draw classical (blue bars, behind)
  ctx.fillStyle = 'rgba(69,123,157,0.45)';
  const barW = Math.max(1, plotW / SIZE - 1);
  for (let p = 0; p < SIZE; p++) {
    if (cProb[p] < 1e-12) continue;
    const x = pad.l + (p / SIZE) * plotW;
    const h = (cProb[p] / maxProb) * plotH;
    ctx.fillRect(x, pad.t + plotH - h, barW, h);
  }

  // Draw quantum (red line)
  ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2;
  ctx.beginPath();
  for (let p = 0; p < SIZE; p++) {
    const x = pad.l + ((p + 0.5) / SIZE) * plotW;
    const y = pad.t + plotH - (qProb[p] / maxProb) * plotH;
    p === 0 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
  }
  ctx.stroke();

  // Title
  ctx.fillStyle = '#333'; ctx.font = '12px system-ui'; ctx.textAlign = 'center';
  ctx.fillText(fmt('Position distribution after T=%T% steps', { T: T }), pad.l + plotW / 2, pad.t - 4);
}

// Run on load with default T=40
runWalk();

Result

Console

Notice how the classical distribution forms a bell curve centred at 0 — the walker diffuses, with standard deviation ≈ √T. The quantum distribution builds two sharp peaks near ±0.54·T, separated by a near-empty centre. The quantum walker has literally spread far more in the same number of steps — the speedup ratio grows as √T. This is the quadratic speedup made visible: to reach the same distance, the classical walker needs $T^{2}$ steps while the quantum walker needs only T.

The Real Complexity

The visual drama of the twin peaks translates directly into provable complexity separations:

Unstructured search ( $O(\sqrt{N})$ ): Grover's algorithm — arguably the canonical quantum walk on a complete graph — finds a marked element in $O(\sqrt{N})$ oracle calls. This is provably optimal for quantum computers, and provably better than any classical algorithm's Ω(N) lower bound.
Element distinctness ( $O(N^{2/3})$ ): Given N numbers, decide whether any two are equal. Classically this requires Ω(N) comparisons. Using a quantum walk on a Johnson graph, Ambainis (2003) solved it in $O(N^{2/3})$ — a strict quantum speedup that cannot be matched classically.
Triangle finding and matrix product verification: Quantum walks on structured graphs give sub-quadratic algorithms for problems where classical algorithms seem stuck at Ω(N²).
Continuous-time quantum walks: the Farhi–Gutmann model replaces the step-by-step coin with a Hamiltonian evolution. It underlies proposals for quantum simulation and adiabatic computation.

These speedups are not heuristic improvements — they come with lower-bound proofs showing no classical algorithm can match them using the same oracle model. The quantum walk framework also connects directly to Grover search and quantum simulation: the walk IS the search, and simulating a physical quantum system is a natural quantum walk on the system's configuration space.

One important caveat: the speedups are defined in the query complexity model (counting oracle accesses), not raw gate operations. Converting a quantum walk algorithm to a fault-tolerant circuit introduces polylogarithmic overheads, but the asymptotic separation survives.

Where It Matters

The quadratic speedup from walking quantum is not merely theoretical:

Quantum search and optimisation: every quantum search algorithm, from Grover's to amplitude amplification, can be viewed as a quantum walk on an appropriate graph. This unified framework makes it easier to design and prove new algorithms.
Quantum chemistry: simulating a molecule's electron structure is a quantum walk on the molecule's Hilbert space. Early fault-tolerant quantum computers will likely use quantum walks to achieve this, providing exponential speedups over classical methods for large molecules.
Photonic experiments: a photon passing through a beamsplitter network is a physical quantum walk. Labs have built one- and two-dimensional quantum walks with photons, atoms in optical lattices and trapped ions — demonstrating the speedup in hardware.
Graph problems: quantum walks on graphs offer quadratic or better speedups for connectivity, triangle detection and certain optimisation problems, with implications for network analysis and logistics.
Quantum machine learning: walk-based subroutines appear in proposals for faster linear-algebra primitives, though the practical advantage depends heavily on data-loading assumptions.

As Grover's search showed, even a quadratic speedup is meaningful at scale: a database of $10^{18}$ entries that would take a classical computer a billion seconds to search could be searched in ~31,623 seconds on a quantum machine walking through it.

Conclusion

The quantum walk is one of the cleanest ideas in quantum computing: swap a classical coin for a quantum one, let the walker be in superposition, and watch interference do the heavy lifting. The result is a distribution that races outward with ballistic speed instead of diffusing slowly — twin peaks at ±T/√2 instead of a bell curve at 0.

That geometric difference, visible in any simulation, is the same gap that gives Grover's search its quadratic speedup, that lets Ambainis solve element distinctness in $O(N^{2/3})$ , and that will one day let quantum computers simulate molecules classical machines cannot touch.

The walk is simple. The physics is real. The speedup is proven. Few ideas in computer science pack so much into a single changed premise.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quantum-walks/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Quantum Walks

How a quantum coin makes exploration quadratically faster