4 papers · 1 filter
Exponential quantum speedup for -Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
Robin Kothari, Tony Metger, Ryan O'Donnell +2
We study vector subset sum over : given random vectors from , find a nonempty subset that sums to zero; the smaller , the more difficult it i…
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…
(Sub)Exponential Quantum Speedup for Optimization
Jiaqi Leng, Kewen Wu, Xiaodi Wu +1
We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization, achieved through simple and natural quantum optimization algorithms, namely…
Quantum state preparation with optimal T-count
David Gosset, Robin Kothari, Kewen Wu
How many T gates are needed to approximate an arbitrary -qubit quantum state to within error ? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that…