ALGORITHMS / 30 MIN
Quantum walks & graph search
|ψ(t)⟩ = exp(−itA)|ψ(0)⟩
DERIVATION 1
A graph is a Hamiltonian
For an undirected graph, its real symmetric adjacency matrix A is Hermitian. Continuous-time evolution exp(−itA) is unitary (with ℏ=1). Amplitudes interfere along paths; probabilities do not follow the same transition rule as a classical random walk.
DERIVATION 2
Two connected vertices
For two vertices joined by one edge, A=X. Starting at vertex 0 gives cos(t)|0⟩−i sin(t)|1⟩. At t=π/2 the walker is entirely at vertex 1, up to a global phase. At t=π it returns to 0.
DERIVATION 3
Search depends on structure
Discrete-time walks can use a coin register and conditional shift. Quantum walk search bounds depend on graph structure, marked vertices, access assumptions and spectral gap. No universal exponential speedup follows from calling a process a quantum walk.
Assessment
0 / 2 answered · 0 saved attempts
