Thirty years after Shor’s and Grover’s breakthroughs, should we lament how few quantum algorithms have been discovered since then, which we’re confident achieve huge speedups over classical computing for problems that matter in practice?  Or should we rejoice in the quantum speedups we have?  This is of course a question about our emotional stance, as much as about the quantum algorithms themselves.  Nevertheless, I’ll do my best to ponder the question in the light of quantum walk algorithms, quantum annealing and other heuristic methods, Forrelation, HHL-type learning algorithms, and (since 2022) Yamakawa-Zhandry-type algorithms for NP search and optimization problems.

Scott Aaronson, Professor of Computer Science, The University of Texas at Austin