软解码器中的量子优势 Quantum Advantage from Soft Decoders

Quantum Advantage from Soft Decoders

软解码器中的量子优势

https://dl.acm.org/doi/pdf/10.1145/3717823.3718319

摘要
近年来，Regev 的归约被用作一种量子算法工具，为解码问题的多种变体提供了量子优势。沿着这一研究方向，最近出现了一种名为“解码量子干涉”（Decoded Quantum Interferometry）的新量子算法设计，该算法能够在多项式时间内解决多个优化问题。他们特别研究了最优多项式插值（OPI）问题，该问题可被视为在里德-所罗门（Reed-Solomon）码上的一个解码问题。在本研究中，我们对 OPI 问题的某些实例提供了显著的改进。其中最显著的改进体现在源自格密码学的 ISIS∞问题上（基于里德-所罗门码），但我们同时也研究了 OPI 的不同约束条件。我们的结果提供了一些自然且令人信服的解码问题，我们相信在这些问题上存在量子优势。我们的证明技术涉及使用里德-所罗门码的软解码器，特别是 Koetter 与 Vardy 提出的解码算法。为了能在 Regev 归约的框架下使用该解码器，我们提出了一种新颖的通用归约方法，将伴随式解码问题转化为陪集采样问题，从而提供了一个强大且易于使用的定理，该定理推广了此前的工作，本身也具有独立的研究价值。我们还对使用 Koetter 与 Vardy 算法的 OPI 问题进行了广泛研究。

CCS 概念
• 计算理论 → 量子计算理论；
• 安全与隐私 → 密码分析与其他攻击。

关键词
量子算法，基于编码的密码学，Regev 归约，多项式插值

1 引言
1.1 背景
近年来，Regev 的归约被用作一种量子算法工具，为解码问题的各类变体提供了量子优势。Chen、Liu 和 Zhandry [3] 开启了这一研究方向，展示了如何将 Regev 归约用于算法设计。他们证明了可以在量子多项式时间内解决某些参数下的 SIS∞ 问题。尽管该量子算法在多项式时间内运行的参数范围较为极端，但目前尚无已知的经典算法能够在这些参数下解决 SIS∞ 问题。随后，Yamakawa 和 Zhandry [16] 利用本质上是一个解码问题的构造，证明了其在无结构条件下的量子优势算法。

1.2.2 使用 KV 解码器求解 S-多项式插值问题。Koetter-Vardy 解码器将使我们能够在 [8] 无法处理的参数范围内，解决比 OPI 问题更具约束性的问题。简而言之，与在 OPI 问题中试图找到一个满足大部分交集约束的多项式不同，我们现在希望满足所有的约束条件。这可以重新表述为以下的 S-多项式插值问题。

2 初步知识

2.1 符号表示

2.4 里德-所罗门码及其解码算法

具有效率解码算法的一类重要码是里德-所罗门（Reed-Solomon）码。由于我们还将关注其对偶码的解码，因此稍微扩展这一码族将更为方便，使得该码族在取对偶操作下保持不变，同时我们也能使用相同的（高效）解码算法来解码该族中的任意成员。广义里德-所罗门码（Generalized Reed-Solomon codes）正是此处合适的对象。

2.5 与里德-所罗门码相关的计算问题
我们现在关注与里德-所罗门码相关的一些具体计算问题，这些问题将是我们的研究对象。第一个问题称为 S-RSC，它是文献 [8] 中提出的最优多项式插值（Optimal Polynomial Interpolation）问题的一个略微特殊的情形。需要注意的是，我们在此考虑的是具有完整支撑的里德-所罗门码，即 = 。

3 通用归约

原文链接：https://dl.acm.org/doi/pdf/10.1145/3717823.3718319