Search

Article

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

Quantum computing with time-travelling quantum gates

Wang Can Lu Chao-Yang Chen Ming-Cheng

Citation:

Quantum computing with time-travelling quantum gates

Wang Can, Lu Chao-Yang, Chen Ming-Cheng
PDF
HTML
Get Citation
  • 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.
      Corresponding author: Chen Ming-Cheng, cmc@ustc.edu.cn
    [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 183Google 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 1460Google Scholar

    [7]

    Wu Y L, Bao W S, Cao S, et al. 2021 Phys. Rev. Lett. 127 180501Google Scholar

    [8]

    Arute F, Arya K, Babbush R, et al. 2019 Nature 574 505Google Scholar

    [9]

    Madsen L S, Madsen L S, Laudenbach F, et al. 2022 Nature 606 75Google 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 1126Google Scholar

    [13]

    Deutsch D 1991 Phys. Rev. D 44 3197Google 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 040403Google Scholar

    [15]

    Ringbauer M, Broome M A, Myers C R, White A G, Ralph T C 2014 Nat. Commun. 5 4145Google Scholar

    [16]

    Bacon D 2004 Phys. Rev. A 70 032309Google 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 080502Google Scholar

    [18]

    Brun T A, Harrington J, Wilde M M 2009 Phys. Rev. Lett. 102 210402Google Scholar

    [19]

    Vairogs C, Katariya V, Wilde M M 2022 Phys. Rev. A 105 052434Google Scholar

    [20]

    Brun T A, Wilde M M, Winter A 2013 Phys. Rev. Lett. 111 190401Google Scholar

    [21]

    Ahn D, Myers C R, Ralph T C, Mann R B 2013 Phys. Rev. A 88 022332Google Scholar

  • 图 1  扩展量子门线路 (a)标准的量子门线路; (b)包含时间旅行的CNOT门的线路

    Figure 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展示了其作用在不同物理量子比特上的情形

    Figure 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 $的情况, 这对应上面寄存器里只存储了正确的解

    Figure 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 183Google 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 1460Google Scholar

    [7]

    Wu Y L, Bao W S, Cao S, et al. 2021 Phys. Rev. Lett. 127 180501Google Scholar

    [8]

    Arute F, Arya K, Babbush R, et al. 2019 Nature 574 505Google Scholar

    [9]

    Madsen L S, Madsen L S, Laudenbach F, et al. 2022 Nature 606 75Google 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 1126Google Scholar

    [13]

    Deutsch D 1991 Phys. Rev. D 44 3197Google 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 040403Google Scholar

    [15]

    Ringbauer M, Broome M A, Myers C R, White A G, Ralph T C 2014 Nat. Commun. 5 4145Google Scholar

    [16]

    Bacon D 2004 Phys. Rev. A 70 032309Google 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 080502Google Scholar

    [18]

    Brun T A, Harrington J, Wilde M M 2009 Phys. Rev. Lett. 102 210402Google Scholar

    [19]

    Vairogs C, Katariya V, Wilde M M 2022 Phys. Rev. A 105 052434Google Scholar

    [20]

    Brun T A, Wilde M M, Winter A 2013 Phys. Rev. Lett. 111 190401Google Scholar

    [21]

    Ahn D, Myers C R, Ralph T C, Mann R B 2013 Phys. Rev. A 88 022332Google Scholar

  • [1] Zhou Zong-Quan. “Quantum memory” quantum computers and noiseless phton echoes. Acta Physica Sinica, 2022, 71(7): 070305. doi: 10.7498/aps.71.20212245
    [2] Zhang Yang, Song Xiao-Yan, Xu Wen-Wu, Zhang Zhe-Xu. Thermodynamic study and cellular automaton simulation of thermal stability of nanocrystalline SmCo7 alloy. Acta Physica Sinica, 2012, 61(1): 016102. doi: 10.7498/aps.61.016102
    [3] Xu Feng, Liu Tang-Yan, Huang Yong-Ren. Theoretical computation and numerical simulation of the relaxation of sphere-capillary model saturated with oil and water. Acta Physica Sinica, 2008, 57(1): 550-555. doi: 10.7498/aps.57.550
    [4] Wang Min, Hu Xiao-Fang. Research on diffraction enhanced imaging computed tomography technique. Acta Physica Sinica, 2007, 56(8): 4989-4993. doi: 10.7498/aps.56.4989
    [5] Li Zhi-Jie, Pan Zheng-Ying, Zhu Jing, Wei Qi, Wang Yue-Xia, Zang Liang-Kun, Zhou Liang, Liu Ti-Jiang. Simulations of the structure characteristic of diamond-like carbon films formed by ion-beam-assisted deposition. Acta Physica Sinica, 2005, 54(5): 2233-2238. doi: 10.7498/aps.54.2233
    [6] Zheng Xiao-Ping, Zhang Pei-Feng, Liu Jun, He De-Yan, Ma Jian-Tai. Computer simulation of thin-film epitaxy growth. Acta Physica Sinica, 2004, 53(8): 2687-2693. doi: 10.7498/aps.53.2687
    [7] Xu Feng, Huang Yong-Ren. . Acta Physica Sinica, 2002, 51(11): 2617-2622. doi: 10.7498/aps.51.2617
    [8] Lai Hai-Jiang, Yang Qing-Yi, Wei Lian-Fu. . Acta Physica Sinica, 2002, 51(8): 1730-1735. doi: 10.7498/aps.51.1730
    [9] WANG LIU-DING, CHEN CHANG-LE, LIU LIN, KANG MO-KUANG, JI BANG-JIE, WEI YING-HUI. COMPUTER SIMULATION OF X-RAY DIFFRACTION PROFILES AND TEM DIFFRACTION PATTERNS ON ORDERING FOR Cu-4wt%Ti ALLOY. Acta Physica Sinica, 2000, 49(5): 926-930. doi: 10.7498/aps.49.926
    [10] CHEN BAO-JIU, QIN WEI-PING, WANG HAI-YU, XU WU, HUANG SHI-HUA. COMPUTER SIMULATION OF ENERGY TRANFER PROCESS. Acta Physica Sinica, 1999, 48(3): 545-549. doi: 10.7498/aps.48.545
    [11] WU FENG-MIN, ZHU QI-PENG, WU ZI-QIN. COMPUTER SIMULATION OF THE EPITAXY GROWTH IN ULTRA-THIN FILMS. Acta Physica Sinica, 1998, 47(9): 1427-1435. doi: 10.7498/aps.47.1427
    [12] LV XIAO-YANG, LIU MU-REN, KONG LING-JING. THEORETICAL ANALYSIS AND COMPUTER EXPERIMENTS FOR 1D RANDOM TRAFFIC FLOW MODELS. Acta Physica Sinica, 1998, 47(11): 1761-1768. doi: 10.7498/aps.47.1761
    [13] ZENG JIAN-LIN, BA LONG, HOU JIAN-GUO, WU ZI-QIN. COMPUTER SIMULATION OF AGGREGATION-FRACTALS IN THIN FILMS. Acta Physica Sinica, 1997, 46(1): 28-34. doi: 10.7498/aps.46.28
    [14] ZHANG DENG-YU. SPONTANEOUS EMISSION AND DECOHERENCE IN QUANTUM COMPUTER MEMORY CELL. Acta Physica Sinica, 1997, 46(4): 656-660. doi: 10.7498/aps.46.656
    [15] LIN HONG-YI, WU XU-HUI, HE YU-LIANG, CHU YI-MING. GROWTH DYNAMICS OF NANO-CRYSTALLINE SILICON (nc-Si:H)FILMS AND ITS COMPUTER SIMULATION. Acta Physica Sinica, 1996, 45(4): 655-660. doi: 10.7498/aps.45.655
    [16] XU XIU-YING, ZHANG XING-KUI, FENG DUAN, Lü PENG. BIREFRINGENCE IMAGE OF A LARGE HEXAGONAL LAMELLAR INCLUSION AND COMPUTER SIMULATION. Acta Physica Sinica, 1990, 39(3): 491-494. doi: 10.7498/aps.39.491
    [17] SHI SHUANG-HE, CHEN JIN-CHANG, WANG XIU-WEI. A COMPUTER SIMULATION OF THE STRUCTURE OF AMORPHOUS ALLOY Fe-P(I)——THE SHORT RANGE ORDER OF THE STRUCTURE OF Fe75P25 ALLOY. Acta Physica Sinica, 1988, 37(11): 1849-1854. doi: 10.7498/aps.37.1849
    [18] WANG XU-WEI, CHEN JIN-CHANG, SHI SHUANG-HE. A COMPUTER SIMULATION OF THE STRUCTURE OF AMORPHOUS ALLOY Fe-P(II)——THE DEPENDENT RELATION OF THE STRUCTURE OF Fe100-xPx ON THE CONCENTRATION. Acta Physica Sinica, 1988, 37(11): 1775-1784. doi: 10.7498/aps.37.1775
    [19] SUN ZONG-QI. COMPUTER SIMULATIONS OF THE ANOMALOUS INTERNAL FRICTION ASSOCIATED WITH THE INTERACTION BETWEEN OSCILLATING KINKS AND MOBILE POINT DEFECTS. Acta Physica Sinica, 1982, 31(5): 561-570. doi: 10.7498/aps.31.561
    [20] HAN FU-SEN, FAN HAI-FU. COMPUTER ANALYSIS OF PATTERSON MAP. Acta Physica Sinica, 1981, 30(2): 224-233. doi: 10.7498/aps.30.224
Metrics
  • Abstract views:  2558
  • PDF Downloads:  135
  • Cited By: 0
Publishing process
  • Received Date:  08 August 2023
  • Accepted Date:  31 October 2023
  • Available Online:  17 November 2023
  • Published Online:  20 January 2024

/

返回文章
返回