Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
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).
Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.