量子科技中心_量科网

随机经典线性码的解码问题被广泛认为具有较高难度。虽然当编码率足够快速趋近于零时存在略低于指数时间的算法，但所有已知恒定编码率下的算法仍需要指数时间。相比之下，随机量子稳定子码的解码复杂度长期以来始终是个悬而未决的问题。该工作填补了我们对于随机量子码与随机经典码算法难度差异的理解空白。研究团队证明：即使仅含单个逻辑量子比特的随机稳定子码，其解码难度至少与恒定编码率下（即最困难情形）的随机经典码解码相当。这一结果表明，最简单的随机量子解码问题至少与最困难的随机经典解码问题同等复杂，并证明在任何编码率下对典型稳定子码进行亚指数时间解码的算法，都将立即引发密码学领域的突破性进展。 更广泛而言，该工作还刻画了稳定子码的诸多其他计算复杂性特征。尽管经典解码存在随机自归约性，但研究团队证明量子情形下随机自归约存在显著障碍——这一结论源自对克利福德熵和泡利混合时间的新界限（这些发现可能具有独立价值）。作为补充结果，该团队展示了其他实际可实现的归约（例如搜索问题与判定问题之间的归约）。同时研究表明，量子简并性等量子现象会导致稳定子码解码的多种合理定义（这些定义在经典情形下完全等价）具有不同或非平凡等价的复杂度。