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 decoders are known^2,3. To test this, we construct a max-XORSAT instance for which DQI finds an approximate optimum substantially faster than general-purpose classical heuristics, such as simulated annealing. Although a tailored classical solver can outperform DQI on this instance, our results establish that combining quantum Fourier transforms with powerful decoding primitives provides a promising new path towards quantum speed-ups for hard optimization problems.

Fig. 1. Schematic illustration of DQI.

As the initial Dicke state is of weight ℓ, the final polynomial P is of degree ℓ. Here, for simplicity, we take w_ℓ = 1 and w_k = 0 for all k ≠ ℓ. Recycling icon adapted from FreeSVG (https://freesvg.org) under a CC0 1.0 Universal Public Domain licence.

Fig. 2. Illustration of OPI problem.

A stylized example of the OPI problem. For $y_1\in {\mathbb{F}}_p$, the orange set above the point y₁ represents $F_{y_1}$. Both polynomials Q₁(y) and Q₂(y) represent solutions that have a large objective value, as they each intersect all but one set F_y.

Fig. 3. Approximate optima for OPI.

Plot of the expected fraction ⟨s⟩/p of satisfied constraints achieved by DQI with the Berlekamp–Massey decoder and by Prange’s algorithm for the OPI problem in the balanced case r/p = 1/2, as a function of the ratio of variables to constraints n/p. At n/p = 1/10, Prange’s algorithm satisfies a fraction 0.55 of the clauses whereas DQI satisfies $⟨s⟩/p=1/2+\sqrt{19}/20\approx 0.7179$. As a concrete challenge to the classical algorithms community, we propose matching or exceeding this value in polynomial time. In our concrete resource estimation, we consider n/p = 1/2, where OPI achieves $⟨s⟩/p=1/2+\sqrt{3}/4\approx 0.9330$ and Prange’s algorithm achieves 0.75. BM, Berlekamp–Massey decoder.