Researchers at Google Quantum AI have published a quantum algorithm called decoded quantum interferometry, or DQI, that they say could solve certain hard optimization problems far faster than any known classical method. The work, first posted as a preprint in August 2024, appeared in the journal Nature in October 2025, giving it peer-reviewed standing.
Optimization problems, which involve finding the best option among an enormous number of possibilities, show up everywhere from logistics and scheduling to finance and materials design. Finding quantum algorithms that beat classical computers on them has been a long-standing goal, and progress has been slow. The authors describe DQI as a step toward superpolynomial speedups for a class of such problems, meaning the advantage grows rapidly as problems get larger.
Turning one hard problem into another
The core idea is a translation. DQI uses the quantum Fourier transform to convert an optimization problem into a decoding problem of the kind studied in error-correcting codes, where the task is to recover a message from a noisy signal. Decoding is a well-developed field with efficient classical algorithms for many code families. By routing the problem through that machinery, the quantum computer can use interference, the way quantum amplitudes reinforce or cancel one another, to concentrate probability on good solutions.
A classical computer effectively explores candidate solutions one path at a time. A quantum computer manipulates many possibilities in superposition, and interference is the mechanism that makes useful answers more likely to appear when the system is measured. DQI is an attempt to harness that mechanism for optimization in a structured way rather than through heuristics.
What it can and cannot do yet
The paper’s strongest result applies to a specific problem the authors call optimal polynomial intersection, for which they argue DQI achieves an exponential advantage over the best classical algorithms they could identify. For more general problems, such as finding approximate solutions to systems of constraints, the algorithm’s performance depends on how good the available decoders are, and the authors are careful to describe those cases as open questions rather than settled wins.
The algorithm is also theoretical for now. Running DQI on a problem large enough to show an advantage would require a fault-tolerant quantum computer with far more reliable qubits than any machine available today. Google and its competitors are working toward such hardware, but the company has not claimed that DQI has been demonstrated on a real device at a scale that beats classical methods.
Even so, the result matters because new quantum algorithms with provable advantages are rare. Most of the field’s progress has come from improving hardware, and DQI adds to the short list of problems where a future quantum computer has a clear mathematical reason to outperform a classical one.
