-
Quantum computing can solve problems that are difficult to solve in classical computing, expanding the range of problems that can be effectively computed within the allowable range of classical physical principles, and posing a challenge to the extended Church-Turing thesis in classical computing. Here, we discuss an interesting question: how to achieve more powerful computers by breaking through the limitations of physical principles, further enhancing the capabilities of quantum computers. To extend quantum computing, novel operations related to relativistic physics are a crucial candidate. Among them, the concept of closed time-like curve has aroused widespread interest, and it introduces the ability for time travel. Mathematically, quantum state along the closed time-like curve is determined through self-consistent equations, which has been demonstrated in simulations. Here, we consider a novel manipulation capability that allows quantum computing to achieve time-travelling quantum control gate. This is an intuitive extension of the graphical language of quantum circuits. Explaining quantum circuits as tensor networks, we first explain how to experimentally simulate the output of such a circuit in a system without time-travel capability. Then, we take an example to demonstrate an extended quantum algorithm that can efficiently solve SAT problems, indicating that with the involvement of time-travelling quantum gates, the computational complexity class P = NP. We also anticipate that the time-travelling quantum gates will play a facilitating role in accomplishing other quantum tasks, including achieving deterministic non-orthogonal quantum state discrimination, and quantum state cloning. Our results contribute to a more in-depth understanding of the relationship between computation and physical principles.
-
Keywords:
- extended Church-Turing thesis /
- time travel /
- closed time-like curves /
- quantum computer /
- P vs. NP problem
[1] Deutsch D 1997 The Fabric of Reality: The Science of Parallel Universes-and Its Implications (Penguin Books) p98
[2] Landauer R 1961 IBM J. Res. Dev. 5 183
Google Scholar
[3] Bernstein E, Vazirani U 1993 Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing San Diego California USA, May 16–18, 1993 p11
[4] Fortnow L 2009 Commun. ACM 52 78
[5] Shor P W 1994 Proceedings 35th Annual Symposium on Foundations of Computer Science Santa Fe NM USA, November 20–22, 1994 p124
[6] Zhong H S, Wang H, Deng Y H, et al. 2020 Science 370 1460
Google Scholar
[7] Wu Y L, Bao W S, Cao S, et al. 2021 Phys. Rev. Lett. 127 180501
Google Scholar
[8] Arute F, Arya K, Babbush R, et al. 2019 Nature 574 505
Google Scholar
[9] Madsen L S, Madsen L S, Laudenbach F, et al. 2022 Nature 606 75
Google Scholar
[10] Nielsen M A, Chuang I L 2010 Quantum Computation and Quantum Information: 10th Anniversary Edition (Cambridge University Press) p40
[11] Cook S A 2023 Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook (Vol. 43) (ACM Books) p143
[12] Gott J R 1991 Phys. Rev. Lett. 66 1126
Google Scholar
[13] Deutsch D 1991 Phys. Rev. D 44 3197
Google Scholar
[14] Lloyd S, Maccone L, Garcia-Patron R, Giovannetti V, Shikano Y, Pirandola S, Rozema L A, Darabi A, Soudagar Y, Shalm L K, Steinberg A M 2011 Phys. Rev. Lett. 106 040403
Google Scholar
[15] Ringbauer M, Broome M A, Myers C R, White A G, Ralph T C 2014 Nat. Commun. 5 4145
Google Scholar
[16] Bacon D 2004 Phys. Rev. A 70 032309
Google Scholar
[17] Chen M C, Li R L, Gan L, Zhu X B, Yang G W, Lu C Y, Pan J W 2020 Phys. Rev. Lett. 124 080502
Google Scholar
[18] Brun T A, Harrington J, Wilde M M 2009 Phys. Rev. Lett. 102 210402
Google Scholar
[19] Vairogs C, Katariya V, Wilde M M 2022 Phys. Rev. A 105 052434
Google Scholar
[20] Brun T A, Wilde M M, Winter A 2013 Phys. Rev. Lett. 111 190401
Google Scholar
[21] Ahn D, Myers C R, Ralph T C, Mann R B 2013 Phys. Rev. A 88 022332
Google Scholar
-
图 1 扩展量子门线路 (a)标准的量子门线路; (b)包含时间旅行的CNOT门的线路
Fig. 1. Extending quantum circuits: (a) Standard quantum circuit; (b) circuit incorporating a time-travelling CNOT gate
图 2 等效的张量网络表示, 借助辅助量子比特(蓝色线)可以非确定性地模拟实现时间旅行CNOT门 (a)示例1, 在时间旅行门的两个拐角, 引入两个分支, 认作一个辅助量子比特(蓝色线), 将其初态制备到$ \left| + \right\rangle $态并同时后选择投影到$ \left\langle + \right| $态, 右图是相应的标准量子门线图表示; (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 $ \left|+\rangle \right. $ state and subsequently projected to the $ \langle \left.+\right| $ 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.
图 3 求解SAT问题 (a)设计的量子算法, 门线路的深度线性正比于SAT问题规模, 即子句的数量$ m $, 最上面$ n $个量子比特作为SAT问题解的寄存器, 中间$ m $个量子比特用于标记$ m $个逻辑子句是否被独立满足, 最后一个量子比特标记位用于判断是否所有的逻辑子句被同时满足; (b)最后标记位上的时间旅行CNOT门的运行细节, 这里$ p $对应张量网络解释中的后选择概率, 当算法中的标记位为$ \left| 1 \right\rangle $时, 相应的辅助量子比特的后选择投影概率为0; 而标记位为$ \left| 0 \right\rangle $时, 后选择投影概率为1, 算法最终只输出标记位为$ \left| 0 \right\rangle $的情况, 这对应上面寄存器里只存储了正确的解
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 $ \left|1\rangle \right. $, the corresponding auxiliary qubits have a posterior-select projection probability of 0; while the marking qubit is $ \left|0\rangle \right. $, the posterior-select projection probability is 1. The algorithm ultimately only outputs the case where the marking qubit is $ \left|0\rangle \right. $, corresponding to storing only the correct solutions in the registers above.
-
[1] Deutsch D 1997 The Fabric of Reality: The Science of Parallel Universes-and Its Implications (Penguin Books) p98
[2] Landauer R 1961 IBM J. Res. Dev. 5 183
Google Scholar
[3] Bernstein E, Vazirani U 1993 Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing San Diego California USA, May 16–18, 1993 p11
[4] Fortnow L 2009 Commun. ACM 52 78
[5] Shor P W 1994 Proceedings 35th Annual Symposium on Foundations of Computer Science Santa Fe NM USA, November 20–22, 1994 p124
[6] Zhong H S, Wang H, Deng Y H, et al. 2020 Science 370 1460
Google Scholar
[7] Wu Y L, Bao W S, Cao S, et al. 2021 Phys. Rev. Lett. 127 180501
Google Scholar
[8] Arute F, Arya K, Babbush R, et al. 2019 Nature 574 505
Google Scholar
[9] Madsen L S, Madsen L S, Laudenbach F, et al. 2022 Nature 606 75
Google Scholar
[10] Nielsen M A, Chuang I L 2010 Quantum Computation and Quantum Information: 10th Anniversary Edition (Cambridge University Press) p40
[11] Cook S A 2023 Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook (Vol. 43) (ACM Books) p143
[12] Gott J R 1991 Phys. Rev. Lett. 66 1126
Google Scholar
[13] Deutsch D 1991 Phys. Rev. D 44 3197
Google Scholar
[14] Lloyd S, Maccone L, Garcia-Patron R, Giovannetti V, Shikano Y, Pirandola S, Rozema L A, Darabi A, Soudagar Y, Shalm L K, Steinberg A M 2011 Phys. Rev. Lett. 106 040403
Google Scholar
[15] Ringbauer M, Broome M A, Myers C R, White A G, Ralph T C 2014 Nat. Commun. 5 4145
Google Scholar
[16] Bacon D 2004 Phys. Rev. A 70 032309
Google Scholar
[17] Chen M C, Li R L, Gan L, Zhu X B, Yang G W, Lu C Y, Pan J W 2020 Phys. Rev. Lett. 124 080502
Google Scholar
[18] Brun T A, Harrington J, Wilde M M 2009 Phys. Rev. Lett. 102 210402
Google Scholar
[19] Vairogs C, Katariya V, Wilde M M 2022 Phys. Rev. A 105 052434
Google Scholar
[20] Brun T A, Wilde M M, Winter A 2013 Phys. Rev. Lett. 111 190401
Google Scholar
[21] Ahn D, Myers C R, Ralph T C, Mann R B 2013 Phys. Rev. A 88 022332
Google Scholar
下载:
计量
- 文章访问数: 2556
- PDF下载量: 135
- 被引次数: 0
