Sign in

Robin Kothari

@robinkothari.bsky.social
467 followers 35 following 29 posts

Theoretical computer scientist working on quantum algorithms and complexity at Google Quantum AI. Previously at Microsoft Quantum, MIT, U. Waterloo, and IIT Bombay.

PostsRepliesMedia
Robin Kothari @robinkothari.bsky.social · 01/10/2026
With 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/2026
With 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/2026
Carlos 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/2026
Now 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/2026
I'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/2025
Are 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/2025
Fresh 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/2025
New 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/2025
The 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/2025
Rational 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!
Screenshot of the table of separations from the paper
050
Robin Kothari @robinkothari.bsky.social · 26/04/2025
In "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
A screenshot of the title and abstract of the paper
1110