Continuous-Time Quantum Walk
A quantum walk that evolves under a graph Hamiltonian, requiring no coin register.
Evolution under a graph Hamiltonian
A continuous-time quantum walk needs no coin. It takes the graph's adjacency matrix A (or Laplacian L) as a Hamiltonian and evolves the state under exp(-i A t). Each vertex is a basis state; the off-diagonal entries of A cause amplitude to flow between connected vertices continuously in time, with interference shaping the resulting distribution.
Contrast with the classical walk
The classical continuous-time random walk evolves a probability vector under exp(-L t), a stochastic process that relaxes to the stationary distribution. Replacing the real, dissipative exponential with the complex, unitary exp(-i A t) preserves norm and allows interference, again yielding ballistic rather than diffusive spreading on regular structures.
Key properties
- No coin register: the state space is just the vertices, using fewer qubits.
- Dynamics set entirely by the graph matrix and evolution time.
- Implemented via Hamiltonian simulation of a sparse matrix.
- Naturally suited to graphs where the adjacency structure is the object of interest.
Spatial search
For spatial search, add a marking term to the Hamiltonian: H = -gamma A - |w>
Notable results
A celebrated continuous-time walk result is exponential speedup for traversing a specially constructed glued-trees graph: the quantum walk crosses from entrance to exit exponentially faster than any classical algorithm using the same oracle. This is one of the clearest examples of an exponential quantum speedup from a walk. For search on general graphs the advantage is typically quadratic, matching the discrete-time model. Continuous-time walks are also universal for quantum computation.