arXiv preprint ·
Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Exponential separation in sensing continuous signals via squeezing
Complexity study of the Hartle-Hawking state in JT gravity
Polarisation-resolved identification of spontaneous four-wave mixing processes in a multimode fused tapered fibre coupler
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
A Separation Between Types of Quantum Oracle Separations
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.