SCIENTIA SINICA Informationis, Volume 47, Issue 10: 1277-1299(2017) https://doi.org/10.1360/N112017-00178

Quantum Computing

More info
  • ReceivedSep 11, 2017
  • AcceptedSep 18, 2017
  • PublishedOct 16, 2017


Quantum computing exploits quantum mechanical properties to perform computations. It enables quantum parallelism and provides much more powerful data processing capabilities than classical computers. With a quantum computer, one can exponentially accelerate quantum system simulation and accelerate some important classical algorithms. Traditional quantum algorithms use unitary evolution to process information. A quantum computing process is the product of a series of unitary operators. In 1994, Shor invented a quantum prime factorization algorithm that exponentially accelerates the factorization of an integer. In 1996, Grover proposed a quantum search algorithm that accelerates the search of an unsorted database using square-root steps. Afterwards, the development of quantum algorithms slowed down, leading to a subsequent query by Shor in 2003 regarding why no more significant quantum algorithms have been found. Since 2009, many important new quantum algorithms have been proposed, such as a quantum algorithm for solving linear equations with the capability of exponential acceleration, a quantum algorithm for sparse Hamiltonian simulation using linear combinations of unitary operators, and a novel algorithm for Hamiltonian simulation, which provides exponential improvements in precision. In this paper, we first describe the basic principles of quantum computation. We then describe the Shor algorithm and Grover/Long search algorithm. These quantum algorithms are the general quantum algorithms that use unitary operations in their computational processes. Next, we introduce the basic principles of duality quantum computing, which was proposed in 2002. In contrast to traditional quantum computing, duality quantum computing allows the use of linear combinations of unitary operators in the computation process, meaning the multiplication, division, addition, and subtraction of unitary operators are all possible in duality quantum computing. Thus, duality quantum computing provides more flexibility for constructing quantum algorithms and the techniques used in classical algorithm design can be directly used to construct quantum algorithms. We then review recent work regarding newer quantum algorithms that enable the linear combination of unitary operators, which are actually duality quantum algorithms. Additionally, a duality quantum simulation algorithm for open quantum systems is introduced. This algorithm not only reduces computational complexity, but also improves accuracy exponentially. Finally, a summary and the future prospects of quantum algorithms are provided.

Funded by





[1] Benioff P. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. J Stat Phys, 1980, 22: 563-591 CrossRef ADS Google Scholar

[2] Manin Y I. Vychislimoe i nevychislimoe (Computable and noncomputable) (in Russian). Sov Radio, 1980, 13--15. Google Scholar

[3] Feynman R P. Simulating Physics with Computers. Int J Theor Phys, 1982, 21: 467-488 CrossRef ADS Google Scholar

[4] Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc R Soc A-Math Phys Eng Sci, 1985, 400: 97-117 CrossRef ADS Google Scholar

[5] Shor P W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J Comput, 1997, 26: 1484-1509 CrossRef Google Scholar

[6] Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, 1996. 212--219. Google Scholar

[7] Wang S H, Long G L. Big data and quantum computation. Chin Sci Bull (Chin Ver), 2015, 60: 499-508 CrossRef Google Scholar

[8] Shor P W. Why haven't more quantum algorithms been found? J ACM, 2003, 50: 87--90. Google Scholar

[9] Gui-Lu L. General Quantum Interference Principle and Duality Computer. Commun Theor Phys, 2006, 45: 825-844 CrossRef ADS Google Scholar

[10] Gui-Lu L, Yang L. Duality Computing in Quantum Computers. Commun Theor Phys, 2008, 50: 1303-1306 CrossRef ADS arXiv Google Scholar

[11] Gui-Lu L, Yang L, Chuan W. Allowable Generalized Quantum Gates. Commun Theor Phys, 2009, 51: 65-67 CrossRef ADS Google Scholar

[12] Gudder S. Mathematical Theory of Duality Quantum Computers. Quantum Inf Process, 2007, 6: 37-48 CrossRef Google Scholar

[13] Long G L. Mathematical Theory of the Duality Computer in the Density Matrix Formalism. Quantum Inf Process, 2007, 6: 49-54 CrossRef ADS Google Scholar

[14] Long G L. Duality Quantum Computing and Duality Quantum Information Processing. Int J Theor Phys, 2011, 50: 1305-1318 CrossRef ADS Google Scholar

[15] Gudder S. Duality Quantum Computers and Quantum Operations. Int J Theor Phys, 2008, 47: 268-279 CrossRef ADS Google Scholar

[16] Wang Y Q, Du H K, Dou Y N. Note on Generalized Quantum Gates and Quantum Operations. Int J Theor Phys, 2008, 47: 2268-2278 CrossRef ADS Google Scholar

[17] Du H K, Wang Y Q, Xu J L. Applications of the generalized Lüders theorem. J Math Phys, 2008, 49: 013507 CrossRef ADS Google Scholar

[18] Cao H X, Li L, Chen Z L. Restricted allowable generalized quantum gates. Chin Sci Bull, 2010, 55: 2122-2125 CrossRef Google Scholar

