Quantum Speedup for Sampling Random Spanning Trees

Simon Apers, Minbo Gao, Zhengfeng Ji, Chenghua Liu

Introduction

A spanning tree is a fundamental combinatorial structure—a subset of edges that connects all vertices in a graph without forming any cycles. In the realm of computer science and physics, sampling a random spanning tree (RST), where the probability of selecting a specific tree is proportional to the product of its edge weights, is a cornerstone problem. This task has historical roots in Kirchhoff’s 19th-century laws of electrical circuits and modern relevance in the Traveling Salesman Problem (TSP), network reliability analysis, and diversity sampling in machine learning.

While classical algorithms for RST sampling have reached near-perfection—achieving runtimes nearly linear in the number of edges ($m$)—they face a fundamental bottleneck: they must "touch" or examine almost every edge in the graph. This research introduces the first quantum algorithm to break this linear-time barrier, achieving a sublinear runtime of $\tilde{O}(\sqrt{mn})$ for dense graphs. Furthermore, the authors establish that this complexity is optimal by proving a matching quantum lower bound.

The Computational Challenge

In classical computing, the best-known algorithms for sampling RSTs run in $\tilde{O}(m)$ time. For dense graphs, where the number of edges $m$ can approach $n^2$ (where $n$ is the number of vertices), this linear dependence on $m$ becomes a significant computational cost. The central question addressed by this paper is whether quantum mechanics can be leveraged to sample these structures without inspecting every edge, effectively achieving a "sublinear" speedup relative to the graph's size.

Methodology: Quantum-Charging the Random Walk

The authors achieve their breakthrough by accelerating a classical Markov chain technique known as the down-up random walk. Their approach involves several key innovations:

1. The Large-Step Down-Up Walk

A standard down-up walk transitions between spanning trees by removing an edge (splitting the tree) and adding a new edge to reconnect the components. Typically, these walks change one edge at a time and require many iterations to "mix" or reach a truly random state. The authors implement a "large-step" version that modifies $\Theta(n)$ edges simultaneously. This innovation reduces the mixing time to a nearly constant $O(1)$ steps, drastically lowering the number of transitions required to produce an accurate sample.

2. Isotropic Transformation and QResistance

To ensure efficient sampling, the graph must be "balanced" so that edges have relatively equal importance (isotropy). Classically, this preprocessing requires $O(m)$ time. To avoid this, the authors developed QResistance, a quantum data structure that maintains this balanced state implicitly. It allows the algorithm to query edge properties, such as effective resistance, on the fly without ever writing down the full list of edges.

3. Quantum Multi-Sampling

The "up" portion of the walk—finding new edges to add—is the most computationally expensive phase. The authors utilize a variant of quantum search (Grover-like techniques) to sample multiple edges at once without replacement. This allows the algorithm to perform the necessary updates in $\tilde{O}(\sqrt{mn})$ time, bypassing the classical requirement to scan all $m$ edges.

Key Results and Complexity Analysis

The paper provides a rigorous theoretical framework for the quantum complexity of RST sampling:

  • Quantum Upper Bound: The proposed algorithm samples an $\epsilon$-accurate RST in $\tilde{O}(\sqrt{mn} \log(1/\epsilon))$ time.
  • Quantum Lower Bound: The authors prove a query complexity lower bound of $\Omega(\sqrt{mn})$ by reducing the problem to a search for marked elements. This confirms that the proposed algorithm is optimal up to polylogarithmic factors.
  • The Sublinear Advantage: The significance of this result is most apparent in dense graphs. For a graph where $m \approx n^2$, a classical algorithm requires $O(n^2)$ time, whereas this quantum algorithm requires only $O(n^{1.5})$ time.

Discussion and Future Work

This work represents a major step forward in quantum combinatorial optimization and sampling. By proving that sublinear sampling is possible for weighted graphs, it opens several new avenues for research:

  1. Unweighted Graphs: The $\Omega(\sqrt{mn})$ lower bound specifically applies to weighted graphs. The authors hypothesize that for unweighted graphs, an even faster algorithm—potentially $\tilde{O}(n)$—might exist.
  2. Determinantal Point Processes (DPPs): RSTs are a specific instance of DPPs, which are widely used in machine learning to ensure diversity in subset selection. Extending these quantum speedups to the broader class of DPPs could have significant implications for AI efficiency.
  3. Broad Combinatorial Application: The success of the "large-step" quantum walk suggests that other sampling problems, such as independent sets or graph colorings, may be susceptible to similar quantum acceleration.

In conclusion, this research provides the first optimal quantum algorithm for a fundamental graph problem, demonstrating that quantum computers can provide a provable, sublinear advantage in sampling complex combinatorial structures.

Summary updated

BibTeX
@inproceedings{apers2025quantum,
  author = {Simon Apers and Minbo Gao and Zhengfeng Ji and Chenghua Liu},
  title = {{Quantum Speedup for Sampling Random Spanning Trees}},
  booktitle = {ICALP},
  year = {2025},
  doi = {10.4230/lipics.icalp.2025.13},
}
Figure