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.
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.
In recent years, quantum computing has emerged as a transformative force in the field of combinatorial optimization, offering novel approaches to tackling complex problems that have long challenged classical computational methods. Among these, the Quantum Approximate Optimization Algorithm (QAOA) stands out for its potential to efficiently solve the Max-Cut problem, a quintessential example of combinatorial optimization. However, practical application faces challenges due to current limitations on quantum computational resource. Our work optimizes QAOA initialization, using Graph Neural Networks (GNN) as a warm-start technique. This sacrifices affordable computational resource on classical computer to reduce quantum computational resource overhead, enhancing QAOA's effectiveness. Experiments with various GNN architectures demonstrate the adaptability and stability of our framework, highlighting the synergy between quantum algorithms and machine learning. Our findings show GNN's potential in improving QAOA performance, opening new avenues for hybrid quantum-classical approaches in quantum computing and contributing to practical applications.
Quantum optimization algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), are emerging as promising heuristics for solving complex combinatorial problems. To improve performance, several extensions to the standard QAOA framework have been proposed in recent years. Two notable directions include: warm-starting techniques, which incorporate classical approximate solutions to guide the quantum evolution, and custom mixer Hamiltonians, such asXYmixers, which constrain the search to feasible subspaces aligned with the structure of the problem. In this work, we propose an approach that integrates these two strategies: a warm-start initialization with anXYmixer ansatz, enabling constraint, preserving quantum evolution biased toward high-quality classical solutions. The method begins by reformulating the combinatorial problem as a MaxCut instance, solved approximately using the Goemans-Williamson algorithm. The resulting binary solution is relaxed and used to construct a biased superposition over one-hot quantum states that preserves the Hamming weight 1, maintaining compatibility with theXYmixers constraints. We evaluate the approach on 5-city instances of the Traveling Salesperson Problem, a canonical optimization problem frequently encountered as a subroutine in real-world route planning problems. Our method is benchmarked against both the standardXY-mixer QAOA and a warm-start-only variant based on MaxCut relaxation. Results show that the proposed combination consistently outperforms both baselines in terms of the percentage and rank of optimal solutions, demonstrating the effectiveness of combining structured initializations with constraint-aware quantum evolution for optimization problems.
The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.
This paper is a comparison between classical and quantum inspired methods for solving the max-flow problem, which is commonly a foundational challenge in optimization and graph theory. This study will investigate the feasibility and performance of applying the Quantum Approximate Optimization Algorithm (QAOA) and other hybrid quantum-classical approaches to address the max-flow problem. This paper starts with comparing quantum approaches with well-established classical methods such as the Ford-Fulkerson and Edmonds-Karp.The main aim of this work is to asses how close quantum-inspired formulations can get to classical approaches in terms of their flow value as well as their runtime. Implementations are developed using the Qiskit framework on simulated quantum backends and compared against classical baselines across synthetic graph instances of varying sizes and densities. Experimentally, it can be seen that quantum approaches implemented using the QAOA technique managed to attain flow solutions comparable to classical ones, demonstrating similar accuracy, and in certain very dense graph configurations, competitive runtime performance due to parallelization in state-vector computing.These findings suggest that although current quantum-inspired approaches may not yet surpass classical algorithms in efficiency, but they can replicate their outcomes with reasonable fidelity. This provides an important validation of their applicability to combinatorial optimization. This study also lays groundwork for future research to explore hardware-level implementations, scalability enhancements, and also hybrid integration strategies for quantum optimization in network flow problems.
The Quantum Approximate Optimization Algorithm (QAOA) was developed to tackle combinatorial optimization problems, such as the Travelling Salesman Problem (TSP), by approximating solutions through quantum mechanics. QAOA utilizes a unitary transformation to prepare a quantum state that encodes a potential solution, with the parameters of the unitary optimized by a classical optimizer. This study evaluates QAOA's performance on the NP-hard TSP, comparing the standard version of the algorithm from Farhi \cite{qaoa} and an enhancement, Warm-Start QAOA \cite{warmstart}, to a classical solver. The TSP seeks the shortest possible route that visits a set of cities, a problem that is amenable to quantum formulation using platforms like Qiskit. Warm-Start QAOA initializes the algorithm's parameters based on a solution to a relaxed version of the problem, offering potential improvements in optimization efficiency. By comparing these quantum algorithms to a classical solver, we provide a comprehensive assessment of their performance across key metrics, including route quality, execution time, and scalability. Through this analysis, we highlight the relative strengths and weaknesses of QAOA and its warm-start variant for solving the TSP, alongside the classical approach, offering insights into their potential for route optimization and practical applications in realworld settings. We conclude that, while the classical solver significantly outperforms QAOA and warm-start QAOA at smaller-scale problem cases, warm-Start QAOA has the potential to yield advantages at a larger scale when run on NISQ-era noisy hardware.