【作者】 王娟；

【导师】 曲日；

【作者基本信息】 天津大学 ， 计算机科学与技术， 2014， 硕士

【摘要】 量子计算与量子信息的研究对象是用量子力学系统能够完成的信息处理任务。1985年Deutsch提出了通用量子计算机概念，并指出，量子计算机可以有效解决经典计算机，甚至是概率图灵机不能有效解决的计算问题。量子计算机进一步发展的研究表现在Grover搜索算法上，表明在没有结构的搜索空间上进行的搜索问题在量子计算机上可以被二次加速，由于搜索算法的广泛适用性，引起了人们对Grover算法的极大关注。Ramsey理论是组合数学的一个重要分支，而图的Ramsey数是Ramsey理论的一个重要研究方向。然而，确定Ramsey数是NP问题，到目前为止，只有很少的Ramsey数的精确值被确定，已知的上下界大多相距很远，进一步的工作，即使给出较好的上下界，面对的都是非常巨大的计算量。目前仍没有一种合理的通用方法求出Ramsey数的所有值。基于量子计算机相比经典计算机更强大的计算性能，本文在量子计算领域寻求计算Ramsey数的方法，重点研究了r-齐次超图Ramsey数的确定。研究内容主要包括以下两部分。第一部分，分析r-齐次超图的Ramsey数的运算机制，研究r-齐次超图从图表示到代数表示的转化，进而给出求解r-齐次超图的Ramsey数的组合优化问题。第二部分，深入研究Grover算法以及量子计数算法，将上述优化问题与Grover算法建立映射关系，给出对应该问题的量子搜索算法，最终设计求解r-齐次超图Ramsey数的量子计数算法，给出具体的量子线路逻辑框架，并对该算法进行性能分析。该算法是对经典算法的二次加速,为解决Ramsey数提供了新颖的研究思路。最后，本文对该领域研究提出了改进意见及展望。更多还原

【Abstract】 Quantum computation and quantum information is the study of the informationprocessing tasks that can be accomplished using quantum mechanical systems.Deutsch outlined the notion of a Universal Quantum Computer in1985and claimedwhether it is possible for a quantum computer to efficiently solve computationalproblems which have no efficient solution on a classical computer, even aprobabilistic Turing machine. Further evidence for the power of quantum computerscame in1995when Grover showed that another important problem-the problem ofconducting a search through some unstructured search space-could also be sped upon a quantum computer. The widespread applicability of search-based methodologieshas excited considerable interest in Grover’s algorithm.Ramsey theory is an important branch of combinatorial mathematics and theRamsey numbers in graph theory is an important research direction. However,determining the Ramsey number is NP problem, so far, only a few of the exact valueof Ramsey numbers is determined. Most known bounds are far apart, and even if thefurther work gives a better upper and lower bounds, it will always face enormousamount of computation. There is still no universal method to find a reasonablefunction to compute all of the Ramsey numbers.As quantum computers have more powerful computing performance compared toclassical computers, this paper seeks the approach to calculate Ramsey numbers in thefield of quantum computing. This paper focuses on the r-uniform hypergraph RamseyNumbers. The study includes the following two parts.In the first part, we analyze the computing mechanisms of the r-uniformhypergraph Ramsey numbers, research the representation of r-uniform hypergraphfrom the graph to the algebraic transformation, and give the combinatorialoptimization problem for r-uniform hypergraph Ramsey numbers.In the second part, we study quantum counting algorithm and Grover algorithm.We establish the mapping between the above optimization problem and Grover’salgorithm and give the quantum search algorithm for this problem. Finally we designthe quantum counting algorithm to computing the r-uniform hypergraph Ramseynumbers, give the quantum circuits and performance analysis of the algorithm. This algorithm has a quadratic speedup over the best classical one. Moreover, itprovides novel research ideas to address the Ramsey number. Finally, this paperpresents the improvements and outlook of the research in this field.更多还原