Quantum Approaches for Degree-Constrained Minimum Spanning Tree Computation

Quantum optimization algorithms, particularly the Quantum Approximate Optimization Algorithm (QAOA), have significantly addressed combinatorial optimization problems. While QAOA has been applied to various NP-hard problems, such as Max-Cut and the Traveling Salesman Problem (TSP), its application to the Degree-Constrained Minimum Spanning Tree (DCMST) problem remains unexplored. Inspired by Fowler’s formulation, this work presents the first implementation of the DCMST Hamiltonian within QAOA and insights from its benefits to graph-based machine learning algorithms. We investigated two approaches: (i) the standard QAOA ansatz with an X mixer and (ii) a warm-started QAOA utilizing classical preprocessing to enhance convergence. We used these strategies to provide numerical results for instances with 3 and 4 nodes, employing the COBYLA optimizer and metaheuristic optimization techniques. Our findings serve as a proof of concept, demonstrating the feasibility of applying QAOA to this problem; however, the number of qubits scales as O(N2) with the number of nodes, limiting scalability. Current research focuses on developing more efficient implementations that encode the same number of binary variables using fewer qubits. This study contributes to the expanding field of quantum optimization, highlighting the potential of hybrid quantum-classical algorithms, especially with resource-efficient mixers and warm-starting techniques, to solve complex combinatorial problems and advance the development of scalable quantum algorithms.