Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
Abstract
Regev's reduction quantumly finds codewords satisfying nonlinear constraints by decoding the dual code. To date, applications that have not been dequantized have relied on efficient classical decoders and coordinate-wise constraints. We overcome these restrictions separately. Our first contribution uses a quantum decoder to find solutions y∈(𝔽q∖{0})m to By=0, where B∈𝔽qn× m. For fixed prime q>2, Chen, Liu, and Zhandry solve this problem for random matrices with m=Ω(n2), a regime now covered by classical algorithms. We adapt their template to codes (spanned by the rows of B) that satisfy a "two-fold multiplication property": the coordinate-wise products of pairs of codewords span a space of dimension smaller than m. Under suitable distance conditions, this allows us to solve instances with m≤ n2−Ω(1), beyond the established guarantees of classical algorithms. We also give an efficient classical algorithm under a stronger three-fold multiplication property, leaving intermediate regimes as candidates for quantum advantage. For Reed-Muller codes punctured at random points, our algorithm finds a word in the unpunctured dual code supported exactly on those points. This works beyond known efficient classical decoding regimes. Our second contribution retains classical decoding but allows global constraints on symbol frequencies. We study "histogram-local" constraints, which specify the allowed numbers of occurrences of each symbol. For broad families, stability under resampling one coordinate yields efficient quantum algorithms for variants of optimal polynomial intersection (OPI) combining coordinate-wise and histogram-local constraints. Adapting Yamakawa-Zhandry, we prove a quantum-classical separation for these problems relative to a classical random oracle.
Related
- Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders
- Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning
- Provable Classical and Quantum Local Algorithms for Max-k-Cut and Quantum Advantage at Moderate Girth
- Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms
- Exponential quantum speedup for 𝔽3n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
BibTeX
@misc{ragavan2026quantum,
title = {{Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability}},
author = {Seyoon Ragavan and Noah Shutty},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00502},
eprint = {2610.00502},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00502},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
AU - Seyoon Ragavan
AU - Noah Shutty
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.00502
UR - https://arxiv.org/abs/2610.00502
AB - Regev's reduction quantumly finds codewords satisfying nonlinear constraints by decoding the dual code. To date, applications that have not been dequantized have relied on efficient classical decoders and coordinate-wise constraints. We overcome these restrictions separately. Our first contribution uses a quantum decoder to find solutions y∈(𝔽_q∖{0})^m to By=0, where B∈𝔽_q^n× m. For fixed prime q>2, Chen, Liu, and Zhandry solve this problem for random matrices with m=Ω(n^2), a regime now covered by classical algorithms. We adapt their template to codes (spanned by the rows of B) that satisfy a "two-fold multiplication property": the coordinate-wise products of pairs of codewords span a space of dimension smaller than m. Under suitable distance conditions, this allows us to solve instances with m≤ n^2−Ω(1), beyond the established guarantees of classical algorithms. We also give an efficient classical algorithm under a stronger three-fold multiplication property, leaving intermediate regimes as candidates for quantum advantage. For Reed-Muller codes punctured at random points, our algorithm finds a word in the unpunctured dual code supported exactly on those points. This works beyond known efficient classical decoding regimes. Our second contribution retains classical decoding but allows global constraints on symbol frequencies. We study "histogram-local" constraints, which specify the allowed numbers of occurrences of each symbol. For broad families, stability under resampling one coordinate yields efficient quantum algorithms for variants of optimal polynomial intersection (OPI) combining coordinate-wise and histogram-local constraints. Adapting Yamakawa-Zhandry, we prove a quantum-classical separation for these problems relative to a classical random oracle.
ER -