Optimization by Decoded Quantum Interferometry

Achieving superpolynomial speedups for optimization has long been a central goal for quantum algorithms. I will describe Decoded Quantum Interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems. For approximating optimal polynomial fits over finite fields, DQI achieves a superpolynomial speedup over known classical algorithms. The speedup arises because the problem's algebraic structure is reflected in the decoding problem, which can be solved efficiently. It is an open problem to determine whether DQI can also achieve speedup for more generic combinatorial problems that lack algebraic structure. In the second half of this talk, I will describe some recent progress toward answering this question.