Theoretical computer scientist working on quantum algorithms and complexity @GoogleQuantumAI. Previously @MSFTQuantum, @MIT, @UWaterloo, @iitbombay.
Joined November 2009
- Tweets192
- Following92
- Followers2.2K
- Likes743
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:
google.com/about/careers/app…
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-quantum-comp
Paper: scirate.com/arxiv/2610.23832
Competition: kaggle.com/competitions/goog…
In less than a day the separation has moved from 2.006 to 2.05. How much higher can it go?
Can you (or your agents) improve the super-quadratic separation between block sensitivity and sensitivity from the current bound of ~2.006? The optimal exponent is between 2 and 4. My guess is 2.5 is achievable. Submit your lean-verified solutions here: prove2.me/campaigns/block-se…
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.
Can you (or your agents) improve the super-quadratic separation between block sensitivity and sensitivity from the current bound of ~2.006? The optimal exponent is between 2 and 4. My guess is 2.5 is achievable. Submit your lean-verified solutions here: prove2.me/campaigns/block-se…
Looks like the Aaronson-Kuperberg conjecture was resolved today. Turns out there is an efficient algorithm, as I conjectured 🙂
With Chenyi Zhang, Norah Tan (@NorahTan1), David Gosset, & Craig Gidney (@CraigGidney): 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.39092
arxiv.org/abs/2609.39092
With Tony Metger, Ryan O'Donnell (@BooleanAnalysis), Noah Shutty and Kewen Wu (@wu_kewen): A new exponential quantum speedup! Or alternatively, a new rigorous classical algorithm for Binary-Error LWE.
scirate.com/arxiv/2609.40321
arxiv.org/abs/2609.40321
Carlos Bravo-Prieto (@charl_bp), Aram Harrow (@quantum_aram), 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.35660
arxiv.org/abs/2609.35660
For QIP 2027 submissions: Submit your paper to the arXiv by Wednesday at 2pm ET to have moderation delay protection. After that you’re taking a chance.
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).
Note the various submission deadlines for QIP 2027. It’s different from last year! Your paper must be on the arXiv on the final submission day and hence it is recommended to upload your paper to the arXiv by Sept 30.
For talk submissions, remember to register by 28 Sep (23:59 AoE)! Registration only requires a title, short abstract, authors, and topic selections, but do note the recommended cutoff for the arXiv submission and talk submission - read the details at qipconference.org/2027/call/
The STOC 2027 Call For Papers is out and has many differences compared to last year.
acm-stoc.org/stoc2027/stoc20…
I like these changes! They are very consistent with my own views on how conferences in 2027 should adapt to the new world we’re in.
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.15063
Frontier LLMs can now solve interesting open problems. So how should academic conferences adapt? I get asked this often and I've given this a lot of thought for QIP 2027 specifically, as chair of the Steering Committee. My personal thoughts (not speaking for the SC): (1/4)
This seems independent of whether the ideas were generated by humans or AI. Even if the results were generated by AI, authors still play an important role: they understand the results, verify correctness, simplify the arguments, and present them clearly for other humans. (3/4)
QIP 2027 CFP is out! Some changes: Separate registration and submission deadlines one week apart. Paper must be on arXiv by submission deadline. 3 page abstract has no author names. Poster and talk submissions separate. AI use OK, but badly written papers will be rejected.
We're pleased to announce the QIP 2027 call for submissions. The key dates are as follows; refer to the website qipconference.org/2027/call/ for detailed instructions.
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?
