Aram Harrow 并不能确定他究竟是个物理学家, 还是计算机科学家. 他早年在 MIT 获得了学士学位(物理和数学)和博士学位(物理), 后来曾在 University of Bristol(数学和计算机科学) 和 University of Washington(计算机科学)拿到过教职. 然而, 他现在仍然是量子计算的信徒.
(以下是正文部分.)
量子计算是验证困难的物理实验的正确性的绝佳方式, 但是直到真正的量子计算机出现之前, 计算机科学家们需要了解量子信息吗? 事实上, 量子计算不仅是一个关于新的计算设备的理论, 而且也是一种崭新而令人惊讶的理解世界的方式. 在这篇文章中, 我会介绍量子计算的来源, 量子计算是什么, 以及我们会从中知道什么.
量子计算的发展
在长达数个世纪的时间里, 我们以确定性的观点来审视世界, 这使得我们把它想象成一个非常复杂的机械装置. 但是, 当计算机变得无处不在的时候, 它提供了新的比喻手段, 并且改变了我们思考自然科学、数学甚至社会科学的方式. 计算机不仅帮助我们解决问题, 而且在建造它们和编程的过程中, 它也以全新的思考方式启发了我们.
比如说, 我们将 DNA、语言或者认知这些纷繁复杂的现象, 视为演化出对编码压缩和纠错的信息传输机制. 自博弈论和经济学始, 开始出现与计算的效率和计算能否实现相关的概念, 正如 Kamil Jain 关于纳什均衡的著名评论, “如果你在你的笔记本电脑找不到它, 那么它就不可能在市场上出现.” 计算机科学也被这些领域的目标所改进. 而对数学, 其自身与计算有效性也日益引发关注, 造就了与计算机相关的蓬勃发展的新兴领域: 信息论, 图论和统计学. P-vs-NP 问题是最新的 Clay 千禧年问题, 它的解决将会为求解数学中的古老谜题提供新的曙光: 寻找证明如此困难的原因是什么?
事后想来, 如此这般的计算观点似乎是非常自然的. 但当计算机第一次出现的时候, 即使是预言了其在商业上的巨大成功的寥寥数人, 也无法预见它掀起的思维方式革命. 譬如熵的概念(熵是压缩和纠错编码中的核心概念)在 Gauss 的时代, 或者中世纪的阿拉伯人, 甚至是古希腊人就能轻易提出. 但是它直到十九世纪才有了实践意义下的进一步发展, 当我们的热力学理论足够理解蒸汽机的时候. 当 Bell 实验室借研究密码学之名, 在战争时期雇佣了 Claude Shannon 之后, 同样的事情也发生在了二十世纪. 而这样的事情无独有偶, 也并非局限在计算机科学之中. Einstein 在专利局当小职员的经历帮助他想出了相对论, 比如高速铁路网中的时钟同步就曾是个重要的工程问题, 以及对时钟及火车的比喻为他著名的思想实验提供了素材. 总而言之, 自然科学的进展总是跟随着技术的发展, 因为发明总是带给我们全新的认知世界的方式, 以及亟待理论解释的新现象.
关于量子计算的故事大抵亦复如是. 量子力学的提出在二十世纪初叶, 而它现在广泛使用的形式则是建立于 1930 年. 但是量子力学潜在的计算上的优势却没有顺势被发现, 直到物理学家们试图在计算机上模拟量子力学. 为了这样的模拟, 他们尝试考虑实际问题: 当一个孤立系统 (譬如极化后的光子) 可能只需要用两个复数描述 (比如极化后的水平和竖直分量的幅值), 那么完全描述
个这样的系统需要的不是
而是
个复数, 尽管在测量后我们只能提取出个比特. 针对这个问题, 物理学家们发展了它的解析解以及物理模拟的近似解, 而这些解都与大量的实际应用相关.
量子力学中以指数增长的态空间, 应该自然地联系着更多的计算资源, 甚至远远超过我们的想象. 除此之外, 它和量子力学的新奇特性看起来更像是某种限制, 甚至是"造化弄人". 譬如 Heisenberg 不确定性关系被认为是对测量的限制. 而诸如量子纠缠的现象则被认为是量子力学基础中的一部分, 或者是关于量子力学的哲学,
但是并没有什么具有可操作性的关联. 直到量子计算和量子密码学, 在上世纪七十年代和八十年代被各自独立提出.
( 图为 Richard Feynman )
量子计算 (或者更准确的说, 利用量子力学优势的计算) 来自 Richard
Feynman 在1982 年的建议: 既然传统计算机需要用指数级别的资源来模拟量子力学, 也许一台基于量子力学的计算机能够更为有效的完成任务. David
Deutsch 在 1985 年对这一想法进行了形式化, 他令人惊讶地展示了一个量子计算机与经典计算机相比存在优势的例子 (计算两比特的异或), 当然, 这个问题在表面上似乎和量子力学并没有什么关系. 很快一系列能有效加速算法被提出, 但都是针对人为设计的问题. 直到 1994 年, Peter Shor 提出了多项式时间的整数分解算法.
( 图为 David Deutsch )
而在更早些的时候, 即 1970 年, 还是研究生的 Stephen Wiesner 提出了利用 Heisenberg 约束测量, 来防止对方窃取秘密信息的方法. 因而, 量子密码学应运而生, 尽管 Wiesner 的论文几乎被所有期刊拒收, 并且这样的想法一直并不为人所知. 直到 Charles Bennett 和 Giller Brassard 在 1984 年发表了一篇关于量子密钥分发 (Quantum Key Distribution) 的工作, 甚至这个工作也一直没有受到关注, 直到他们的想法在 1991 年获得实验证实.
这一关键的概念上的演进, 使得量子计算和量子密码学, 开始被用于思考量子力学在操作意义上与信息相关的影响, 而不是被作为某种极限、好奇心或者是悖论的来源. 一旦这样的变化完成, 技术层面的量子信息会变得比早先发展的量子力学更为简单, 就像是上世纪五十年代完成的对量子力学和狭义相对论的统一.
原文发布时间为：2017.02.01
本文作者：Climber.pI
本文来源：知乎，如需转载请联系原作者。
