Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability

Regev’s reduction is a quantum algorithmic framework for finding 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 specifying a set of allowed values for each coordinate. We push past these two restrictions separately via two separate contributions. 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 (Eurocrypt 2022) solve this problem for random matrices with $m=\mathrm{\Omega }(n^2)$, a regime now covered by classical algorithms. We adapt their template to codes (spanned by the rows of $\mathbf{B}$) with a two-fold multiplication property'': the coordinate-wise products of pairs of codewords span a space of dimension much smaller than $m$. 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 of these constraints, we show that a uniformly random satisfying vector remains satisfying with constant probability after resampling a uniformly random coordinate. This stability provides sufficient Fourier mass at decodable Hamming weights, yielding efficient quantum algorithms for variants of optimal polynomial intersection (OPI).