Skip to main content
Browse by:
GROUP

DQC Seminar Series: Optimization by Decoded Quantum Interferometry

Event Image
Thursday, February 20, 2025
12:00 pm - 1:00 pm
Noah Shutty, Google Quantum AI

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

Contact: Margo Ginsberg