Robin Kothari

Are you a PhD student in quantum computing and interested in working with our team in 2027 as a student researcher (i.e., an internship that's ~3 months and in-person at our office)? If so, apply here: www.google.com/about/career...

Can you (or your agents) come up with smaller quantum circuits for important quantum algorithms? Give it a try on this Kaggle competition with real prize money. Blog post: goo.gle/kaggle-quant... Paper: scirate.com/arxiv/2610.2... Competition: www.kaggle.com/competitions...

Can you (or your agents) improve the super-quadratic separation between block sensitivity and sensitivity from the current bound of 2.05? The optimal exponent is between 2 and 4. My guess is 2.5 is achievable. Submit your lean-verified solutions here: prove2.me/campaigns/bl...

I'm honored and excited to announce that this paper was selected to receive a Best Paper Award at FOCS 2026! Thanks to my coauthors Matt, Daochen, and Rain for including me in this work, and to the FOCS PC for selecting this despite it having a simple proof.

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

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

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

Reminder for those submitting to QIP 2027: You must register your paper by the end of the day! This means you have to enter a title, abstract, list of authors, and select the topic area(s).

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...

Frontier LLMs can now solve many quantum computing and theoretical computer science problems that I've personally spent weeks or months working on. How is everyone else dealing with the existential crisis that accompanies this reality?

My strategy of attending the past 17 QIPs in a row has paid off! I'm happy to announce I'm now chair of the QIP steering committee (qipconference.org/steeringcomm...). More seriously, I'd like to thank the committee for selecting me and I look forward to QIP 2027 in Singapore.

Just watched this movie. I wholeheartedly recommend it to everyone, even if you think AI is not very relevant to your life (because if it isn't right now, it soon will be). www.youtube.com/watch?v=xkPb...

Registration is now open for QEC26, to be held this June in sunny Santa Barbara, CA! See the registration page at qec-conference.org for a link. Also, the deadline for submissions is next Friday. Make sure to get those in and spread the word to friends and collaborators!

I'm honored that this work with David Gosset and Chenyi Zhang was selected as one of three long plenary talks at QIP 2026!

A very clear, detailed talk by Kewen Wu on our joint work with @booleananalysis.bsky.social

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...

Are you a PhD student in quantum computing and interested in working with our team in 2026 as a student researcher (i.e., an internship that's ~3 months and in-person at our office)? If so, apply here: www.google.com/about/career...

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...

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

The notifications for #FOCS2025 are out: congratulations to all! The registration page is up: focs.computer.org/2025/register/ and information about student travel support will be added within days. Looking forward to seeing you in Sydney in December!

The submission server for #FOCS2025 is now open! Submit your work: focs25.hotcrp.com

Some #qip2025 talks this week by my excellent student coauthors: Mon 1:30pm (Kewen Wu): Quantum state preparation with optimal T-Count Mon 5pm (Alexander Schmidhuber): Quartic quantum speedups for planted inference Fri 5pm (Robbie King): Triply Efficient Shadow Tomography

If you're an early-career faculty member (received their PhD within seven years of submission) in quantum computing, consider applying to Google's Research Scholar Program. The application process is lightweight and the grant comes in the form of an unrestricted gift. research.google/programs-and...