{"id":"arxiv/2609.40314","url":"https://arxiv.org/abs/2609.40314","tags":["quant-ph"],"score":0,"title":"Quantum Sampling of Random Spanning Trees via Amortized Data Structures","domain":"quant-ph","source":"arxiv","authors":["Yassine Hamoudi","Adrian Tanasa","Shrinidhi Teganahally Sridhara"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}