/ advanced / algorithmsBack to lab
Advanced studies

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

1. For A=X and t=π/2, a walker starting at 0 is found at…
2. For an undirected graph, adjacency A is…

Sign in to save your assessment

Sign in to sync your saved circuits across devices.