Distributional Variants of the Aaronson-Ambainis Conjecture

Uma Girish, Kunal Mittal, Barak Nehoran +1

A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query…