量子科技中心_量科网

Chen、Liu和Zhandry [CLZ22]提出了|S⟩|LWE⟩和|C⟩|LWE⟩问题，作为带错误学习问题的量子类比，旨在构建非均匀短整数解（ISIS）问题的量子算法。后续的几项研究已利用此框架在特定情况下构建了新的量子算法。然而，这些问题之间的普遍关系仍不明确。 本文研究了|S⟩|LWE⟩与ISIS之间的等价性。该团队首次提出了从ISIS到|S⟩|LWE⟩的完全通用归约，即使底层算法存在错误也依然有效。随后，该团队探讨了反向关系，引入了|C⟩|LWE⟩的非均匀变体，记为|I⟩|C⟩|LWE⟩，并证明|I⟩|C⟩|LWE⟩可归约至|S⟩|LWE⟩。最后，该团队证明在特定可恢复性条件下，针对ISIS的算法可转化为针对|S⟩|LWE⟩的算法。该团队通过调整已知的(I)SIS∞算法，在字母表大小q为2的小次幂时，实例化了这一反向归约，从而构建了针对|S⟩|LWE⟩的量子算法，复现了Bai等人[BJK+25]的部分结果。因此，该团队的研究结果阐明了|S⟩|LWE⟩与ISIS之间归约的格局，既展示了它们的紧密联系，也揭示了证明完全等价性所面临的剩余障碍。