Continuous-Time Quantum Walks

The discrete-time quantum walk uses an explicit coin-flip-and-shift step applied repeatedly at integer times. A complementary model, introduced by Farhi and Gutmann (1998), evolves the walker continuously in time through a Hamiltonian. No coin register is needed; the graph itself encodes the dynamics.

From adjacency matrix to Hamiltonian

Given an undirected graph $G = (V, E)$ with $n = |V|$ vertices, label the vertex states $|0\rangle, |1\rangle, \ldots, |n-1\rangle$ . The walker's Hilbert space is $\mathbb{C}^n$ . The continuous-time quantum walk (CTQW) is governed by the Schrödinger equation

$i\hbar \frac{d}{dt}|\psi(t)\rangle = H |\psi(t)\rangle,$

where the Hamiltonian is the adjacency matrix of $G$ (up to a sign convention and an overall rate constant $\gamma$ ):

$H = -\gamma A.$

Here $A$ is the $n \times n$ adjacency matrix: $A_{jk} = 1$ if there is an edge between vertex $j$ and vertex $k$ , and $A_{jk} = 0$ otherwise. Setting $\hbar = 1$ and absorbing $\gamma$ into $t$ , the time-evolution operator is

$U(t) = e^{-iHt} = e^{i\gamma A t}.$

Starting from a vertex $|j\rangle$ , the amplitude to be at vertex $k$ at time $t$ is

$\langle k | U(t) | j \rangle = \left(e^{i\gamma A t}\right)_{kj}.$

Math you'll use here: spectral decomposition

A Hermitian matrix $A$ (here, the adjacency matrix) always has a full set of orthonormal eigenvectors $|v_k\rangle$ with real eigenvalues $\lambda_k$ . This lets us write

$A = \sum_k \lambda_k\, |v_k\rangle\langle v_k|,$

the spectral decomposition: $A$ resolved into orthogonal rank-1 projectors, each scaled by its eigenvalue. The projectors are complete, $\sum_k |v_k\rangle\langle v_k| = I$ , and mutually orthogonal, $\langle v_j | v_k\rangle = \delta_{jk}$ .

The payoff is evaluating a function of a matrix: applying $f$ to $A$ just means applying $f$ to each eigenvalue, leaving the projectors untouched. For the matrix exponential,

$f(A) = \sum_k f(\lambda_k)\, |v_k\rangle\langle v_k| \quad\Longrightarrow\quad e^{i\gamma A t} = \sum_k e^{i\gamma \lambda_k t}\, |v_k\rangle\langle v_k|.$

(Check: expand $e^{i\gamma A t}$ as a power series and use $A^m |v_k\rangle = \lambda_k^m |v_k\rangle$ term by term.) This turns the hard problem of exponentiating a matrix into trivial scalar exponentials — exactly the move the example below makes to compute the walker's amplitudes on the 3-vertex path.

A concrete example: the path on three vertices

Consider three vertices connected as a line: $0 - 1 - 2$ . The adjacency matrix is

$A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}.$

The eigenvalues of $A$ are $\lambda_0 = -\sqrt{2}$ , $\lambda_1 = 0$ , $\lambda_2 = +\sqrt{2}$ , with corresponding orthonormal eigenvectors

$|v_0\rangle = \frac{1}{2}\begin{pmatrix} 1 \\ -\sqrt{2} \\ 1 \end{pmatrix}, \quad |v_1\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix}, \quad |v_2\rangle = \frac{1}{2}\begin{pmatrix} 1 \\ \sqrt{2} \\ 1 \end{pmatrix}.$

Because $A$ is diagonalizable as $A = \sum_k \lambda_k |v_k\rangle\langle v_k|$ , the matrix exponential factorises as

$e^{i\gamma A t} = \sum_{k=0}^{2} e^{i\gamma \lambda_k t} |v_k\rangle\langle v_k|.$

Starting at vertex $|0\rangle$ with $\gamma = 1$ , the probability to find the walker at vertex $2$ at time $t$ is

$\langle 2 | e^{iAt} | 0 \rangle = \frac{1}{4}e^{-i\sqrt{2}\,t} - \frac{1}{2} + \frac{1}{4}e^{i\sqrt{2}\,t} = \frac{1}{2}\!\left(\cos\!\left(\sqrt{2}\,t\right) - 1\right).$

Working through the eigenvector expansion gives $P(2, t) = \tfrac{1}{4}\!\left(\cos(\sqrt{2}\,t) - 1\right)^2$ . The probability oscillates between 0 and $1$ , reflecting the coherent interference of amplitudes traveling along the two routes through the graph.

Comparison with the discrete-time model

Both models describe quantum walkers that spread faster than classical diffusion, but they differ in key respects.

| Property | Discrete-time | Continuous-time | |---|---|---| | Time parameter | Integer steps $t \in \mathbb{Z}$ | Continuous $t \in \mathbb{R}$ | | Extra register | Coin qubit(s) required | No coin — walker lives on vertices only | | Generator | Coin-and-shift unitaries | Adjacency (or Laplacian) Hamiltonian | | Physical analogy | Kicked quantum system | Quantum hopping on a lattice |

The coin-free nature of CTQWs often makes them easier to analyse mathematically and to implement via Hamiltonian simulation. In particular, any quantum algorithm that uses a discrete-time walk on a graph $G$ can in principle be converted into a continuous-time version by using the same graph adjacency structure.

Ballistic transport in the CTQW

Just as the discrete-time model on a line spreads ballistically — standard deviation $\sigma(t) \propto t$ rather than $\sqrt{t}$ — the continuous-time walk on an infinite line also achieves $\sigma(t) = O(t)$ . The adjacency matrix of the infinite path is a tri-diagonal operator; its eigenstates are plane waves $e^{ikx}$ and the group velocity is $\pm 2\gamma\sin(k)$ . A localised initial state contains many momenta and therefore spreads at rate proportional to $t$ , giving a quadratic improvement over classical diffusion.

Implementing a CTQW on a quantum computer

The time-evolution operator $e^{-iHt}$ can be implemented by Hamiltonian simulation. For sparse adjacency matrices — graphs where each vertex has at most $d$ neighbours — efficient simulation algorithms exist. The standard approach decomposes $e^{-iHt}$ into a product of simpler unitaries (Trotter–Suzuki formulas) and applies them as gates. The cost scales polynomially in $n$ , $t$ , $d$ , and the target precision $\varepsilon$ , making CTQWs a practical building block for quantum algorithms on real hardware.

The next lesson shows how both discrete and continuous-time walks can be used as the core subroutine in spatial search algorithms, turning the ballistic spreading advantage into a concrete speedup for finding a marked vertex in a graph.