Stephen Jordan [Google Quantum AI]

Abstract: Achieving superpolynomial speedups for optimization has long been a central goal for quantum algorithms. Recently, we showed that quantum algorithms can solve certain optimization problems related to polynomial regression exponentially faster than known classical algorithms. This is achieved through a quantum algorithm called Decoded Quantum Interferometry (DQI), which converts these optimization problems into decoding problems for classical error-correcting codes. The speedup arises because the polynomial regression problem’s algebraic structure is reflected in the decoding problem, which can be solved efficiently using powerful classical decoding algorithms. Whether DQI can also achieve a quantum speedup for more generic optimization problems such as max-k-XORSAT remains an open question. I will discuss recent progress on this question, using quantum decoding algorithms. Prior knowledge of quantum algorithms will not be assumed.

Research Interests: quantum algorithms, optimization, decoding