3 papers
quant-ph2026
No exponential quantum speedup for anymore
Robin Kothari, Ryan O'Donnell, Kewen Wu
In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case -Short Integer Solution () problem, in a parameter r…
quant-ph2025
Quartic quantum speedups for planted inference
Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari +1
We describe a quantum algorithm for the Planted Noisy XOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (th power) speedup over the…
quant-ph2024
Uniformity testing when you have the source code
Clément L. Canonne, Robin Kothari, Ryan O'Donnell
We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the di…