Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry
Abstract
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 left open whether one can design a quantum algorithm that solves OPI in the worst-case beyond the DQI regime. We give such a quantum algorithm. As a byproduct, we also improve the existential bound of Sun and Wootters in certain parameter regimes. In particular, when each subset contains roughly half of the field elements, our algorithm finds a solution with satisfaction rate s=1 whenever the rate satisfies R>0.75. This matches the previous average-case bound, whereas DQI cannot achieve s=1 unless R=1. Our existential bound guarantees the existence of a solution when R> 0.7158, improving over the previous threshold R>0.7495. More generally, our existential results extend to the Max-LINSAT problem with respect to arbitrary maximum distance separable (MDS) codes. The corresponding algorithmic results apply only to MDS codes whose dual admits an efficient list decoder. Our results are obtained through a novel application of a Brascamp--Lieb-type inequality in the MDS setting, which may have further applications.
Related
- COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry
- Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
- Exact quantum algorithm for searching of multiple sets intersection
- Mirror subspace diagonalization: a real-time quantum Krylov algorithm with near-optimal sampling cost
- An Optimal Quantum Linear Systems Algorithm
BibTeX
@misc{horinaga2026worstcase,
title = {{Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry}},
author = {Shuji Horinaga and Takashi Yamakawa},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.14650},
eprint = {2607.14650},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.14650},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry
AU - Shuji Horinaga
AU - Takashi Yamakawa
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2607.14650
UR - https://arxiv.org/abs/2607.14650
AB - 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 left open whether one can design a quantum algorithm that solves OPI in the worst-case beyond the DQI regime. We give such a quantum algorithm. As a byproduct, we also improve the existential bound of Sun and Wootters in certain parameter regimes. In particular, when each subset contains roughly half of the field elements, our algorithm finds a solution with satisfaction rate s=1 whenever the rate satisfies R>0.75. This matches the previous average-case bound, whereas DQI cannot achieve s=1 unless R=1. Our existential bound guarantees the existence of a solution when R> 0.7158, improving over the previous threshold R>0.7495. More generally, our existential results extend to the Max-LINSAT problem with respect to arbitrary maximum distance separable (MDS) codes. The corresponding algorithmic results apply only to MDS codes whose dual admits an efficient list decoder. Our results are obtained through a novel application of a Brascamp--Lieb-type inequality in the MDS setting, which may have further applications.
ER -