Quantum Algorithm for Testing Graph Completeness

Abstract

Testing graph completeness is a critical problem in computer science and network theory. Leveraging quantum computation, we present an efficient algorithm using the Szegedy quantum walk and quantum phase estimation (QPE). Our algorithm, which takes the number of nodes and the adjacency matrix as input, constructs a quantum walk operator and applies QPE to estimate its eigenvalues. These eigenvalues reveal the graph's structural properties, enabling us to determine its completeness. We establish a relationship between the number of nodes in a complete graph and the number of marked nodes, optimizing the success probability and running time. The time complexity of our algorithm is $\mathcal{O}({\log }^{2}n)$, where $n$ is the number of nodes of the graph. offering a clear quantum advantage over classical methods. This approach is useful in network structure analysis, evaluating classical routing algorithms, and assessing systems based on pairwise comparisons.

Revtex file, color figures. Notation improved, typos corrected

References in corpus (13)

• Quantum Mechanics helps in searching for a needle in a haystack
• Community detection algorithms: a comparative analysis
• Information and Computation: Classical and Quantum Aspects
• Random Walks: A Review of Algorithms and Applications
• A Quantum-Quantum Metropolis Algorithm
• Google in a Quantum Network
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Quantum Walk Search on the Complete Bipartite Graph
• Efficient quantum circuits for Szegedy quantum walks
• Equivalence of Szegedy's and Coined Quantum Walks
• Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
• Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations