arXiv:2609.40314
Quantum Sampling of Random Spanning Trees via Amortized Data Structures
Yassine Hamoudi, Adrian Tanasa, Shrinidhi Teganahally Sridhara
Abstract
We present a quantum algorithm that generates a uniform superposition over the spanning trees of a graph -- also known as a q-sample -- using only a sub-linear number of queries to the graph. This goes beyond previous work that focuses on generating classical samples, including a recent quantum algorithm by Apers, Gao, Ji, and Liu [ICALP 2025]. For an $n$-vertex, $m$-edge graph, our algorithm admits a pre-processing step of $\tilde{O}(\sqrt{mn} + m^{1-δ})$, after which each q-sample can be generated in $\tilde{O}(n^{1+2δ})$ for any $δ$. Alternatively, $k$ independent q-samples can be generated at a total cost of $\tilde{O}(\sqrt{kmn})$. We also prove a matching lower bound up to logarithmic factors, showing that our algorithm is essentially optimal. Further tradeoffs are given in the paper. In comparison, the optimal classical algorithms (Anari, Liu and Vuong [FOCS 2022]) need an $\tilde{O}(m)$ pre-processing step, after which each sample costs $\tilde{O}(n)$ operations. These results yield faster quantum walk-based algorithms for counting spanning trees or finding a marked one. Our result is obtained via quantum walk sampling over a sequence of slowly-changing Markov chains. Each chain is an isotropized up-down walk that mixes rapidly to the spanning tree distribution of the input graph. A key ingredient is an amortized data structure supporting fast implementation of the associated quantum walk operators throughout the sequence. This data structure maintains access to a spectral sparsifier and a leverage score sampler that evolve with the underlying graph.
AI Summary
The paper studies coherent sampling of spanning trees: given adjacency-list oracle access to a connected weighted graph with $n$ vertices and $m$ edges, prepare $|\pi\rangle=\sum_T\sqrt{\pi(T)}|T\rangle$, where $\pi(T)\propto\prod_{e\in T}w(e)$. This differs from outputting a classical random tree, since a classical sampler’s random-seed register cannot generally be erased efficiently. For $m\ge100n$ and $\rho\in[n/m,1]$, the algorithm uses $\widetilde O(\sqrt{mn/\rho})$ preprocessing queries, followed by $\widetilde O(\sqrt{mn\rho})$ queries per approximate q-sample. Reflections about the target state cost $\widetilde O(\sqrt{m\rho})$ queries. Optimizing the tradeoff gives $\widetilde O(\sqrt{kmn})$ total queries for $k\le m/n$ independent q-samples. A reduction from multiple threshold problems establishes a matching lower bound up to logarithmic factors, assuming per-copy error $O(1/k)$; beyond this range, query complexity saturates at $\widetilde\Theta(m)$. The construction uses quantum simulated annealing along $\widetilde O(\sqrt n)$ distributions obtained by uniformly rescaling edges outside a fixed spanning tree. A marginal-aware up-down walk has spectral gap $\widetilde\Omega(1/n)$ while retaining a temperature-independent tree encoding. Reusable sparsification data and a static envelope containing all potentially high-leverage edges reduce walk-implementation queries throughout the schedule. Applications include approximate counting and searching for marked trees. The speedups concern input-oracle queries, not runtime. The stated implementation takes $\widetilde O(n^2)$ time for preprocessing and each q-sample, uses quantum-readable classical memory, and leaves faster coherent dynamic-tree operations for future work.
Error found: The abstract's unrestricted matching lower bound is false for k > m/n, where reading the entire graph caps query complexity at O(m). The advertised Õ(√(mn)) single-sample bound does not guarantee sublinear total queries for sparse graphs with m = Θ(n). The schedule-length proof drops the logarithm and uses π_G(S) where its reciprocal is required, although the corrected calculation recovers Õ(√n). The approximate-sampling lower-bound reduction asserts one-sided error without filtering zero-weight-edge trees that a TV-close distribution may output.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.