arXiv:2610.00502
Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
Seyoon Ragavan, Noah Shutty
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 $\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 algorithms. We adapt their template to codes (spanned by the rows of $\mathbf{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\leq 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.
AI Summary
The paper studies code intersection via Regev’s reduction (decoded quantum interferometry), asking whether it can avoid efficient classical decoding or accommodate non-coordinate-wise constraints. It develops separate extensions for these two restrictions. The first finds full-support kernel vectors $\mathbf y\in(\mathbb F_q^\times)^m$ satisfying $B\mathbf y=0$. For $D=\operatorname{rowspan}(B)$ of dimension $n$, let $s_2,s_3$ denote its two- and three-fold coordinate-wise product-space dimensions. A polynomial-time quantum algorithm succeeds when $d(D)\log_q(q-1)\geq2n+s_2+2$; a classical algorithm for odd $q$ succeeds under $d(D)\geq n+s_3$. The quantum decoder measures each symbol into an error-free two-element list, then relinearizes quadratic constraints using the Schur square. Randomly punctured Reed–Muller codes yield regimes with $m\leq n^{2-\Omega(1)}$, including regimes outside the classical guarantee. The second extension imposes global symbol-count constraints after coordinate-dependent alphabet relabeling. Efficient preparation of uniform constrained states, a Fourier-weight/replacement-stability identity, Poissonization, and classical list decoding give quantum algorithms. A concrete example forbids half the alphabet and requires counts $\{1,2\}$ and $\{3,4\}$ for the remaining thirds and sixths. At Reed–Solomon rate $7/8$, random public permutations give inverse-polynomial average success over prime fields. A folded-code random-oracle variant has constant quantum success but exponentially small success for polynomial-query classical algorithms, using list recovery and resistance to random histogram completions. Neither plain-model extension establishes classical hardness. The extensions are not combined; histogram guarantees average over random relabelings rather than hold worst-case. Whether the quantum-decoding construction can be dequantized remains open.
The aforementioned GPT models were used to assist with writing throughout.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.