突破!光量子验证机根据部分信息判断NP问题

图片来源：Light: Science & Applications

南京大学张利剑课题组和姚鹏晖课题组合作，统筹优化算法设计和实验架构，基于单光子和可调光学线路演示了一种适用于光子系统实现的量子算法——NP问题的量子验证算法。该研究实现了NP问题光量子验证机这一新颖的专用量子计算模型，拓展现有光学量子计算系统的应用场景，有望促进现有规模光学量子计算系统的实用化进程。

在电影《复仇者联盟3：无限战争》中，奇异博士使用时间宝石经历了14000605种可能的战斗，找到了其中唯一一种战胜灭霸的办法。实际上，奇异博士的做法是一个典型的求解可满足性问题的过程，通过遍历所有可能的解并验证其是否满足，从而寻找是否存在一种办法取得胜利。

奇异博士遍历所有可能性寻找战胜灭霸的方法。《复仇者联盟3：无限战争》剧照

布尔可满足性问题（Boolean Satisfiablity Problem, SAT），即确定一个给定的布尔表达式是否存在可满足的赋值的问题，是首个被证明并被广泛研究的NP完全问题，在线路设计、模式检验、自动证明和人工智能中具有广泛应用。在计算机科学研究中，不同的计算问题根据其内在的求解困难程度而被分类为不同的计算复杂性。其中NP复杂性是计算机科学研究的核心问题之一，包括了许多实际生活中十分重要的规划、优化等计算问题。而NP完全问题可以被简单地理解为NP复杂性类中最为困难的一类问题。

正如奇异博士寻找打败灭霸的办法需要遍历多达1400万种可能，求解NP完全问题被认为是困难的。计算机科学中被广泛相信的指数时间假设（Exponential Time Hypothesis, ETH）认为求解3-SAT问题（SAT问题的一种代表性形式）的最好经典算法需要指数级运行时间。基于指数时间假设，验证包含n个布尔变量的3-SAT问题至少需要O(n)比特长度的信息。否则，验证者可以简单地遍历所有可能的证据，从而得到一个亚指数级的3-SAT求解算法。也就是说，验证3-SAT问题解的对错基本上需要解的全部信息。

令人惊喜的是，如果将问题的解编码在量子态中并使用量子计算机验证，这一信息长度上的限制则不再适用。2008年Aaronson等人提出了次线性复杂度的3-SAT问题量子验证算法，随后一些变体和优化算法也被陆续提出。这意味着仅通过问题解的部分信息就能判断出解的对错，这在经典计算中被认为是不可能的任务，可以突破ETH所施加的限制。

基于量子信息理论进行的量子计算能够在计算任务中突破经典模型的限制，这一巨大潜力推动了近年来量子计算的算法理论和实验技术的不断发展。量子计算领域当前正致力于寻找合适的途径，在现有规模有噪声量子计算系统上解决具有广泛研究兴趣与实际应用价值问题。光子具有丰富的自由度和更高维度，通过对多自由度的利用和调控，可以突破传统的量子比特模型的限制，在高维度希尔伯特空间中进行信息的编码与处理。这些特点使得光子系统适用于实现高维度、低纠缠、线性操作的量子算法。

近日，南京大学现代工程与应用科学学院张利剑课题组和计算机科学与技术系姚鹏晖课题组合作，结合算法理论和量子光学实验技术，利用光子系统的优势设计并实现了NP问题光量子验证机，演示了可满足性问题的量子验证算法。

该成果以“Quantum verification of NP problems with single photons and linear optics”为题发表在Light: Science & Applications。

QMA(2)证明系统示意图

研究人员首先从算法理论研究出发，结合3-SAT量子验证算法和直积态判定算法，并进一步针对实验进行优化，发展了适用于光子系统实现的两证明者完整量子验证算法，包括满足性测试、均匀性测试、对称性测试和直积态测试四项测试。该算法考虑量子多项式时间可验证问题，由quantum-Merlin-Arthur（QMA）复杂性来定义，是NP复杂性的量子类比。在QMA(K)证明系统中，K个计算能力强大的、相互之间不进行交流的证明者（称为Merlin），发送K个相互之间非纠缠的量子态作为量子证据给一个计算能力有限的验证者Arthur。Arthur在他的量子计算机上验证证据并做出接受或拒绝证据的决定。

NP问题光量子验证机的实验实现

实验上，研究人员采用光子路径、偏振等多自由度的混合编码方式，设计并搭建了可调节光学线路，进行高维度量子信息的编码与处理。进而以包含6个变量、8个子句的布尔表达式为例，演示了对特定3-SAT问题子句集的量子验证，并分析了可满足表达式、不可满足表达式、欺骗型证明者等不同情况的结果，验证了量子验证机的完备性与可靠性。另外，研究人员还通过多模式Hong-Ou-Mandel（HOM）干涉实现了该算法组成部分之一——高维量子态的光学交换测试。实验结果显示，基于单光子编码的光量子验证机可以有效地执行对3-SAT问题布尔表达式的验证这一计算任务。

该研究将光学量子计算的能力拓展至证明系统这一重要的计算模型，突出了光子系统在实现计算空间复杂度上新型量子优势的能力。通过当前光量子技术的进一步发展，可以期待该方案在不远的将来拓展至更大的问题规模。量子验证机具有诸多的发展前景，包括对不同证明系统的实验研究（如QMA、QAM、QIP、MIP*等），启发基于验证者的量子算法以及应用于量子云计算等。该研究明确了基于光子系统的有噪声中等规模量子技术在特定计算问题上的优势，为探索量子计算的实际应用提供了新思路与新方案，同时也为计算复杂性与量子物理基础问题的研究提供了新的工具。

本文第一作者为张傲男，通讯作者是姚鹏晖教授和张利剑教授