A new quantum toolkit for optimization (research.google)

Google Quantum AI and academic collaborators have introduced Decoded Quantum Interferometry (DQI), a new quantum algorithmic toolkit that reframes certain hard optimization tasks as decoding problems that quantum interference can exploit. DQI uses the wave-like interference of a sufficiently large, error-corrected quantum computer to amplify near-optimal solutions; those solutions map onto lattice decoding problems. Their flagship result is for "optimal polynomial intersection" (OPI), where DQI reduces the task to decoding Reed–Solomon codes. In analysis, some OPI instances could be solved on the order of a few million elementary quantum logic operations versus roughly 10^23 operations for the best-known classical algorithm—an explicit, structure-based route to quantum advantage for approximate optimization. The work clarifies why advantage can arise despite NP-hardness: by restricting instances to ones with algebraic structure (e.g., lattices generated by successive powers), the decoding side becomes tractable while the original optimization remains classically hard. They also explore sparse cases (max-k-XORSAT → LDPC decoding), where sparsity helps decoders but also helps classical heuristics like simulated annealing, making quantum advantage subtler; they produced one DQI-favorable sparse example but could still solve it classically with a tailored method. Overall DQI provides a new paradigm—translate optimization → decoding, leverage decades of coding-theory algorithms—and points the community toward specific structured problems and decoding advances as promising near-term targets for large-scale quantum computers.