Applied & Computational Mathematics seminar: Optimization by Decoded Quantum Interferometry

Speaker: Stephen P. Jordan, Google Quantum AI, Venice, CA

Title:  Optimization by Decoded Quantum Interferometry

Abstract:  In this talk I will describe Decoded Quantum Interferometry (DQI), a quantum algorithm for reducing classical optimization problems to classical decoding problems by exploiting structure in the Fourier spectrum of the objective function. (See: https://arxiv.org/abs/2408.08292.) For a regression problem called optimal polynomial intersection, which has been previously studied in the contexts of coding theory and cryptanalysis, DQI achieves an exponential quantum speedup over all classical algorithms we are aware of. We also investigate the application of DQI to average-case instances of max-k-XORSAT. DQI reduces max-k-XORSAT to decoding LDPC codes, which can be achieved using powerful classical algorithms such as belief propagation. In this setting we identify a family of max-XORSAT instances where DQI achieves a better approximation ratio than simulated annealing, although not better than specialized classical algorithms tailored to those instances. The recent quantum query complexity speedup of Yamakawa and Zhandry can also be obtained as a special case of DQI. This is joint work with Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, and Ryan Babbush.

Bio: Stephen Jordan is a quantum algorithms researcher at Google Quantum AI. He obtained his PhD in theoretical physics from MIT in 2008. Prior to joining Google he carried out research on quantum algorithms and quantum complexity theory at NIST and Microsoft and led a research group at University of Maryland. From 2015-2017 he served on the interagency working group on quantum information science for the White House Office of Science and Technology Policy.
He is also the author and maintainer of the quantum algorithm zoo, a website cataloging known quantum algorithms.

Time:  Monday, November 18 – 1:30pm – 2:30pm
Place:  Innovation Hall, room 328 Hall