{"id":"arxiv/2607.14650","url":"https://arxiv.org/abs/2607.14650","tags":["quant-ph"],"score":0,"title":"Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry","domain":"quant-ph","source":"arxiv","authors":["Shuji Horinaga","Takashi Yamakawa"],"reviews":0,"subject":"quant-ph","summary":"The Optimal Polynomial Intersection (OPI) problem asks us to find a low-degree polynomial over a finite field whose values lie in prescribed subsets on as many given inputs as possible. Decoded quantum interferometry (DQI) gives a quantum algorithm for OPI in parameter regimes beyond those achieved by the best known classical heuristics. Follow-up works improve the parameter regimes, but their analyses are limited to average-case settings. Recently, Sun and Wootters showed that, even in the worst case, OPI has a solution in a larger parameter regime than the one covered by DQI. However, they…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-16","reactions":{}}