6 papers
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…
Sunflowers and Ramsey problems for restricted intersections
Barnabás Janzer, Zhihan Jin, Benny Sudakov +1
Extremal problems on set systems with restricted intersections have been an important part of combinatorics in the last 70 years. In this paper, we study the following Ramsey versi…
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…
Tight Characterizations for Preprocessing against Cryptographic Salting
Fangqi Dong, Qipeng Liu, Kewen Wu
Cryptography often considers the strongest yet plausible attacks in the real world. Preprocessing (a.k.a. non-uniform attack) plays an important role in both theory and practice: a…