计算机科学 ›› 2020, Vol. 47 ›› Issue (1): 40-50.doi: 10.11896/jsjkx.190400432

• 计算机科学理论 • 上一篇    下一篇

量子计算与不确定性原理

Renata WONG   

  1. (南京大学计算机科学与技术系 南京210093)1;
    (南京大学软件新技术国家重点实验室 南京210093)2
  • 收稿日期:2019-04-10 发布日期:2020-01-19
  • 通讯作者: Renata Wong(renata.wong@protonmail.com)
  • 基金资助:
    国家重点研发计划(2019YFA0308700);江苏省自然科学基金(BK20191249)

Uncertainty Principle as Related to Quantum Computation

Renata WONG   

  1. (Department of Computer Science and Technology,Nanjing University,Nanjing 210093,China)1;
    (State Key Laboratory for Novel Software Technology at Nanjing University,Nanjing 210093,China)2
  • Received:2019-04-10 Published:2020-01-19
  • About author:Renata WONG,doctoral student.Her main research interests include quantum computing,protein structure prediction,physics and linguistics.
  • Supported by:
    This work was supported by the National Key R&D Program of China (2019YFA0308700) and Natural Science Foundation of Jiangsu Province (BK20191249).

摘要: 对量子计算的计算潜力的高度期望源于量子力学的各种特性,如叠加原理、纠缠现象、破坏性和建设性的量子干扰。相对于经典计算,量子计算具有某些假定的优势,例如量子算法的运行速度比经典算法快;但另一方面却似乎存在影响经典算法但不影响量子算法的障碍,障碍之一是传统上归因于Werner Heisenberg的两个不确定性原理。Heisenberg最初制定的不确定性原理涉及用于测量量子系统的非量子仪器必然会对该系统造成影响。 这个原理与其后来的发展有所不同,因为后来发现的不确定性所假定的是不交换可观察量在测量方面存在固有的不能精确测量的特性。在目前的技术发展状况以及当前对量子力学的形式表述与诠释的情况下,这两种不确定性皆有可能对量子计算的速度造成不良影响。近年来,针对这两种不确定性原理有了新的研究成果:1)Ozawa对Heisenberg原理提出了修改,将两种不确定性纳入其内进行并列考虑,从而可以减小Heisenberg原理的不确定性程度;2)在考虑到熵不确定性的情况下,Heisenberg不确定性可被视为Hirschmann不确定性的下界,因此除了在测量上的不确定性之外,量子计算还必须考虑来自其他如信息学的不确定性因素。

关键词: 量子计算, 不确定性原理, 不确定性关系, 熵不确定性

Abstract: The high expectations regarding the computational potential of quantum computation stem from quantum mechanical features,such as the principle of superposition,the phenomenon of entanglement,the destructive and constructive interference.Besides the presumed advantages of quantum computation over classical computation,there exist impediments that appear to be affecting the former but not the latter.One of them are the two uncertainty principles traditionally ascribed to Werner Heisenberg.The uncertainty principle formulated originally by Heisenberg pertains to the inability of measuring a quantum system with non-quantum instruments without affecting it.This principle is different from the later development postulating an inherent inability of non-commuting observables to be measured precisely.At present state of technological development and within the current formulation and interpretation of quantum mechanics,both versions of the uncertainty affect the speed attainable by a quantum computer.Recently,the two uncertainty principles have received more attention.In his improvement to Heisenberg’s principle,Ozawa took into account both types of uncertainty mentioned above.Furthermore,research into entropic uncertainty has shown that Heisenberg’s uncertainty can be seen as a lower bound of Hirschmann’s uncertainty,thereby indicating that quantum computation may need to consider other types of uncertainties,such as information uncertainty,as well.

Key words: Quantum computing, Uncertainty principle, Uncertainty relations, Entropic uncertainty

中图分类号: 

  • TP3-0
