线性代数应用于计算机科学例子,为什么计算机科学家们应该了解量子计算?（三）：算法棱镜折射出的科学...

待我称王封你为后i 2022-10-09 00:58 143阅读 0赞

译者按: 本文译自 Aram Harrow 的 Why now is the right time to study quantum computing(原文链接), 经 Aram 授权翻译. Aram 最广为人知的工作应该是求解线性方程组的 HHL 算法(Scott 的介绍), 这几乎是现在绝大多数的量子机器学习算法的基础. 他现在是 MIT 物理系的助理教授.

本节介绍了作者如何从量子信息观点看待量子力学, 比较了能量最小化问题在经典情形和量子情形下求解的困难程度. 以及从能隙与激发的关系得到的扩展图的量子对应, 并试图将其用于量子系统的经典模拟. 最后作者介绍了量子信息与张量计算之间的联系, 并认为量子信息会带给我们对线性代数和概率的不同理解. 文中若存在不准确之处, 欢迎指正.

(续上节)

算法棱镜折射出的科学

毋庸置疑, 大规模量子计算机的出现, 将会引起我们思考自然科学的方式的变化, 这样的变化是巨大且无法预测的. 但是, 即使没有真正的量子计算机, 我们到目前为止在理论上的进展, 仍然能够引起不少观念上的进步.

比如这样的想法就是一个主要的进步, 从物理学中分离量子力学的信息部分. 就像现在做的, 我们总是一起教授它们,  这样一来糅合了反直觉的概念和数学完备的图像, 比如说我们用偏微分方程中的 Schrodinger 方程来描述测量和纠缠, 就像生活在

![equation?tex=%5Cmathbb%7BR%7D%5E3][equation_tex_5Cmathbb_7BR_7D_5E3]中的无穷维函数空间一样. 而概率似乎仅仅出现在教授统计力学的时候, 并且学生们学到的第一个分布往往就是理想气体的热力学分布. 相反, 如果我们先学到了量子力学关于信息的意义, 再用这样的框架来解释原子, 光子和其他物理学现象, 那么我相信量子力学会起到更大的作用.

刚刚起步的学生们, 并不是唯一能够从量子信息观点中获益的量子力学的实践者. 很多涉及量子力学的现象, 也与这样的一些问题相关, 比如熵、纠缠或者有物理上相关性的关联, 但它们最好以信息方式来描述. 寻找量子系统(比如逐对相互作用的个量子比特)的最低能态就是个早年的成功例子. 对于经典系统, 这样的问题是 NP-Complete的, 除非在特殊情况下, 比如这样的系统构成直线或者树的情形. 而对于量子系统, 能量最小化问题(Energy-minimization problem)是 QMA-Complete 的. QMA 代表了"量子 Merlin-Arthur 博弈(Quantum Merlin-Arthur games)", 并且我们相信量子计算机很难解决它, 就像经典计算机难以解决 NP 中的某些问题一样.

![none.gif][]

为什么计算机科学家们应该了解量子计算?(三)：算法棱镜折射出的科学-3.jpg (51.25 KB, 下载次数: 8)

2018-5-11 00:26 上传

(译者注: P与 BQP, 以及 NP 与 QMA 之间的类比关系见上图. 关于 QMA 的更多解释参见题图: Prover 拥有无限的计算能力, 他总是给出问题的证明, 并且想法设法让 Verifier 觉得证明是对的. 但 Verifier 的计算能力有限, 她只相信自己算出来正确的东西.)

这给出了很多根据经验观察, 总结而出的物理现象的理论判据, 比如说找玻璃的基态总是很困难的. 令人惊讶地是,  即使对于只有相邻点对有相互作用的直线情形, 能量最小化问题仍然是 QMA-Complete 的. 这与物理学家们的直觉相违背, 即一维的情形不总是容易的.

至于其他情形, 量子信息观点也给出了些正面的结果, 甚至是新的经典算法. 一个相关的例子是能隙(Energy gap), 即系统的最低能级和系统的第二低能级之间的间隙. 从物理上说, 能隙大小对应于一次激发的难易程度. 对于一些物质的激发, 像是光子或者固体的振动, 它们不会产生物质变化; 而在半导体中移动的外部电子, 则会得到有效的质量. 从这样的图象中, 我们希望小的能隙会对应于长程关联(Long-range correlation), 而大的能隙则意味着关联会迅速的减弱. 可现实中的结果却是更加微妙的. 对于一个可观测量, 我们考虑特定点的磁场强度, 当能隙很大的时候, 关联确实会迅速的减弱. 但是如果将系统状态作为整体考虑, 它仍然表现了长程关联. 下面我们来给出一个这样的情形的恰当类比, 考虑一百万比特的空间, 在其上固定一千个随机的一一映射函数. 如果这样的函数

![equation?tex=f][equation_tex_f]是随机选择的, 那么有序对

![equation?tex=%28x%2C+f%28x%29%29][equation_tex_28x_2C_f_28x_29_29]的互信息会接近极大值, 这意味着知道会把可能性的数量 从

