A quantum algorithm for minimal spanning tree

Abstract

Quantum computing algorithms are considered for several problems in graph theory. Classical algorithms involve searching over some space for finding the minimal spanning tree problem in a graph. We modify classical Prim's algorithm and replace quantum search instead of classical search, of which it will lead to more efficient algorithm. Also we proposed the structure for non-classical algorithms and design the various phases of the probabilistic quantum-classical algorithm for classical and quantum parts. Finally, we represent the result of implementing and simulating Prim's algorithm in the probabilistic quantum-classical algorithm.