Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability

Abstract: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=\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).

arXiv:2610.00502 [quant-ph]

(or arXiv:2610.00502v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.00502 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.