pipette
ENEnglish

Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability

Seyoon Ragavan, Noah Shutty

Preprint

En palabras de los autores

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 to , where . For fixed prime , Chen, Liu, and Zhandry (Eurocrypt 2022) solve this problem for random matrices with , a regime now covered by classical algorithms. We adapt their template to codes (spanned by the rows of ) with a "two-fold multiplication property": the coordinate-wise products of pairs of codewords span a space of dimension much smaller than . 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).

Resultado principalLimitación que admiten los autores

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.