分布式量子计数算法研究

发布时间：2018-04-03 06:18

本文选题：分布式量子计算　切入点：量子计数算法　出处：《东北大学》2012年硕士论文

【摘要】：随着量子计算和量子信息技术的发展,分布式量子计算应运而生。通过量子网络将量子计算机连接起来能获得更强的计算能力。分布式量子计算具有逻辑门级并行能力,与传统的并行计算相比,这是更底层的并行。所有的P问题都属于NP问题,而所有NP问题又可多项式规约到NP完全问题,因此如果能设计出一个复杂度更低的求解NP完全问题的算法,那么所有NP问题都可以在原有算法基础上的获得同样的加速。计数问题是一类受到广泛关注的NP完全问题,本文提出一个解决计数问题的分布式量子算法,将这个算法作为通用的计算模式,在解决其他NP问题(当然也包括P问题)时,只需设计相应的黑箱,研究适当的地址映射方案,就能在原有的算法上获得将近。O的加速。本文首先总结分布式量子计算的发展现状,包括物理环境和应用,然后给出NP问题和计数问题的精确定义,NP完全问题的证书以及相应的计数问题描述。接下来介绍基本量子门,包括单比特量子门、多比特量子门、基本量子门的通用性。然后详细描述量子门的非本地化方法,这是分布式量子计算的关键。再设计一些典型问题的量子线路。然后,详细描述分布式量子计数算法的理论推导和设计与实现。先从理论上推导量子计数算法的原理,再设计算法的总体结构,接着详细描述了算法各个部分的设计与实现,包括Grover迭代、化简多量子比特门和量子逆傅立叶变换,最后给出量子计数算法求解集合覆盖问题的实例。文章最后分析分布式量子算法的复杂度,包括量子门复杂度、查询复杂度和通信复杂度,还讨论了量子比特利用率。
[Abstract]:With the development of quantum computing and quantum information technology, distributed quantum computing emerges as the times require.A quantum computer can be connected to a quantum network to achieve greater computing power.Distributed quantum computing has the parallel capability of logic gate, which is lower level than traditional parallel computing.All P problems belong to NP problems, and all NP problems can be reduced to NP complete problems by polynomials. Therefore, if we can design a lower complexity algorithm for solving NP complete problems,Then all NP problems can be obtained the same acceleration on the basis of the original algorithm.The enumeration problem is a kind of NP-complete problem, which is widely concerned. In this paper, a distributed quantum algorithm is proposed to solve the counting problem, which is regarded as a general computing model, and is used to solve other NP problems (including P problem, of course).By designing the corresponding black box and studying the appropriate address mapping scheme, we can obtain the acceleration of nearly. O on the original algorithm.This paper first summarizes the development of distributed quantum computing, including the physical environment and applications, then gives the exact definition of NP problem and enumeration problem and the certificate of NP-complete problem and the corresponding description of counting problem.Then we introduce the generality of basic quantum gates, including single-bit quantum gates, multi-bit quantum gates, and basic quantum gates.Then the non-localization method of quantum gate is described in detail, which is the key of distributed quantum computing.Then we design some typical quantum circuits.Then, the theoretical derivation, design and implementation of the distributed quantum counting algorithm are described in detail.The principle of quantum counting algorithm is deduced theoretically, then the overall structure of the algorithm is designed. Then, the design and implementation of each part of the algorithm are described in detail, including Grover iteration, simplification of multi-quantum bit gates and quantum inverse Fourier transform.Finally, an example of quantum counting algorithm for solving set covering problem is given.Finally, the complexity of distributed quantum algorithms, including quantum gate complexity, query complexity and communication complexity, is analyzed. Quantum bit utilization is also discussed.
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP38;O413

【参考文献】