[1]MANIN Y.Вычислимое и невычислимое [S].Советское Радио,1980.
[2]FEYNMAN R.Simulating physics with computers [J].International Journal of Theoretical Physics,1982,21(6/7):467-488.
[3]BENIOFF P A.Quantum mechanical Hamiltonian models of Turing machines [J].Journal of Statistical Physics,1982,29(3):515-546.
[4]DEUTSCH D.Quantum theory,the Church-Turing principle, and the universal quantum Turing machine [J].Proceedings of the Royal Society of London,1985,404(1818):97-117.
[5]SIMON D.On the power of quantum computation [C]∥Foundations of Computer Science.IEEE,1994:116-123.
[6]DEUTSCH D,JOZSA R.Rapid solution of problems by quantum computation [J].Proceedings of the Royal Society of London,1992,439(1907):553-558.
[7]BERNSTEIN E,VAZIRANI U.Quantum complexity theory
[C]∥Proc.25th Annual ACM Symposium on Theory of Computing.ACM,1993:11-20.
[8]SHOR P.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J].SIAM Journal on Scientific and Statistical Computing,1994,26:1484-1509.
[9]BERNSTEIN D,HENINGER N,LOU P,et al.Post-quantum RSA:Report 217/351[R].Cryptology ePrint Archive,2017.
[10]MOORE G.Cramming more components onto integrated circuits [J].Electronics,1965,38(8):114-117.
[11]GREENLAW R,HOOVER H,RUZZO W.Limits to parallel computation:P-completeness theory [M].Oxford University Press,1995.
[12]LADNER R.The circuit value problem is log space complete for P [J].SIGACT News,1975,7(1):18-20.
[13]EINSTEIN A.Über einen die Erzeugung und Verwandlung des Lichtes betreffenden heuristischen Gesichtspunkt [J].Annalen der Physik,1905,17:132-148.
[14]VON NEUMANN J.Mathematische Grundlagen der Quantenmechanik [M].Springer,1932.
[15]RANGAN C,BLOCH A M,MONROE C,et al.Control of trapped-ion quantum states with optical pulses [J].Physical Review Letters,2004,92(11):113004.
[16]HUANG G M,TARN T J,CLARK J W.On the controllability of quantum-mechanical systems [J].Journal of Mathematical Physics,1983,24(11):2608- 2618.
[17]LAU H K,POOSER R,SIOPSIS G,et al.Quantum Machine Learning over Infinite Dimensions [J].arXiv:1603.06222.Physical Review Letters,2017(118):080501.
[18]BORN M.Zur Quantenmechanik der Stoβvorgänge [J]. Zeitschrift für Physik,1926,37:863-867.
[19]HEISENBERG W.Über den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik [J].Zeitschrift für Physik,1927,43(3):172-198.
[20]ROBERTSON H.The uncertainty principle [J].Physical Re- view,1929,34:163-164.
[21]BACH R,POPE D,LIOU S H,et al.Controlled double-slit electron diffraction [J].New Journal of Physics,2013,15:033018.
[22]SCHRÖDINGER E.An undulatory theory of the mechanics of atoms and molecules [J].Physical Review,1926,28(6):1049-1070.
[23]PAULI W.Die allgemeinen Prinzipien der Wellenmechanik
[M]∥Handbuch der Physik (24).Springer,1933.
[24]GARRISON J,WONG J.Canonically conjugate pairs,uncertainty relations,and phase operators [J].Journal of Mathematical Physics,1970,11(8):2242-2249.
[25]POISSON J.Poisson bracket [J].Journal de l’École Polytechnique,1809,8:266.
[26]MANDELSTAM L,TAMM I.The uncertainty relation between energy and time in nonrelativistic quantum mechanics [J].Journal of Physics (USSR),1945,9(4):249-254.
[27]AHARONOV Y,BOHM D.Time in the Quantum Theory and the Uncertainty Relation for Time and Energy [J].Physical Review,1961,122(5):1649-1658.
[28]BRIGGS J S.A derivation of the time-energy uncertainty relation [J].Journal of Physics Conference Series,2008,99:012002.
[29]KLEIN U.What is the limit of quantum theory? [J].American Journal of Physics,2012,80(11):1009.
[30]SEN D,SENGUPTA S.A critique of the classical limit problem of quantum mechanics [J].Foundations of Physics Letters,2006,19:403-412.
[31]SREDNICKI M.Quantum Field Theory [M].Cambridge University Press,2007.
[32]BUNGE M.The turn of the tide [M]∥Quantum theory and reality.Springer,1967.
[33]HEISENBERG W.Die physikalischen Prinzipien der Quantentheorie [M].S.Hirzel,1930.
[34]UFFINK J.The rate of evolution of a quantum state[J].Ameri- can Journal of Physics,1993,61:935.
[35]MARGOLUS N,LEVITIN L B.The maximum speed of dynami- cal evolution [J].Physica D,1998,120:188.
[36]DEFFNER S,CAMPBELL S.Quantum speed limits:from Heisenberg’s uncertainty principle to optimal quantum control [J].Journal of Physics A,2017,50(45):453001.
[37]LEVITIN L B,TOFFOLI Y.Fundamental limit on the rate of quantum dynamics:The unified bound is tight [J].Physical Review Letters,2009,103:160502.
[38]LLOYD S.Ultimate physical limits to computation [J].Nature,2000,406:1047-1054.
[39]COLES R,KANIEWSKI J,WEHNER S.Equivalence of wave-particle duality to entropic uncertainty [J].Nature Communications,2014,5:5814ôarXiv:1403.4687.
[40]COLES R,BERTA M,TOMAMICHEL M,et al.Entropic uncertainty relations and their applications [J].Reviews of Mo-dern Physics,2017,89(1):015002-1.
[41]DüRR S,REMPE G.Can wave-particle duality be based on the uncertainty relation? [J].American Journal of Physics,2000,68:1021-1024.
[42]BUSCH P,SHILLADAY C.Complementarity and uncertainty in Mach-Zehnder interferometry and beyond [J].Physics Reports,2006,435:1-31.
[43]YOUNG T.Bakerian Lecture:Experiments and calculations rela- tive to physical optics [J].Philosophical Transactions of the Royal Society,1804,94:1-16.
[44]ROZEMA L A,DARABI A,MAHLER D H,et al.Violation of Heisenberg’s measurement-disturbance relationship by weak measurements [J].Physical Review Letters,2012,109:100404.
[45]MARGENAU H.Measurements in quantum mechanics [J]. Annals of Physics,1963,23(3):469-485.
[46]POPPER K.Quantum mechanics without “the observer” [M]∥Quantum theory and reality.Springer,1967.
[47]BALLENTINE L E.The statistical interpretation of quantum mechanics [J].Review of Modern Physics,1970,42(4):358-381.
[48]OZAWA M.Uncertainty relations for noise and disturbance in generalized quantum measurements [J].Annals of Physics,2003,311(2):350-416.
[49]OZAWA M.Uncertainty relations for joint measurements of noncommuting observables [J].Physics Letters A,2004,320:367-374.
[50]BAEK S-Y,KANEDA F,OZAWA M,et al.Experimental violation and reformulation of the Heisenberg’s error-disturbance uncertainty relation [R].Scientific Reports 3,2013.
[51]HIRSCHMAN I I.A note on entropy [J].American Journal of Mathematics,1957,79(1):152-156.
[52]COLES P J,BERTA M,TOMAMICHEL M,et al.Entropic uncertainty relations and their applications [J].Review of Modern Physics,2017,89(1):015002.
[53]MAASSEN H,UFFINK J B M.Generalized entropic uncertainty relations [J].Physical review Letters,1988,60(12):1103-1106.
[54]DEUTSCH D.Uncertainty in quantum measurements [J]. Physical Review Letters,1982,50(9):631-633.
[55]BIAłYNICKI-BIRULA I,MYCIELSKI J.Uncertainty relations for information entropy in wave mechanics [J].Communications in Mathematical Physics,1975,44(2):129-132.
[1] 罗文俊, 雷爽. 噪声信道下的盲量子计算[J]. 计算机科学, 2020, 47(7): 37-41.
[2] 周恒, 王拥军, 王宝山, 燕健. 直觉主义视角下量子逻辑的进一步解释[J]. 计算机科学, 2020, 47(5): 1-6.
[3] 戴文静, 袁家斌. 隐含子群问题的研究现状[J]. 计算机科学, 2018, 45(6): 1-8.
[4] 张亮亮,张翌维,梁洁,孙瑞一,王新安. 新量子技术时代下的信息安全[J]. 计算机科学, 2017, 44(7): 1-7.
[5] 徐永振,郭躬德,蔡彬彬,林崧. 基于一维三态量子游走的量子聚类算法[J]. 计算机科学, 2016, 43(3): 80-83.
[6] 樊富有,杨国武,张 艳,杨 钢. 三值量子基本门及其对量子Fourier变换的电路实现[J]. 计算机科学, 2015, 42(7): 57-61.
[7] 王冬,刘强,李善治. 基于矩阵初等变换的量子可逆逻辑电路双向综合算法[J]. 计算机科学, 2014, 41(9): 18-23.
[8] 樊富有,杨国武,李晓瑜,罗庆斌. 混合多值可逆逻辑中广义Toffoli门仅用CNOT门的实现[J]. 计算机科学, 2014, 41(8): 115-117.
[9] 王冬,刘志昊,朱皖宁,李善治. 基于多目标扩展通用Toffoli门的量子比较器设计[J]. 计算机科学, 2012, 39(9): 302-306.
[10] 董青 吴楠. 整数质因子分解算法新进展与传统密码学面临的挑战[J]. 计算机科学, 2008, 35(8): 17-20.
[11] 缑水平 焦李成 田小林. 基于量子进化规划核聚类算法的图像分割[J]. 计算机科学, 2008, 35(7): 213-215.
[12] 钱辰. 量子纠缠和量子计算[J]. 计算机科学, 2006, 33(12): 230-234.
[13] 张云洁. 量子测量与量子计算[J]. 计算机科学, 2006, 33(10): 216-220.
[14] 苏运霖. 量子计算机的回顾与展望[J]. 计算机科学, 2002, 29(1): 17-20.
[15] 匡春光. 浅释量子计算的计算能力[J]. 计算机科学, 2001, 28(9): 128-129.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .