Skip to content
Preprint

Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability

Sep 2026 · 0 citations
Physics

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).

View source

Similar papers

Preprint Oct 2026

Membership in the cone of quantum states over time is NP-hard

A state over time (stote) pairs a state $\rho$ with a channel $\mathcal{E}$ as the Hermitian, generally non-positive operator $(\rho\otimes\mathbf{1})\star J_\mathcal{E}$. Characterizing the convex cone $\widehat{\mathcal{Q}}$ these operators generate was posed as an open problem in Hoogsteder-Riera, Calsamiglia and Wi...

Matt Hoogsteder-Riera · 0 citations
Preprint Sep 2026

Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

A deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest, and a full sample--time tradeoff that interpolates between exponential and polynomial runtime is established.

Robin Kothari, Tony Metger, Ryan O'Donnell et al. · 0 citations
Sep 2026

Norm-One Torus Decompositions and Decoding of Gashkov-Sidel'nikov Codes

Let $q=3^m$, let $K=\mathbb F_{q^2}$, and let \[\mathcal T=\{x\in K^*:\operatorname{N}_{K/\mathbb F_q}(x)=1\}.\] For both cyclic and constacyclic Gashkov-Sidel'nikov codes, we show that the set of signed parity-check column labels is precisely $\mathcal T$. Consequently, the decoding problem separates into two stages:...

Min-Jia Shi, Shi-Tao Li, Yu-Hong Xia et al. · 0 citations
Sep 2026

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

The main idea behind the algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches.

Srinivasan Arunachalam, Qi-Zhao Huang, Makrand Sinha · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.