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.

Links:
arxiv.org/abs/2601.08727
scirate.com/arxiv/2601.0...

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.

THE AI DOC: OR HOW I BECAME AN APOCALOPTIMIST - Official Trailer [HD] - Only In Theaters March 27 YouTube video by Focus Features

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!

Rational degree is polynomially related to degree We prove that $\mathrm{deg}(f) \leq 2 \, \mathrm{rdeg}(f)^4$ for every Boolean function $f$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{rdeg}(f)$ is the rational degree of $f$. This res...

arxiv.org/abs/2601.08727
scirate.com/arxiv/2601.0...

Congrats to Matt Kovacs-Deak, Daochen Wang, and (undergraduate student!) Rain Zimin Yang on resolving the 30+ year old conjecture (by Lance Fortnow) in query complexity on rational degree vs. degree. What's more, the proof is like ~2 pages if you know the standard tools of query complexity!

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

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case $\ell_\infty$-Short Integer Solution ($\mathrm{SIS}^\infty$) problem, in a parameter range outside the nor...

Links:
arxiv.org/abs/2510.07515
scirate.com/arxiv/2510.0...

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

I believe they’re working on porting it over to a more permanent website.

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!

Screenshot of the table of separations from the paper

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!

A screenshot of the title and abstract of the paper

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

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

Research scholar program Overview

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