为什么计算机科学家们应该了解量子计算?（三）：算法棱镜折射出的科学-白红宇

算法棱镜折射出的科学

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

比如这样的想法就是一个主要的进步, 从物理学中分离量子力学的信息部分. 就像现在做的, 我们总是一起教授它们, 这样一来糅合了反直觉的概念和数学完备的图像, 比如说我们用偏微分方程中的 Schrodinger 方程来描述测量和纠缠, 就像生活在 $\mathbb{R}^3$ 中的无穷维函数空间一样. 而概率似乎仅仅出现在教授统计力学的时候, 并且学生们学到的第一个分布往往就是理想气体的热力学分布. 相反, 如果我们先学到了量子力学关于信息的意义, 再用这样的框架来解释原子, 光子和其他物理学现象, 那么我相信量子力学会起到更大的作用.

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

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

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

至于其他情形, 量子信息观点也给出了些正面的结果, 甚至是新的经典算法. 一个相关的例子是能隙(Energy gap), 即系统的最低能级和系统的第二低能级之间的间隙. 从物理上说, 能隙大小对应于一次激发的难易程度. 对于一些物质的激发, 像是光子或者固体的振动, 它们不会产生物质变化; 而在半导体中移动的外部电子, 则会得到有效的质量. 从这样的图象中, 我们希望小的能隙会对应于长程关联(Long-range correlation), 而大的能隙则意味着关联会迅速的减弱. 可现实中的结果却是更加微妙的. 对于一个可观测量, 我们考虑特定点的磁场强度, 当能隙很大的时候, 关联确实会迅速的减弱. 但是如果将系统状态作为整体考虑, 它仍然表现了长程关联. 下面我们来给出一个这样的情形的恰当类比, 考虑一百万比特的空间, 在其上固定一千个随机的一一映射函数. 如果这样的函数 $f$ 是随机选择的, 那么有序对 $(x, f(x))$ 的互信息会接近极大值, 这意味着知道 $x$ 会把 $f(x)$ 可能性的数量从 $2^{1,000,000}$ 降到 $1000$ . 而在另一方面, $x$ 中的一个独立的比特, 将会和 $f(x)$ 中的任意一个特定的比特几乎毫无关联. 即使我们把这样的随机函数被换成了有合适参数的扩展图(Expander Graph), 这样的论断仍然有效. 在这样的直觉的指引下, 研究者们想出了扩展图的量子对应, 即用大的能隙和任意独立可观测量之间迅速减弱的关联来表示系统, 但是系统的不同部分之间的互信息, 在数值上仍然十分巨大大. 为什么我们应该关系这些不同种类的关联, 除了对用理论预测真实世界中的可观测量的渴求? 在经典计算机上模拟量子系统, 就是这样一个令人兴奋的应用. 如果一个 $n$ 量子比特系统中没有纠缠, 那么描述它所用的参数数量将不再是 $2^n$ , 而是 $2n$ . 如果这些量子比特被排成一条直线, 并且它们之间的关联被大致限制在某个很短的距离 $k$ , 那么参数的数量的规模将会是 $n \cdot exp(k)$ . 因此, 控制量子系统中的关联, 也能够帮助我们有效的模拟它.

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

量子信息观点在科学上的益处也不仅仅局限于量子力学. 一些重要的问题表面上看起来和量子力学无关, 但和多维阵列的线性代数相关. 比如说, 给定一个由数 $A_{ijk}$ 组成的三维集合(collection), 这里的 $i,j,k$ 在 $\{1,\cdots,n\}$ 中取值, 那么类似计算下面的最大奇异值问题有多难? 下式遍历了所有单位矢量 $x, y, z$ .

$\max \sum_{i,j,k} A_{i,j,k} x_i y_j z_k$

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

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

原文发布时间为：2017.02.01

本文作者：Climber.pI

本文来源：，如需转载请联系原作者。