[19] Zhang Y, Cao H X, Li L. Realization of allowable qeneralized quantum gates. Sci China Phys Mech Astron 2010, 53: 1878--1883. Google Scholar

[20] Chen L, Cao H X, Meng H X. Generalized duality quantum computers acting on mixed states. Quantum Inf Process, 2015, 14: 4351-4360 CrossRef ADS Google Scholar

[21] Cao H X, Chen Z L, Guo Z H. Complex duality quantum computers acting on pure and mixed states. Sci China-Phys Mech Astron, 2012, 55: 2452-2462 CrossRef ADS Google Scholar

[22] Liu J, Cheng J, Huang X L. Quantum Coherence and Bose-Einstein Correlations for Time-Dependent Source. Int J Theor Phys, 2013, 52: 1-8 CrossRef ADS Google Scholar

[23] Cui J, Zhou T, Long G L. Density matrix formalism of duality quantum computer and the solution of zero-wave-function paradox. Quantum Inf Process, 2012, 11: 317-323 CrossRef Google Scholar

[24] Long G, Liu Y. Duality quantum computing. Front Comput Sci China, 2008, 2: 167-178 CrossRef Google Scholar

[25] Long G L, Liu Y. General principle of quantum interference and the duality quantum computer. Rep Prog Phys, 2008, 28: 410--431. Google Scholar

[26] Zou X, Qiu D, Wu L. On mathematical theory of the duality computers. Quantum Inf Process, 2009, 8: 37-50 CrossRef Google Scholar

[27] Qiang X, Zhou X, Aungskunsiri K, et al. Quantum processing by remote quantum control. Quantum Sci Technol, 2017, 045002. Google Scholar

[28] Harrow A W, Hassidim A, Lloyd S. Quantum Algorithm for Linear Systems of Equations. Phys Rev Lett, 2009, 103: 150502 CrossRef PubMed ADS arXiv Google Scholar

[29] Wei S J, Zou Z R, Ruan D, et al. Realization of the algorithm for system of linear equations in duality quantum computing. In: Proceeding IEEE 85th Vehicular Technology Conference, Sydney, 2017. Google Scholar

[30] Childs A M, Wiebe N. Hamiltonian simulation using linear combinations of unitary operations. Quantum Inform Comput, 2012, 12: 901-924. Google Scholar

[31] Berry D W, Childs A M, Cleve R. Simulating Hamiltonian Dynamics with a Truncated Taylor Series. Phys Rev Lett, 2015, 114: 090502 CrossRef PubMed ADS arXiv Google Scholar

[32] Wei S J, Long G L. Duality quantum computer and the efficient quantum simulations. Quantum Inf Process, 2016, 15: 1189-1212 CrossRef ADS arXiv Google Scholar

[33] Wei S J, Ruan D, Long G L. Duality quantum algorithm efficiently simulates open quantum systems. Sci Rep, 2016, 6: 30727 CrossRef PubMed ADS Google Scholar

[34] Barenco A, Bennett C H, Cleve R. Elementary gates for quantum computation. Phys Rev A, 1995, 52: 3457-3467 CrossRef ADS Google Scholar

[35] Liu Y, Long G L, Sun Y. ANALYTIC ONE-BIT AND CNOT GATE CONSTRUCTIONS OF GENERAL n-QUBIT CONTROLLED GATES. Int J Quantum Inform, 2008, 06: 447-462 CrossRef Google Scholar

[36] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2010. Google Scholar

[37] Lloyd S. Universal quantum simulators. Science, 1996: 1073--1077. Google Scholar

[38] Hunziker M, Meyer D A. Quantum algorithms for highly structured search problems. Quantum Inf Processing, 2002, 1: 145-154 CrossRef Google Scholar

[39] Grover L K. Quantum Computers Can Search Rapidly by Using Almost Any Transformation. Phys Rev Lett, 1998, 80: 4329-4332 CrossRef ADS Google Scholar

[40] GuiLu L, WeiLin Z, YanSong L. Arbitrary Phase Rotation of the Marked State Cannot Be Used for Grover's Quantum Search Algorithm. Commun Theor Phys, 1999, 32: 335-338 CrossRef Google Scholar

[41] Long G L, Li Y S, Zhang W L. Phase matching in quantum searching. Phys Lett A, 1999, 262: 27-34 CrossRef ADS Google Scholar

[42] Long G L, Li X, Sun Y. Phase matching condition for quantum search with a generalized initial state. Phys Lett A, 2002, 294: 143-152 CrossRef ADS Google Scholar

[43] Long G L. Grover algorithm with zero theoretical failure rate. Phys Rev A, 2001, 64: 022307 CrossRef ADS Google Scholar

[44] Long G, Liu Y. Search an unsorted database with quantum mechanics. Front Comput Sc China, 2007, 1: 247-271 CrossRef Google Scholar