![equation?tex=2%5E%7B1%2C000%2C000%7D][equation_tex_2_5E_7B1_2C000_2C000_7D]降到

![equation?tex=1000][equation_tex_1000]. 而在另一方面, 中的一个独立的比特, 将会和中的任意一个特定的比特几乎毫无关联. 即使我们把这样的随机函数被换成了有合适参数的扩展图(Expander Graph), 这样的论断仍然有效. 在这样的直觉的指引下, 研究者们想出了扩展图的量子对应, 即用大的能隙和任意独立可观测量之间迅速减弱的关联来表示系统, 但是系统的不同部分之间的互信息, 在数值上仍然十分巨大大. 为什么我们应该关系这些不同种类的关联, 除了对用理论预测真实世界中的可观测量的渴求? 在经典计算机上模拟量子系统, 就是这样一个令人兴奋的应用. 如果一个量子比特系统中没有纠缠, 那么描述它所用的参数数量将不再是

![equation?tex=2%5En][equation_tex_2_5En], 而是

![equation?tex=2n][equation_tex_2n]. 如果这些量子比特被排成一条直线, 并且它们之间的关联被大致限制在某个很短的距离

![equation?tex=k][equation_tex_k], 那么参数的数量的规模将会是

![equation?tex=n+%5Ccdot+exp%28k%29][equation_tex_n_5Ccdot_exp_28k_29]. 因此, 控制量子系统中的关联, 也能够帮助我们有效的模拟它.

这条研究主线可以被视为一个大型项目的一部分, 即把量子系统划分能被经典计算机有效模拟的部分(这么说是因为它们还是会在一定程度上纠缠), 并且这也能够实现通用量子计算. 在另一方面, 对于一些系统来说, 它们的计算复杂性明显在经典模拟和通用量子计算之间. 这些系统包括不发生相互作用的光子, 也包括噪音比率过高的量子纠错码(Quantum Error-correcting Code)的作用, 但是太少以致于难以消除大规模纠缠的可能性. 分析这些边界情形的复杂性是未解决问题(Open Problem)的一个令人着迷的来源.

量子信息观点在科学上的益处也不仅仅局限于量子力学. 一些重要的问题表面上看起来和量子力学无关, 但和多维阵列的线性代数相关. 比如说, 给定一个 由数

![equation?tex=A\_%7Bijk%7D][equation_tex_A_7Bijk_7D]组成的三维集合(collection), 这里的

![equation?tex=i%2Cj%2Ck][equation_tex_i_2Cj_2Ck]在

![equation?tex=%5C%7B1%2C%5Ccdots%2Cn%5C%7D][equation_tex_5C_7B1_2C_5Ccdots_2Cn_5C_7D]中取值, 那么类似计算下面的最大奇异值问题有多难? 下式遍历了所有单位矢量

![equation?tex=x%2C+y%2C+z][equation_tex_x_2C_y_2C_z].

![equation?tex=%5Cmax+%5Csum\_%7Bi%2Cj%2Ck%7D+A\_%7Bi%2Cj%2Ck%7D+x\_i+y\_j+z\_k][equation_tex_5Cmax_5Csum_7Bi_2Cj_2Ck_7D_A_7Bi_2Cj_2Ck_7D_x_i_y_j_z_k]

对于这样的问题, 如果要求的计算精度在

![equation?tex=1%2Fpoly%28n%29][equation_tex_1_2Fpoly_28n_29]的话, 那么它是 NP-Hard 的. 而对于大多数更真实的情况, 即只需要常数精度近似的话, 已知的唯一结果用到了量子技术, 就像大多数有希望的经典算法一样. 量子信息观点的有效性是一个可能的理由, 这来自于此处的多维阵列的自然对应就是纠缠态; 并且随着我们对纠缠的量化理解日益深入, 它所导出的有关线性代数的结果的应用会愈加广泛. 线性代数的重要性似乎是获益于理论计算机科学. 这样的例子包括在布尔立方体(Boolean cube)上的 Fourier 分析, 和用图和矩阵的观点来看待相互作用, 它们因而混合了组合和代数的图像. 在未来, 我希望我们关于线性代数和概率的观点的形成, 会越来越受到来自量子信息中的工具的影响.

最后, 量子信息对于计算机科学的绝大多数贡献都是理论意义上的, 因为现在并没有大规模量子计算机. 但是一旦我们拥有了它, 我们希望理论科学家们能从中得到一些启示, 并加以解释, 就像经典计算机中那些启发式的成功例子, 如单纯形法(Simplex). 举个例子, 我们在 Shor 算法中发现了周期结构, 并且它能够被用于获得一系列指数级加速. 而在将来, 我们希望把类似寻阶(Period-finding)的工具用于数据分析, 这就像今天广泛使用的线性回归一样. 绝大多数新工具在一开始都被认为是完全反直觉的, 但当我们深入理解了它们之后, 它们就昭示着科学而系统的看待世界的全新方式.

(全文完)