Decoded quantum interferometry for optimization

Short answer: Decoded quantum interferometry (DQI) is a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems. Its authors report a superpolynomial speed-up over known classical algorithms for approximating optimal polynomial fits over finite fields, and, on one constructed max-XORSAT instance, an approximate optimum found substantially faster than general-purpose heuristics such as simulated annealing. They also say a tailored classical solver can outperform DQI on that instance. It is a theoretical algorithm, not a hardware result.

The idea

The paper introduces DQI as a quantum algorithm for optimization that uses interference patterns as its main underlying principle. It uses a quantum Fourier transform so that amplitudes interfere constructively on strings that give good solutions, and it reduces the optimization problem to a decoding problem. The authors describe superpolynomial speed-ups for optimization as a long-standing central goal for quantum algorithms.

Polynomial fits over finite fields

For approximating optimal polynomial fits over finite fields, the authors report that DQI achieves a superpolynomial speed-up over known classical algorithms. They say the speed-up arises because the algebraic structure of the problem is reflected in the decoding problem, which can then be solved efficiently.

Problems without algebraic structure

The authors then ask whether the approach can give a speed-up for optimization problems that lack algebraic structure but have sparse clauses. They say these problems reduce to decoding low-density parity-check (LDPC) codes, for which powerful decoders are known. To test this, they construct a max-XORSAT instance for which DQI finds an approximate optimum substantially faster than general-purpose classical heuristics such as simulated annealing.

The caveat

The authors state that a tailored classical solver can outperform DQI on this instance. Their conclusion is that combining quantum Fourier transforms with powerful decoding primitives is a promising new path toward quantum speed-ups for hard optimization problems. That is a statement about a research direction, not a proven advantage on practical problems.

How to read the claims

Three different statements appear in the abstract, and they carry different weight. The speed-up for polynomial fits is stated against known classical algorithms, so it depends on what classical methods are known today. The max-XORSAT result is a single constructed instance, compared with general-purpose heuristics rather than the best possible classical method. The final claim, that the approach is a promising path, is an assessment by the authors. The Google Research page lists the same abstract as the Nature paper and the arXiv preprint, so the framing there is the authors' own and is unverified beyond the papers.

Limits

The comparison is with known classical algorithms and with general-purpose heuristics. The result is for specific problem families and the papers do not tie it to a particular hardware platform. Nothing in these papers reports a hardware run.

FAQ

What does DQI stand for?

Decoded quantum interferometry.

How does it work?

It uses a quantum Fourier transform to reduce an optimization problem to a decoding problem.

Where is the speed-up claimed?

For approximating optimal polynomial fits over finite fields, the authors report a superpolynomial speed-up over known classical algorithms.

Did it beat classical solvers on max-XORSAT?

It beat general-purpose heuristics like simulated annealing on a constructed instance, but the authors say a tailored classical solver can outperform it there.

Is it run on hardware?

These papers do not report that.