[45] Hoyer P. Arbitrary phases in quantum amplitude amplification. Phys Rev A, 2000, 62: 052304 CrossRef ADS Google Scholar

[46] Biham E, Biham O, Biron D. Analysis of generalized Grover quantum search algorithms using recursion equations. Phys Rev A, 2000, 63: 012310 CrossRef ADS Google Scholar

[47] Diao Z. Exactness of the original Grover search algorithm. Phys Rev A, 2010, 82: 044301 CrossRef ADS arXiv Google Scholar

[48] Toyama F M, van Dijk W, Nogami Y. Quantum search with certainty based on modified Grover algorithms: optimum choice of parameters. Quantum Inf Process, 2013: 1--18. Google Scholar

[49] Castagnoli G. Highlighting the Mechanism of the Quantum Speedup by Time-Symmetric and Relational Quantum Mechanics. Found Phys, 2016, 46: 360-381 CrossRef ADS Google Scholar

[50] Benioff P. Space searches with a quantum robot. AMS Contemporary Math Series, 2002, 305: 1--13. Google Scholar

[51] Bhattacharya N, van Linden van den Heuvell H B, Spreeuw R J C. Implementation of Quantum Search Algorithm using Classical Fourier Optics. Phys Rev Lett, 2002, 88: 137901 CrossRef PubMed ADS Google Scholar

[52] Puentes G, Mela C L, Ledesma S. Optical simulation of quantum algorithms using programmable liquid-crystal displays. Phys Rev A, 2004, 69: 042319 CrossRef ADS Google Scholar

[53] Ivanov S S, Ivanov P A, Vitanov N V. Simple implementation of a quantum search with trapped ions. Phys Rev A, 2008, 78: 030301 CrossRef ADS arXiv Google Scholar

[54] Botsinis P, Soon Xin Ng P, Hanzo L. Quantum Search Algorithms, Quantum Wireless, and a Low-Complexity Maximum Likelihood Iterative Quantum Multi-User Detector Design. IEEE Access, 2013, 1: 94-122 CrossRef Google Scholar

[55] Yoder T J, Low G H, Chuang I L. Fixed-Point Quantum Search with an Optimal Number of Queries. Phys Rev Lett, 2014, 113: 210501 CrossRef PubMed ADS arXiv Google Scholar

[56] Grover L K, Radhakrishnan J. Is partial quantum search of a database any easier? In: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures. New York: ACM, 2005. 186--194. Google Scholar

[57] Imre S, Balazs F. Quantum Computing and Communications: an engineering approach. Hoboken: John Wiley & Sons, 2013. Google Scholar

[58] Dong D, Petersen I R. Sliding mode control of quantum systems. New J Phys, 2009, 11: 105033 CrossRef ADS arXiv Google Scholar

[59] Trugenberger C A. Quantum pattern recognition. Quantum Inf Processing, 2002, 1: 471-493 CrossRef Google Scholar

[60] Chao-Yang P, Zheng-Wei Z, Guang-Can G. A hybrid quantum encoding algorithm of vector quantization for image compression. Chin Phys, 2006, 15: 3039-3043 CrossRef ADS Google Scholar

[61] Marshman R J, Lund A P, Rohde P P, et al. Passive quantum error correction of linear optics networks through error averaging,. arXiv Google Scholar

[62] Suzuki M. General theory of fractal path integrals with applications to many-body theories and statistical physics. J Math Phys, 1991, 32: 400-407 CrossRef ADS Google Scholar

[63] Blanes S, Casas F, Ros J. Extrapolation of Symplectic Integrators. Celestial Mech Dynamical Astron, 1999, 75: 149-161 CrossRef ADS Google Scholar

  • Figure 1

    Geometrical illustration of Grover algorithm, modified from [36]

  • Figure 2

    (Color online) An illustration for a three-slits duality quantum computer. The input is entered from the second slits marked as 1, andthe input is divided into three sub waves by three slits of the middle screen. After the middle screen, the sub waves are performed individual operations in different slits.The output of the duality quantum computation is obtained from three slits on the right screen, and the outputs at different slits correspond to different quantum calculating results

  • Figure 3

    (Color online) The multi-output duality quantum computing circuit. $|\Psi\rangle$ denotes the initial state of work qubit, and $|0\rangle$ is the initial state of the controlling auxiliary qudit

  • Figure 4

    (Color online) Quantum circuit for the BCCKS algorithm in duality quantum computing. Part A is the quantum circuit of duality computing. $|\Psi\rangle$ is the initial state of duality quantum computer and there are $ K $ auxiliary controlling qubits $|0\rangle$ and $ K $ auxiliary controlling qudits $ |0\rangle_{L}$with $ L$ energy level system . Part B is to illustrate that each unitary operation $U_{0}$ is composed of $ H_{1}, H_{2}, \ldots, H_{L-1}, H_{L}$. The unitary operations $U_{0}$ are activated only when the $ L$ level $ |0\rangle_{L}$ auxiliary controlling qudits hold the values indicated in respective circles

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有