{"id":"arxiv/2610.00502","url":"https://arxiv.org/abs/2610.00502","tags":["quant-ph"],"score":0,"title":"Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability","domain":"quant-ph","source":"arxiv","authors":["Seyoon Ragavan","Noah Shutty"],"reviews":0,"subject":"quant-ph","summary":"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 $\\mathbf{y}\\in(\\mathbb{F}_q\\setminus\\{0\\})^m$ to $\\mathbf{B}\\mathbf{y}=0$, where $\\mathbf{B}\\in\\mathbb{F}_q^{n\\times 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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}