Quantum Sampling of Random Spanning Trees via Amortized Data Structures
This quantum algorithm uses sublinear queries to find a uniform superposition over spanning trees of a graph. It achieves this by using slowly changing Markov chains and reusable data structures that evolve with the graph structure. This allows for preparing high-quality samples of the tree distribution efficiently, offering significant speedups over classical sampling methods.