论文标题
用于Prime-Power场的有效量子解码器
An Efficient Quantum Decoder for Prime-Power Fields
论文作者
论文摘要
我们使用Manhattan距离（非二进制字母的Hamming Metric的类似物）考虑了有限字段$ \ mathbb {f} _Q $上最近代码编号问题的版本。与其他与晶格相关的问题类似，该问题甚至是恒定因子近似。但是，我们表明，对于$ q = p^m $，相对于代码块$ n $，$ p $很小，有一种量子算法可以在时间$ {\ rm poly}（n）$中解决问题$ 1/n^2 $。另一方面，据我们所知，经典算法只能在较小的逆多项式因素上有效地解决该问题。因此，解码器对经典算法进行了指数改进，并对基于代码的密码系统（如Classic McEliece）的大型阿尔如术扩展的加密安全性限制。
We consider a version of the nearest-codeword problem on finite fields $\mathbb{F}_q$ using the Manhattan distance, an analog of the Hamming metric for non-binary alphabets. Similarly to other lattice related problems, this problem is NP-hard even up to constant factor approximation. We show, however, that for $q = p^m$ where $p$ is small relative to the code block-size $n$, there is a quantum algorithm that solves the problem in time ${\rm poly}(n)$, for approximation factor $1/n^2$, for any $p$. On the other hand, to the best of our knowledge, classical algorithms can efficiently solve the problem only for much smaller inverse polynomial factors. Hence, the decoder provides an exponential improvement over classical algorithms, and places limitations on the cryptographic security of large-alphabet extensions of code-based cryptosystems like Classic McEliece.
