2 papers
quant-ph2026
Quantum Sampling of Random Spanning Trees via Amortized Data Structures
Yassine Hamoudi, Adrian Tanasa, Shrinidhi Teganahally Sridhara
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…
quant-ph2026
Dequantization Barriers for Guided Stoquastic Hamiltonians
Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara
We construct a probability distribution, induced by the Perron--Frobenius eigenvector of an exponentially large graph, which cannot be efficiently sampled by any classical algorith…