{"id":"arxiv/2601.15171","url":"https://arxiv.org/abs/2601.15171","tags":["quant-ph"],"score":0,"title":"A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem","domain":"quant-ph","source":"arxiv","authors":["Ansis Rosmanis"],"reviews":0,"subject":"quant-ph","summary":"Recently, Jordan et al. (Nature, 2025) introduced a novel quantum-algorithmic technique called Decoded Quantum Interferometry (DQI) for solving specific combinatorial optimization problems associated with classical codes. They presented a constraint-satisfaction problem called Optimal Polynomial Intersection (OPI) and showed that, for this problem, a DQI algorithm running in polynomial time can satisfy a larger fraction of constraints than any known polynomial-time classical algorithm. In this work, we propose several improvements to the DQI algorithm, including sidestepping the…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-01-21","reactions":{}}