量子算法的一些进展

发布时间：2018-01-18 12:37

本文关键词：量子算法的一些进展　出处：《中国科学:信息科学》2017年10期 　论文类型：期刊论文

【摘要】：量子计算机利用量子力学原理进行计算,具有量子并行计算能力,有比经典计算机更加强大的数据处理能力.量子计算机可以指数加速量子体系模拟,加速一些重要的经典算法.传统的量子计算运算是通过酉算子对信息进行处理,其计算过程是对量子计算机体系的初始量子态进行一系列的酉算子的乘积运算.20世纪90年代中期,量子算法取得重大突破,1994年Shor提出了大数分解量子算法,指数加快了大数分解,1996年Grover提出了量子搜索算法,平方根地加速了无序数据库的搜索.量子算法的重大突破推动量子计算成为国际的持续研究热点领域.之后量子算法的后续发展缓慢,Shor在2003年提出了著名的Shor之问,询问为什么没有发现更多的量子算法.2009年以后,多个重要的新量子算法被发现,如求解线性方程组的量子算法,稀疏Hamiltonian体系的酉算符线性叠加算法,取得计算精度的指数改进的量子系统的新模拟算法.本文首先简单介绍量子算法的基本原理,然后描写Shor算法和Grover/Long搜索算法.这些算法都是传统的量子算法,计算的过程就是一系列酉算子的乘积.接着介绍了2002年提出的对偶量子计算,不同于传统的酉量子算法,对偶量子算法允许酉算子的线性组合.过去的量子计算只能使用酉算子的乘和除,而对偶量子计算可以使用酉算子的加减乘除四则运算.对偶量子计算为构造量子算法提供了方便,可以将经典算法中的技巧直接用于量子算法的构造.我们最近的研究证明2009年以来的几个新量子算法都属于对偶量子计算.本文还介绍开放量子系统的对偶量子模拟算法,该算法不仅降低了计算复杂度,而且指数提高了精度.最后我们给出总结和展望.
[Abstract]:Quantum computer has the ability of quantum parallel computing and has more powerful data processing ability than classical computer. Quantum computer can accelerate quantum system simulation exponentially. Some important classical algorithms are accelerated. The traditional quantum computation is to process the information by unitary operator. The calculation process is a series of product operations of unitary operator for the initial quantum state of quantum computer system. In the middle of 90s, quantum algorithm made a great breakthrough. In 1994, Shor proposed the quantum algorithm of large number decomposition, exponentially accelerated the large number decomposition, and in 1996, Grover proposed a quantum search algorithm. Square root accelerates the search of unordered database. The great breakthrough of quantum algorithm has promoted quantum computing to become a hot research field in the world. After that, the follow-up development of quantum algorithm has been slow. In 2003, Shor put forward the famous question of Shor, asking why no more quantum algorithms were found. After 2009, several important new quantum algorithms were discovered. For example, the quantum algorithm for solving linear equations, the unitary operator linear superposition algorithm for sparse Hamiltonian system. The new simulation algorithm of exponentially improved quantum system is obtained. Firstly, the basic principle of quantum algorithm is introduced briefly in this paper. Then we describe the Shor algorithm and the Grover/Long search algorithm, which are all traditional quantum algorithms. The process of computing is the product of a series of unitary operators. Then the dual quantum computation proposed in 2002 is different from the traditional unitary quantum algorithm. Dual quantum algorithms allow linear combinations of unitary operators. In the past quantum calculations could only use the multiplication and division of unitary operators. Dual quantum computation can use the addition, subtraction, multiplication and division operation of unitary operator, and dual quantum computation provides convenience for constructing quantum algorithm. The techniques in classical algorithms can be directly used in the construction of quantum algorithms. Our recent studies have proved that several new quantum algorithms since 2009 are dual quantum computation. Even quantum simulation algorithm. The algorithm not only reduces the computational complexity, but also improves the accuracy of the index. Finally, we give a summary and prospect.
【作者单位】：清华大学物理系低维量子物理国家重点实验室;量子物质科学协同创新中心;清华信息科学技术国家实验室(筹);
【基金】：国家重点基础研究发展计划(973)(批准号:2011CB9216002) 国家重点研发计划(批准号:2017YFA0303700) 国家自然科学基金(批准号:91221205,11175094)资助项目
【分类号】：TP38
【正文快照】： 1引言量子计算是国际上的热点研究领域,是结合了计算机科学、数学、物理学和工程技术等诸多学科的交叉学科,具有重要的科学意义和战略意义.量子计算利用量子纠缠、量子干涉等独特的量子力学原理进行计算.它的主要的研究目标是打破传统的硅芯片电子计算机不可避免的发展极限,

【相似文献】