Abstract:
量子计算中利用量子平行能力，具有了经典计算没有的计算能力，实现了量子体系的模拟[1]、大数分解[2]和无序数据库搜索[3]的显著加速。但是这些量子算法之后，没有更多的量子算法出现[4]，以至于2003年Shor问了为什么没有更多的量子算法出现这一问题。他把这一问题的原因归结为“量子计算机的运行与经典计算的运行如此不同，以至于经典算法中的构造设计技巧和直觉在量子计算过程中不再成立（Quantum computers operate in a manner so differently from classical computers that our techniques for designing algorithms and our intuitions for understanding the computation process no longer works.）”。2009年以后情况有了一定的改善。2009年，Harrow等人给出了一个线性方程组的高效量子算法，对于一些特殊的线性方程组，可以比经典算法有指数加速[5]。2012年Childs和Wiebe给出了一个哈密顿体系的模拟算法，其模拟精度达到当时的最优[6]。2015年，Berry，Childs，Cleve，Kothari，Somma等澳大利亚、加拿大、美国的联合研究组给出了一个量子模拟算法，其精度达到了指数提高[7]。简单地说，量子计算中只能用到酉算符的乘积（或者相除），而不能用到加和减的操作。2002年提出的对偶量子计算中不仅允许酉算符的乘积，而且允许使用酉算法的线性叠加，这样就可以将经典计算和量子计算联系起来，把一些经典计算中行之有效的方法用于量子算法的构造[8,9,10]。数学家Gudder已经严格证明，对偶量子计算可以构造任意线性有界算符[11]。上面所提到的三个算法都使用了酉算法的线性叠加，是对偶量子计算算法[12].
[1] Feynman R P. Simulating physics with computers. International journal of theoretical physics, 1982, 21(6): 467-488.
[2]Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring. Foundations of Computer Science, 1994 Proceedings., 35th Ann. Symp. IEEE, 1994: 124-134.
[3] Grover L K. A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996: 212-219.
[4] Shor P W. Why haven't more quantum algorithms been found?. J.ACM, 2003, 50: 87-90.
[5]Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. PRL, 103(15): 150502 (2009)
[6]Childs A M, Wiebe N. Hamiltonian simulation using linear combinations of unitary operations. 2012., 12(11-12): 901-924 (2012)
[7] DW Berry, AM Childs, R Cleve, R Kothari, RD Somma. Simulating Hamiltonian dynamics with a truncated Taylor, Phys. Rev. Lett. 114, 090502 (2015)
[8] Long GL, Commun. Theor. Physics, 45, 825( 2006 ). Abstract (5111-53) (Tracking No. FN03-FN02-32， Fluctuations and Noise in Photonics and Quantum Optics“ 18 Oct 2002.
[9] Long GL and Liu Y, Commun. Theor. Phys. (Beijing, China) 50 (2008) 1303
[10] Long, GL. Int. J. Theor. Phys. 50, 1305 (2011). Review article
[11] Stan Gudder, Mathematical Theory of Duality Quantum Computers, Quant Inf Proc, 6:37-48 (2007)
[12] Wei S J, Long G L. Duality quantum computer and the efficient quantum simulations. Quantum Information Processing, 2016, 15(3): 1189-1212.
