2026-07-26T11:03:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23390 2025-10-02T12:53:50Z ddc:004 open_access

Quantum Speedup for Sampling Random Spanning Trees Apers, Simon Gao, Minbo Ji, Zhengfeng Liu, Chenghua Quantum Computing Quantum Algorithms Random Spanning Trees We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Simon Apers and Minbo Gao and Zhengfeng Ji and Chenghua Liu 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.13 urn:nbn:de:0030-drops-233907 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode