Tom Gur

Ah, another beautiful question in quantum complexity theory solved! This one is due to Scott Aaronson and @AAmbainis, about the necessity of structure in a problem for exponential quantum advantage. This question inspired a lot of research and we collectively learned a lot about quantum computing from it. The problem seemed ripe; this year it felt like we were closing in on it. The most recent (human-written) papers on it had solved special cases showing that parallel quantum algorithms cannot achieve exponential speedups for unstructured problems. What is the next beautiful question in quantum algorithms that will spur another generation of learning and understanding? * Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan, Quantum Speedups Require Structure or Depth (arxiv.org/abs/2608.19158) * Qipeng Liu, Saachi Mutreja (my fantastic student!), Parallel Quantum Advantage with Limited Adaptivity Requires Structure (arxiv.org/abs/2608.20297)

I lectured on the "ETH false" (#3SAT in subexponential time) result in my grad complexity class at CMU today. Didn't have time in 80 mins to do the full proof, but I hope I got across the main plan, and some of the basic TCS ingredients going into it. youtu.be/_HlQGMcQWhA