下载中心
会议室预定
电子邮箱
【06-25】知行融创论坛：Quantum Speedup for Sampling Random Spanning Trees
| 知行融创论坛-实验室月度学术交流 | |
| Speaker: | 刘程华 |
| Time: | 2025年6月25日 |
| Venue: | 中国科学院软件园区5号楼三层 334报告厅 |
| Abstract: | We present a quantum algorithm for sampling random spanning trees from a weighted graph in \widetilde O(√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 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 algorith- mic 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. |
| Download | Quantum Speedup for Sampling Random Spanning Trees |