Discrete-Time Quantum Walk

A coined quantum walk whose step alternates a coin operator with a conditional shift, producing ballistic spreading.

Coin and shift

A discrete-time quantum walk uses two registers: a position register for the current vertex and a coin register indexing the possible moves. Each step applies a coin operator C to the coin (a unitary such as the Hadamard or Grover coin), then a shift operator S that moves the walker to the neighbor selected by the coin state. The full step is U = S(I tensor C).

Ballistic spreading

On an infinite line, a classical random walk spreads diffusively: the standard deviation of position grows as sqrt(t). The quantum walk spreads ballistically, with standard deviation growing linearly in t, a quadratic speedup in spreading rate. The probability distribution is bimodal, peaking near the extremes rather than the center, a signature of interference among amplitude paths.

import numpy as np
# one step of a Hadamard walk on a cycle of length N
def step(psi, N):
    # psi shape (N, 2): position x coin
    H = (1/np.sqrt(2))*np.array([[1,1],[1,-1]])
    psi = psi @ H.T                 # apply coin
    out = np.zeros_like(psi)
    out[:,0] = np.roll(psi[:,0], 1) # coin 0 -> move +1
    out[:,1] = np.roll(psi[:,1],-1) # coin 1 -> move -1
    return out

Coin choice matters

Different coins produce different dynamics. The Hadamard coin gives an asymmetric distribution unless the initial coin state is chosen symmetrically. The Grover coin generalizes to higher-degree vertices and is common in search algorithms because it treats all directions symmetrically except the marked one. The coin dimension equals the vertex degree.

Use in search

In quantum walk search, a marked vertex uses a modified coin (often minus identity) while unmarked vertices use the standard coin. Iterating rotates amplitude toward the marked set, giving a quadratic speedup in locating it. The discrete-time model is well suited to regular graphs and lattices, and it is polynomially equivalent to the continuous-time and Szegedy formulations for search purposes.