Computing Hypergraph Ramsey Numbers By Using Quantum Circuit

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.