Optimization by Decoded Quantum Interferometry

We address a longstanding question in quantum computing: Can quantum computers provide exponential speedups for optimization problems? We introduce Decoded Quantum Interferometry (DQI), which reduces optimization problems to decoding problems by exploiting structure in the Fourier spectra of the objective functions. DQI achieves an exponential speedup for a previously-studied optimization problem that generalizes polynomial regression and has been studied in the contexts of cryptanalysis and classical error correction. DQI is a radical departure from prior approaches, as it relies on neither the Abelian hidden subgroup problem nor a Hamiltonian formulation.