Quantum graph algorithms accelerate selected searches inside a graph representation. The first mathematical question is therefore not “what is the graph problem?” but “how is the graph accessed?”
An adjacency matrix provides an oracle for individual pairs (u,v). An adjacency list provides indexed access to neighbours and often degrees. Their classical and quantum query complexities differ. A claimed speedup can disappear if one quotes an adjacency-matrix quantum bound against an adjacency-list classical baseline or ignores the cost of outputting an entire n-vertex object.
This guide develops Grover neighbour search, minimum finding, connectivity/spanning-tree ideas, single-source shortest paths, triangle finding, element-distinctness reductions, Szegedy/MNRS quantum walks, hitting/search complexity and the boundary between query complexity and end-to-end runtime.
Choose graph access model → identify repeated search/minimum/collision primitive → replace classical scan by amplitude/quantum-walk search → preserve correctness/output requirements → compare against the right classical graph algorithm.
1. Adjacency-matrix query model
For an n-vertex graph, an oracle answers
O_G: |u,v,z⟩→|u,v,z⊕A_{uv}⟩
where Auv is 1 if edge (u,v) exists or a weight/value in weighted versions.
The matrix has Θ(n²) possible entries. Classical algorithms that know nothing else may need Θ(n²) edge queries for global properties.
2. Adjacency-list query model
A list oracle can provide the j-th neighbour of vertex u:
O_N: |u,j,0⟩→|u,j,N(u,j)⟩.
Degree access may be given separately.
For sparse graphs with m≪n² edges, adjacency lists are much stronger than pairwise matrix access because a classical traversal costs O(n+m), not O(n²).
Every graph-algorithm complexity in this guide should be read together with its stated access model.
3. Grover search inside a row
Suppose we want to find any neighbour of u satisfying predicate P(v).
In an adjacency-matrix row there are n candidate vertices.
If k candidates satisfy the predicate, Grover/amplitude-amplification search finds one using
O(√(n/k))
predicate queries under ideal coherent access.
If k is unknown, variable-iteration search retains the same expected scaling up to constants.
4. Quantum minimum finding
Dürr and Høyer showed that the minimum of N unsorted values can be found with O(√N) expected comparisons/queries. [1]
The algorithm repeatedly Grover-searches for an item smaller than the current threshold and updates the threshold.
This becomes useful in graph algorithms whenever a classical step scans many candidate vertices for the smallest tentative distance or lightest edge.
5. Connectivity in the matrix model
Classically, exploring an unknown adjacency matrix can cost Θ(n²) queries.
Quantum connectivity algorithms combine a growing discovered component with Grover searches for edges leaving it.
Representative quantum query complexity in the adjacency-matrix model is
O(n^{3/2})
for connectivity/spanning-tree construction, up to algorithm/model details. Dürr, Heiligman, Høyer and Mhalla developed such graph-query algorithms and matching/near-matching lower bounds for several tasks. [2]
6. Why n^(3/2) appears
A spanning tree has n−1 edges.
At a high level, each newly discovered tree edge can be found by searching a row/region of O(n) possible partners using O(√n) queries.
Repeating O(n) times suggests O(n√n)=O(n3/2).
Actual proofs organise searches more carefully, but this heuristic explains the scaling.
7. Output size prevents arbitrarily small connectivity cost
If the requested output is an explicit spanning tree, it contains n−1 edge labels.
Writing the answer therefore costs Ω(n) classical information even if decision connectivity could in principle use fewer internal operations.
Quantum speedups compress search work, not the number of bits that must eventually be printed.
8. Breadth-first search intuition
Classical BFS visits every incident edge of discovered vertices.
In a dense adjacency matrix this can be Θ(n²).
A quantum variant uses repeated Grover search to find yet-unvisited neighbours without scanning all n candidates each time.
The quantum algorithm still stores a classical visited structure because once a vertex has been discovered, future predicates must know not to rediscover it.
9. Weighted shortest paths
Dijkstra’s classical algorithm repeatedly:
- selects the unsettled vertex with minimum tentative distance;
- relaxes outgoing edges.
In an adjacency matrix, a naive minimum selection scans O(n) vertices and edge relaxation scans O(n) possible neighbours.
Quantum minimum finding/search can reduce these scans. Representative query bounds for single-source shortest paths in dense/matrix access reach around O(n3/2) in the standard quantum-query literature, while exact constants/log factors depend on weight and oracle conventions. [2]
10. Negative weights and shortest paths
Dijkstra-type reasoning assumes nonnegative edge weights.
With negative weights one needs Bellman–Ford-style relaxation or other methods; a negative cycle makes shortest-path distance undefined below.
Quantum minimum finding does not remove these mathematical conditions. Speeding up a subroutine does not change which recurrence is correct.
11. Triangle finding
A triangle is a triple {u,v,w} with all three edges present.
Classically, checking every triple costs O(n³), though matrix-multiplication and combinatorial algorithms do much better.
In the adjacency-matrix query model, quantum algorithms achieve strongly subquadratic query complexity. Le Gall gave an O(n5/4) query algorithm using learning-graph/quantum-walk ideas. [4]
This is a query-complexity result; total gate/time complexity includes data structures, coherent memory and checking costs.
12. Triangle finding as collision structure
Fix an edge (u,v). A triangle exists if there is w in the intersection
N(u)∩N(v).
Searching this intersection is a collision/intersection problem.
Naively Grover-searching w for every pair (u,v) is not optimal. Better quantum algorithms organise subsets of vertices so information learned about many possible edges is reused across a quantum walk.
13. Element distinctness
Given N values, element distinctness asks whether any pair is equal.
Ambainis developed a quantum walk algorithm using O(N2/3) queries, improving on the previous O(N3/4) quantum query algorithm of Buhrman and collaborators and matching the known query scaling. [3]
This problem is important because many graph-substructure searches reduce to finding collisions among locally computed labels.
14. Quantum walk search
A classical Markov chain on state space Ω has transition matrix P and stationary distribution π.
Quantum-walk search constructs a unitary from P whose eigenphase gap is related to the classical spectral gap δ.
If an ε fraction of stationary probability is marked, the MNRS search framework has a schematic cost
S + (1/√ε)(U/√δ + C)
where S is setup cost, U update cost and C marked-state checking cost. [5]
The square roots of ε and δ are the source of many quantum-walk speedups.
15. Johnson graph walk
Element-distinctness/triangle algorithms often walk on r-element subsets of an N-element universe.
The Johnson graph J(N,r) connects two subsets when they differ by one element.
A quantum walk can maintain a data structure for the current subset, update it cheaply when one element changes, and search for subsets containing a collision/triangle witness.
The optimal subset size balances setup, update, marked fraction and spectral gap.
16. Hitting time
Classically, hitting time is the expected number of steps before a Markov chain reaches a marked set.
Szegedy-type quantum walks can produce roughly quadratic improvements in hitting/search time for reversible chains under suitable conditions.
The speedup is not “walk distance becomes square-rooted” in every graph. It depends on spectral structure and marked-set overlap.
17. Search on a complete graph reduces to Grover
Take a uniform random walk on N items with one marked item.
The marked fraction is ε=1/N and the spectral gap is constant-order for the complete mixing chain.
The walk-search cost scales as
O(1/√ε)=O(√N),
recovering Grover scaling.
18. Search on grids
Spatial search on low-dimensional lattices behaves differently because the random walk has a small spectral gap and recurrence properties.
Quantum walks can still outperform classical diffusion, but dimensions one and two require special analysis and logarithmic factors may appear.
Graph geometry matters; one cannot infer quantum search time from number of vertices alone.
19. Bipartiteness and cycle properties
Many decision graph properties can be attacked by accelerated traversal/search for witnesses.
For bipartiteness, a witness is an odd cycle or a conflict in a two-colouring.
Quantum query algorithms improve dense-matrix exploration, but sparse adjacency-list BFS is already O(n+m). The relative advantage depends strongly on density.
20. Minimum spanning tree
Classical MST algorithms repeatedly select light edges connecting components.
Quantum minimum finding can accelerate edge selection in dense query models.
The same Dürr–Heiligman–Høyer–Mhalla framework gives O(n3/2)-scale query algorithms for spanning-tree/MST-related dense graph tasks, while the explicit tree output itself remains Ω(n).
21. Quantum walk versus continuous-time quantum walk
Discrete-time/Szegedy walks use unitary reflections derived from a classical Markov chain.
Continuous-time walks evolve under a graph Hamiltonian such as adjacency A or Laplacian L:
|ψ(t)⟩=e^{-iAt}|ψ(0)⟩.
Both can power graph algorithms, but their spectra, oracle implementations and complexity proofs differ.
22. Quantum walk does not mean a classical random walk with complex probabilities
Quantum amplitudes interfere and unitary evolution is reversible.
There is no direct step-by-step probability distribution obeying the same Markov recursion until measurement occurs.
This interference allows amplitude to concentrate on marked structures faster than classical mixing/hitting in selected settings.
23. Data structures matter
Advanced quantum-walk graph algorithms maintain coherent data about the current subset/state.
Setup may require querying many edges; one walk update should change only a small part of the data structure.
If checking a marked condition requires rebuilding the entire structure, the theoretical walk advantage disappears.
Time complexity can therefore be much larger than bare query complexity.
24. Weighted graph values need precision
For weighted shortest path or MST, edge weights must be compared coherently.
If weights are b-bit integers, arithmetic/comparison circuits have poly(b) gate cost.
For real-valued weights returned approximately, correctness depends on separation between competing path costs. Query bounds alone suppress this numerical precision layer.
25. Dynamic and streaming graphs
If a graph changes over time, coherent oracle updates may be more expensive than the graph query algorithm itself.
A QRAM-style adjacency structure must be updated consistently after insertions/deletions.
Quantum graph speedups are strongest when the graph is static or generated by an efficient reversible rule rather than repeatedly reloaded from a changing classical database.
26. Output-sensitive graph tasks
Decision problems ask one bit: “is the graph connected?”
Search problems ask for one witness: “find one triangle.”
Enumeration problems ask for many outputs: “list every triangle” or “return all-pairs distances.”
Quantum acceleration is usually strongest for decision/search. If there are Θ(n²) values to output, an Ω(n²) classical-output floor remains.
27. Classical baselines are powerful
For sparse graphs, classical BFS/DFS is O(n+m).
Dijkstra with heaps, union-find MST methods, fast matrix multiplication and specialised triangle algorithms can be excellent.
A quantum query speedup over n² matrix scanning is not necessarily a practical runtime speedup over the best RAM-model classical graph algorithm.
28. Common misconception: Grover makes every graph algorithm quadratically faster
Graph algorithms contain dependent traversals, data structures and large outputs. Only particular unstructured-search subproblems receive Grover-type speedups.
29. Common misconception: O(n^(3/2)) connectivity beats O(n+m) BFS on every graph
The O(n3/2) figure is a dense adjacency-matrix query result. Sparse adjacency-list BFS may be asymptotically better classically when m=O(n).
30. Common misconception: query complexity equals wall-clock complexity
A coherent graph query can require routing, QRAM/QROM, arithmetic and error correction. Query complexity isolates one resource and must be complemented by implementation cost.
31. Worked synthesis problem
An unknown dense n=10,000 graph is accessible only through an adjacency-matrix oracle. We want to find one edge leaving a discovered connected component from a selected vertex u.
Step 1: Classical row scan. Up to 10,000 edge queries.
Step 2: Quantum predicate. Mark v when Auv=1 and v is not yet visited.
Step 3: One marked neighbour. Grover search uses O(√10,000)=O(100) coherent predicate queries.
Step 4: Traversal scale. Repeating such searches across O(n) discovery events leads heuristically toward n√n≈106 matrix queries rather than n²≈108.
Step 5: Model caveat. If the same graph were supplied as a sparse adjacency list with m≈2n, classical BFS would use O(n+m)≈30,000 neighbour operations and could outperform the dense-oracle quantum method. The representation determines the comparison.
32. Practice set
- Define adjacency-matrix access.
- Define adjacency-list access.
- What is the Grover cost for finding one of k marked items among n?
- What is the Dürr–Høyer minimum-finding scaling?
- What representative matrix-query scaling appears for connectivity/spanning tree?
- Why does explicit spanning-tree output impose Ω(n) work?
- How can quantum minimum finding enter Dijkstra-like algorithms?
- What representative query exponent is known for quantum triangle finding?
- What is the element-distinctness query scaling?
- What do ε and δ mean in quantum-walk search?
- Why can adjacency-list classical algorithms erase a matrix-model speedup?
- Why must graph output size be included in end-to-end complexity?
Answers
- An oracle returns the edge/weight associated with a chosen ordered vertex pair (u,v).
- An oracle returns indexed neighbours (and often degree), exposing sparse structure directly.
O(√(n/k)).O(√N)expected comparisons/queries among N unsorted values.O(n^{3/2})in the standard dense adjacency-matrix query setting.- The tree contains n−1 labelled edges that must be written/classically represented.
- It accelerates repeated selection of the smallest tentative distance or candidate edge in an unstructured collection.
- O(n5/4) queries for a known adjacency-matrix triangle-finding algorithm.
- O(N2/3) queries.
- ε is stationary marked probability; δ is the classical walk spectral gap controlling mixing/eigenphase separation.
- Sparse graphs can be traversed classically in O(n+m), far below n² matrix scanning.
- Quantum computation cannot avoid the information-theoretic cost of producing a large classical answer.
Sources and further study
[1] Christoph Dürr and Peter Høyer, A Quantum Algorithm for Finding the Minimum. Establishes O(√N) quantum minimum finding.
[2] Christoph Dürr, Mark Heiligman, Peter Høyer and Mehdi Mhalla, Quantum query complexity of some graph problems, SIAM Journal on Computing 35, 1310–1328 (2006). Connectivity, shortest-path, spanning-tree and related graph-query algorithms.
[3] Andris Ambainis, Quantum walk algorithm for element distinctness, SIAM Journal on Computing 37, 210–239 (2007). The canonical O(N2/3) walk algorithm.
[4] François Le Gall, Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments, FOCS 2014. Gives O(n5/4) adjacency-matrix query complexity.
[5] Frédéric Magniez, Ashwin Nayak, Jérémie Roland and Miklos Santha, Search via Quantum Walk, SIAM Journal on Computing 40, 142–164 (2011). General reversible-Markov-chain quantum-walk search framework.
Continue through Quantum Mathematics
Guide 69: Quantum State Preparation, Amplitude Encoding, QROM, Data Loading and State-Synthesis Algorithms develops graph-oracle/data-loading costs. Guide 70: Quantum Hamiltonian Learning, System Identification, Bayesian Estimation and Spectroscopy develops inverse dynamical models. Guide 72: Quantum Reference Frames, Superselection Rules, Asymmetry and Relational Quantum States develops symmetry/reference structure.