王粲 陆朝阳 陈明城†

1)(中国科学技术大学近代物理系,合肥微尺度物质科学国家研究中心,合肥 230026)

2)(中国科学技术大学,中国科学院量子信息与量子科技前沿卓越创新中心,上海 201315)

1 引言

计算是一个物理过程,计算过程和能力受到物理定律的限制[1].例如,擦除一个比特信息的操作受到热力学限制,存在最小能耗[2].计算科学中,一个被广泛接受的假设——扩展丘奇图灵论题提出,所有物理上合理的计算过程都可以用通用图灵机来有效替代[3],同时这也定义了经典计算可以有效求解的问题类别,即P 问题[4].当我们在计算过程中引入量子力学原理,通过量子叠加和量子干涉,量子计算可以有效求解P 问题之外的问题.例如,量子Shor 算法可以求解的大数分解被认为是非P 问题[5]; 量子采样算法也被认为位于P 问题之外,并且在近期实验工作中被实现,展示了量子计算的优越性[6–9].

量子计算是目前在物理原理内已知的最强的计算范式[10].考虑到计算的能力受到物理原理的制约,同时很多重要问题类别,比如NP-complete问题[11],处在量子计算能有效求解的范围之外,因此研究量子计算的进一步扩展是一个很有趣的基础问题.

为了扩展量子计算,相对论物理相关的新奇操作是一类重要候选.其中闭合类时曲线概念引起了广泛的兴趣[12],它可以实现量子态沿着封闭的类时曲线传输.闭合类时曲线引入了时间旅行的能力,量子态的闭合类时曲线在数学上通过自洽性方程来定义[13],并在最近的实验中得到模拟演示[14,15].和量子计算模型结合后,可以扩大量子计算的可求解问题类别[16].

相比于量子态的时间旅行,这里我们引入另一种基于量子门的时间旅行.首先通过量子门线路图形语言来形象展示时间旅行的量子门,并介绍其如何物理地通过张量网络模拟实现,最后设计新的量子算法来求解NP-complete 问题,展示超越正统量子计算的能力.

2 扩展的量子计算机

2.1 时间旅行的量子操作门

量子计算的标准通用量子门线路模型是通过单量子比特门和双量子比特CNOT 门来搭建,量子比特的状态信息是从左往右逐步流动[10].其中双量子比特门需要在对齐的同一个时间窗口上进行操作,如图1(a)所示.而在图1(b)中,展示了打破这种时间对齐的CNOT 门,并且同时展示了作用在一个量子比特的过去或未来的CNOT 门操作.我们把这种新奇的CNOT 门称作进行了时间旅行的CNOT 门.

包含时间旅行量子门的门线路打破了量子信息的流动顺序,因此无法在物理上直接实现.通过将量子门线路解释成张量网络,可以在无时间旅行能力的系统中等效地模拟实现这类门线路的输出[17].如图2 所示,我们在时间旅行门的拐角上引入两个分支,作为一个新的辅助量子比特的输入和输出.如果将这个辅助量子比特初始化和投影测量到态上,同时在这之间,辅助比特和时间旅行CNOT 门的起点和终点位置的量子比特分别实现CZ 和CNOT 门,那么辅助量子比特之外的输出就等效于包含时间旅行量子门线路的输出.

图2 等效的张量网络表示,借助辅助量子比特(蓝色线)可以非确定性地模拟实现时间旅行CNOT 门 (a)示例1,在时间旅行门的两个拐角,引入两个分支,认作一个辅助量子比特(蓝色线),将其初态制备到 |+〉态并同时后选择投影到〈+| 态,右图是相应的标准量子门线图表示; (b)示例2,相比示例1 时间旅行门作用在同一个物理量子比特上,示例2 展示了其作用在不同物理量子比特上的情形Fig.2.Equivalent tensor network representation.Using auxiliary qubits (blue line),the implementation of a time-travelling CNOT gate can be nondeterministically simulated: (a) Example 1,where we introduce two branches at the two corners of the time-travelling gate and consider an auxiliary qubit (blue line) prepared in the |+〉 state and subsequently projected to the 〈+| state,the right diagram is the corresponding standard quantum circuit representation; (b) example 2,in contrast to example 1,demonstrates its operation on different physical qubits.

需要特别注意的是,我们所引入的时间旅行量子门是确定性的操作.而模拟实现的代价是借助辅助比特投影到,测量后选择是概率性的.这是时间旅行打破物理原理的代价,在真实物理体系里只能是非确定性的实现.

2.2 更强大的扩展量子算法

我们引入时间旅行量子门的目的是,通过尽可能小的自然的改动,来实现扩展的量子计算.下面将描述一个扩展算法,可以在多项式时间求解布尔可满足性SAT 问题(Boolean satisfiability problem)[11].SAT 问题是计算机科学中的经典问题,属于NP-complete 类别.SAT 问题由n个布尔变量m个子句组成.求解该问题需要找出n个布尔变量的一组值使得m个布尔逻辑子句同时成立.

本文量子算法由三部分构成.其中第一部分是n个量子比特的寄存器,用于存储SAT 问题的布尔变量,初始化为 |0〉⊗n.第二部分是m个量子比特,用于标记各个逻辑子句是否满足,初始化为 |1〉⊗m.第三部分包含1 个标记量子比特,初始化为 |1〉,用于标记上面的m个子句是否全被满足,如果全部满足,就反转该标记比特.该部分的线路包含了时间旅行的CNOT 门,具体如图3(a)所示.

图3 求解SAT 问题 (a)设计的量子算法,门线路的深度线性正比于SAT 问题规模,即子句的数量 m,最上面n个量子比特作为SAT 问题解的寄存器,中间 m 个量子比特用于标记 m 个逻辑子句是否被独立满足,最后一个量子比特标记位用于判断是否所有的逻辑子句被同时满足; (b)最后标记位上的时间旅行CNOT 门的运行细节,这里 p 对应张量网络解释中的后选择概率,当算法中的标记位为 |1〉时,相应的辅助量子比特的后选择投影概率为0; 而标记位为 |0〉时,后选择投影概率为1,算法最终只输出标记位为 |0〉的情况,这对应上面寄存器里只存储了正确的解Fig.3.Solving the SAT problem.(a) The designed quantum algorithm,with the depth of the circuit linearly proportional to the SAT problem size,i.e.,the number of clauses m .The top n qubits serve as registers for solving the SAT problem,the middle m qubits are used to mark whether m logical clauses are independently satisfied,and the last qubits is used to determine whether all logical clauses are simultaneously satisfied.(b) Operational details of the time-travelling CNOT gate on the final marking qubit,here, p corresponds to the posterior-select probability in tensor network interpretation: When the marking qubit in the algorithm is |1〉,the corresponding auxiliary qubits have a posterior-select projection probability of 0;while the marking qubit is |0〉,the posterior-select projection probability is 1.The algorithm ultimately only outputs the case where the marking qubit is |0〉,corresponding to storing only the correct solutions in the registers above.

线路图中,黄色的m个竖直框代表着多比特的受控NOT 门,由具体SAT 问题的各个子句具体内容决定.如果一个子句没有满足,那就通过多比特的受控NOT 反转对应子句的量子比特.

算法运行时,布尔变量的寄存器通过哈德玛门制备到所有可能的均匀叠加态上[10].第一种情况:如果寄存器里的布尔变量没有满足全部子句,标记位将保持 |1〉,时间旅行CNOT 门执行,通过上面介绍的张量网络计算方法(如图3(b)所示),时间旅行的成功概率p=0,实现了完美镇压寄存器里的错误解的概率幅.第二种情况: 如果寄存器里的布尔变量满足全部子句,标记位则被反转成 |0〉,时间旅行CNOT 门没有执行,寄存器里的正确解不受影响.在张量网络解释中算法总的后选择成功率为K/2n,K为SAT 问题满足性解的个数; 在时间旅行门的概念中,成功率为1.因此算法最后,布尔变量寄存器只确定性地保留了第二种情况的布尔变量组合,并随后通过测量随机塌缩输出任意一个满足所有子句的布尔变量组合.

该算法的复杂度正比于SAT 问题的规模,是线性复杂度的.门线路的深度正比于SAT 问题子句的数量.正统的量子计算可以有效求解的问题类别介于P 问题和NP 问题之间,这里设计的扩展量子算法有效求解了NP-complete 的SAT 问题.这也表明了在时间旅行量子门的参与下,计算复杂度类别P=NP,成功展示了时间旅行量子门具有超越正统量子计算的计算能力.

3 总结

计算机的能力受到物理定律的制约,量子计算机扩展了经典计算机可有效计算问题的范围.通过引入相对论时间旅行操作,相对论量子计算机可以在理论上进一步扩展量子计算的能力.在以往的工作中,时间旅行是通过闭合类时曲线实现的,多伊奇通过优雅的自洽性方程将其结合到量子演化过程中.本工作通过量子门线路的图形语言引入了自然的量子门的时间旅行扩展,并通过简洁的算法示例展示了其对量子计算能力的显著扩充.

本文介绍的张量网络等效表示方法,为实验模拟提供了具体的实现方案.同时,也预期时间旅行的量子门在其他量子任务中也起到促进作用,包括实现确定性的非正交量子态甄别[18,19]、量子态克隆[20,21]等.