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. More seriously, I'd like to thank the committee for selecting me and I look forward to QIP 2027 in Singapore.
I'm happy to announce that we improved this result establishing @fortnow'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.
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!
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).
Registration is now open for QEC26, to be held this June in sunny Santa Barbara, CA! see the registration page at https://t.co/KMkO866FcI 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!
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!
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.
A very clear, detailed talk by Kewen Wu about our joint work with @BooleanAnalysis that shows there’s not an exponential quantum speed up for the SIS infinity problem anymore.
https://t.co/Wa50OZFkF1
Are you a computer scientist and don't know what an OTOC is, but want to understand the problem solved in the @Nature paper by @GoogleQuantumAI? We wrote a 2-page note that explains the motivation and presents a simplified version of the problem for arbitrary input size.
Today in @Nature, we published a breakthrough demonstration of verifiable quantum advantage using a measurement known as out-of-time-order correlator (OTOC), or Quantum Echoes. Performed on our Willow chip, it paves a path toward real-world applications → https://t.co/kZyomrKPSx
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:
https://t.co/tlhv8Yp0xt
Fresh on the arXiv: @BooleanAnalysis, 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.
Hermite polynomials are ubiquitous in physics, signal analysis, statistics, and beyond. Our new work gives an algorithm to convert between the computational and discretized Hermite bases efficiently.