Optimization by decoded quantum interferometry.

ABSTRACT: Achieving superpolynomial speed-ups for optimization has long been a central goal for quantum algorithms¹. Here we introduce decoded quantum interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems. When approximating optimal polynomial fits over finite fields, DQI achieves a superpolynomial speed-up over known classical algorithms. The speed-up arises because the algebraic structure of the problem is reflected in the decoding problem, which can be solved efficiently. We then investigate whether this approach can achieve a speed-up for optimization problems that lack an algebraic structure but have sparse clauses. These problems reduce to decoding low-density parity-check codes, for which powerful deco

SUBMITTER: Jordan SP 

PROVIDER: S-EPMC12545177 | biostudies-literature | 2025 Oct

REPOSITORIES: biostudies-literature