Quantum Sampling of Random Spanning Trees via Amortized Data Structures
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 sublinear 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 [AGJL25]. For an nvertex, m-edge graph, our algorithm admits a pre-processing step of ˜︁ O( √ mn + m 1-δ ), after which each q-sample can be generated in ˜︁ O(n 1+2δ ) for any δ. Alternatively, k independent q-samples can be generated at a total cost of ˜︁ O( √ 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 [ALV22] need an ˜︁ O(m) pre-processing step, after which each sample costs ˜︁ 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.
Related
- Quantum computational advantage in random-circuit sampling on IBM superconducting quantum computers
- An End-to-End Hybrid Quantum-Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study
- Improved quantum volume estimation with transducers and amortized quantum walks
- Hierarchical Quantum Logical Processor with Amortized Long-Range Connectivity
- A random sampling method to test the weak Eigenstate Thermalization Hypothesis
BibTeX
@misc{hamoudi2026quantum,
title = {{Quantum Sampling of Random Spanning Trees via Amortized Data Structures}},
author = {Yassine Hamoudi and Adrian Tanasa and Shrinidhi Teganahally Sridhara},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40314},
eprint = {2609.40314},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05800605v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Sampling of Random Spanning Trees via Amortized Data Structures
AU - Yassine Hamoudi
AU - Adrian Tanasa
AU - Shrinidhi Teganahally Sridhara
PY - 2026
DA - 2026/09/30
PB - HAL
DO - 10.48550/arxiv.2609.40314
UR - https://hal.science/hal-05800605v1
AB - 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 sublinear 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 [AGJL25]. For an nvertex, m-edge graph, our algorithm admits a pre-processing step of ˜︁ O( √ mn + m 1-δ ), after which each q-sample can be generated in ˜︁ O(n 1+2δ ) for any δ. Alternatively, k independent q-samples can be generated at a total cost of ˜︁ O( √ 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 [ALV22] need an ˜︁ O(m) pre-processing step, after which each sample costs ˜︁ 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.
ER -