Robin Kothari
@robinkothari.bsky.social
Theoretical computer scientist working on quantum algorithms and complexity at Google Quantum AI. Previously at Microsoft Quantum, MIT, U. Waterloo, and IIT Bombay.
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...
scirate.com/arxiv/2510.1...
October 23, 2025 at 2:58 AM
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...
scirate.com/arxiv/2510.1...
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.
October 10, 2025 at 6:07 AM
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.
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...
arxiv.org/abs/2510.07223
scirate.com/arxiv/2510.0...
October 9, 2025 at 9:21 PM
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...
arxiv.org/abs/2510.07223
scirate.com/arxiv/2510.0...
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
qip2026.lu.lv
August 6, 2025 at 12:44 AM
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
qip2026.lu.lv
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!
April 25, 2025 at 11:03 PM
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!
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
arxiv.org/pdf/2310.08004
April 25, 2025 at 11:03 PM
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
arxiv.org/pdf/2310.08004