Quantum Sampling of Random Spanning Trees via Amortized Data Structures
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.40314
curl -X POST /api/v1/records/arxiv/2609.40314/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.40314/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'