奇客 量子算法解决一类新问题

1994 年数学家 Peter Shor 想出了如何让量子计算机完成普通经典计算机无法做到的事情。这项工作表明，原则上，一台基于量子规则的机器可有效地将大数分解为质因数——对于经典计算机来说，这是一项非常困难的任务，大数质因数分解是今天大部分互联网安全系统的基础。乐观的情绪随之而来。那时研究人员认为，也许我们能发明出可以解决各种不同问题的量子算法。但进展并不顺利。卡内基梅隆大学的 Ryan O’Donnell 表示：“这有点令人失望。”“人们会说，‘这太棒了，我确信我们会找到各种别的惊人的算法。’没有。”科学家仅在一个被称为 NP 的标准集中发现了一个单一的、狭窄的问题类别可以显著加速，这意味着它们有了有效的可验证解决方案——例如因式分解。近三十年来，情况皆是如此。今年 4 月，研究人员发明了一种全新的问题，量子计算机应该能比经典计算机更快地（速度指数级提升）解决该问题。它涉及仅根据混乱的输出来计算复杂数学过程的输入。这个问题是独立的还是许多其他问题中的第一个尚待确定。