H.B. Keller Colloquium

Finding natural problems with exponential quantum speedups is a central goal in quantum computing. Relatively few candidates are known beyond quantum simulation and period finding (i.e., factoring). This talk is about a different approach based on Regev's reduction, which multiplies quantum states to combine global structure with local constraints to solve classical problems. I will discuss two applications. The first is a subset-sum problem: find a nontrivial subset of input vectors summing to zero over finite field GF(3). We give polynomial-time quantum algorithms in a regime where only exponential-time classical algorithms are known. The second is a polynomial fitting problem: find a low-degree polynomial satisfying as many input evaluation constraints as possible over finite fields. We give quantum algorithms satisfying 93% constraints by only going through the input data in one pass with limited memory and efficient computation; and prove that any classical algorithm reaching even 76% needs exponentially more data passes or memory, regardless of computation time. Based on joint works with Robin Kothari, Tony Metger, Ryan O'Donnell, Noah Shutty, and Guangxu Yang.