量子科技中心_量科网

该团队重新审视了Cheng和Wan的归约方法，该方法将有限域上的离散对数问题实例转化为Reed–Solomon码的解码问题，并研究了Regev归约如何用于求解这些实例。Regev归约将码的解码器转化为对偶码解码问题的量子求解器。其量子优势取决于对偶问题在经典计算中的难度，但这一难度难以确立。Cheng–Wan归约为这类实例提供了天然来源：求解这些实例即可求解离散对数问题。由于Shor算法已能求解离散对数，研究目标并非寻找新的量子加速，而是探究：当Regev归约应用于一个我们有独立理由相信其困难的问题时，是否能够求解离散对数？若不能，其局限何在？ 该工作将Cheng–Wan归约对Reed–Solomon码有界距离解码的困难性结论进行了推广——从求解𝔽_q^h^×中的离散对数问题扩展到求解有限阿贝尔群中的离散对数问题，并证明了即使码率渐近为零时，Reed–Solomon码的有界距离解码问题仍为𝖭𝖯困难，尽管已知的𝖭𝖯困难半径远高于Cheng–Wan解码半径。随后，该团队对Cheng–Wan实例执行了Regev归约，并用已知高效解码器进行评估。所有解码器均与Cheng–Wan阈值相差一个常数因子。在关于Cheng–Wan实例的假设下，研究人员确定了解码器为求解离散对数所需达到的QDP参数。其障碍在于效率而非可解性：完美测量（Pretty Good Measurement）可求解每个实例（包括𝖭𝖯困难实例）的相应解码问题，但该方法的实现通常需要指数级资源。