DQC Seminar Series: Optimization by Decoded Quantum Interferometry

Abstract: 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. Spring 2025 Upcoming Speakers 6 Mar: TBA 20 Mar: Kristi Beck 27 Mar: Peter Shor 3 Apr: Ed Farhi 17 Apr: Anthony Ransford