Robin Kothari @robinkothari.bsky.social · 01/10/2026With Chenyi Zhang, Norah Tan, David Gosset, and Craig Gidney: How to compile a circuit over arbitrary 1- & 2-qubit gates to a discrete gate set adaptively with only constant overhead (and 1/poly error). scirate.com/arxiv/2609.3... arxiv.org/abs/2609.39092 090
Robin Kothari @robinkothari.bsky.social · 01/10/2026With Tony Metger, Ryan O'Donnell, Noah Shutty and Kewen Wu: A new exponential quantum speedup! Or alternatively, a new rigorous classical algorithm for Binary-Error LWE. scirate.com/arxiv/2609.4... arxiv.org/abs/2609.40321 080
Robin Kothari @robinkothari.bsky.social · 30/09/2026Carlos Bravo-Prieto, Aram Harrow (@harrowing.bsky.social), and I just uploaded a preprint that proves new upper and lower bounds to finally close the query complexity of the quantum linear systems problem. scirate.com/arxiv/2609.3... arxiv.org/abs/2609.35660 1194
Robin Kothari @robinkothari.bsky.social · 15/09/2026Now on the arXiv: Shalev Ben-David and I (with the help of LLMs) show how a randomized algorithm can compute a total Boolean function faster than it is possible to certify the function! The full proof is < 3 pages. arxiv.org/abs/2609.15063 scirate.com/arxiv/2609.1... 060
Robin Kothari @robinkothari.bsky.social · 09/04/2026I'm happy to announce that we improved this result establishing @lance.fortnow.com's conjecture: from a quartic relationship between degree and rational degree to cubic. This is essentially the limit of this method and further demonstrates the power of "best-case" query measures. 1100
Robin Kothari @robinkothari.bsky.social · 23/10/2025Are you a computer scientist and don't know what an OTOC is, but want to understand the problem solved in the recent Nature paper by Google Quantum AI? We wrote a 2-page note that explains the motivation and presents a simplified version of the problem for any input size. scirate.com/arxiv/2510.1... 0324
Robin Kothari @robinkothari.bsky.social · 10/10/2025Fresh on the arXiv: @booleananalysis.bsky.social, Kewen Wu, and I present new classical algorithms for the Short Integer Solution problem (under infinity norm) that outperform the elegant Chen-Liu-Zhandry quantum algorithm, showing that there is no exponential quantum speed up anymore. 3183
Robin Kothari @robinkothari.bsky.social · 09/10/2025New paper on the arXiv with David Gosset and Google student researcher Chenyi Zhang on how to implement an n-qubit Toffoli gate (approximately) with exponentially fewer T gates than previously thought. arxiv.org/abs/2510.07223 scirate.com/arxiv/2510.0... 0181
Robin Kothari @robinkothari.bsky.social · 06/08/2025The QIP 2026 call for papers is out! QIP 2026 will be held in Riga, Latvia from January 24–30, 2026. See you there! qip2026.lu.lv 02815
Robin Kothari @robinkothari.bsky.social · 26/04/2025Rational degree is one of the rare measures that could be polynomially related to deterministic query complexity, quantum query complexity, sensitivity, and all our favorite measures (for total functions), but we just don't know! Bonus: we have an updated table of query separations! 050
Robin Kothari @robinkothari.bsky.social · 26/04/2025In "On the Rational Degree of Boolean Functions and Applications" with Vishnu Iyer, Siddhartha Jain (@sidjai.bsky.social), Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, and Michael Whitmeyer, we prove many interesting results about rational degree. arxiv.org/pdf/2310.08004 1110