Achieving superpolynomial speedups for optimization has long been a central goal for quantum algorithms. I will discuss Decoded Quantum Interferometry (DQI), a quantum algorithm descended from Regev’s reduction, 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. Whether DQI can also attain quantum advantage for algebraically unstructured optimization problems such as max-k-XORSAT remains an open question. One reason for optimism is that the sparsity of the clause structure in max-k-XORSAT is reflected in the dual decoding problem, which is for LDPC codes. I will describe some current lines of attack on this open question, as well as generalizations of DQI for preparing Gibbs states of Hamiltonians. This talk will target a broad audience without assuming deep background in quantum algorithms.