Algorithm for Finding the Maximum Clique Based on Continuous Time Quantum Walk

Abstract

In this work, we consider the application of continuous time quantum walking(CTQW) to the Maximum Clique(MC) Problem. Performing CTQW on graphs will generate distinct periodic probability amplitude for different vertices. We will show that the intensity of the probability amplitude at frequency indeed implies the clique structure of some special kinds of graph. And recursive algorithms with time complexity $O(N^5)$ in classical computers for finding the maximum clique are proposed. We have experimented on random graphs where each edge exists with probabilities 0.3, 0.5 and 0.7. Although counter examples are not found for random graphs, whether these algorithms are universal is not known to us.

References in corpus (7)

• Quantum Mechanics helps in searching for a needle in a haystack
• A Quantum Approximate Optimization Algorithm
• Quantum Computation and Decision Trees
• Perfect state transfer in quantum spin networks
• Two-particle quantum walks applied to the graph isomorphism problem
• Nested quantum search and NP-complete problems
• Adiabatic quantum search algorithm for structured problems