Metraipolis › archive › dc_418561bbef7e

Quantum Sampling of Random Spanning Trees via Amortized Data Structures — arXiv:2609.40314

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.40314
License (as archived): CC0-1.0
Archived: 2026-10-07T15:22:37.260Z
SHA-256 of the archived text: 3f69fc7112f1ef30746df7274452136c55bbbc278372b73b6b4b745eed40e770
Stable URL of this page: https://metraipolis.com/documento/dc_418561bbef7e

How to cite

Quantum Sampling of Random Spanning Trees via Amortized Data Structures — arXiv:2609.40314 — arXiv (en), https://arxiv.org/abs/2609.40314 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_418561bbef7e (Metraipolis archive dc_418561bbef7e, sha256 3f69fc7112f1ef30746df7274452136c55bbbc278372b73b6b4b745eed40e770)

BibTeX

@misc{dc418561bbef7e,
  title = {Quantum Sampling of Random Spanning Trees via Amortized Data Structures — arXiv:2609.40314},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40314},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_418561bbef7e; sha256 3f69fc7112f1ef30746df7274452136c55bbbc278372b73b6b4b745eed40e770},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40314. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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-\delta})$, after which each q-sample can be generated in $\tilde{O}(n^{1+2\delta})$ for any $\delta$. 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.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-01 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.40314 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:53:56.886Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).