The MaxCut is a combinatorial problem consisting of finding the best sub-partitions of a graph, in order to maximize the value of a tailored-suited cost function. Although such specific problem belongs to the NP-hard class, quantum computing could lower the underlying computational complexity. The paramount quantum algorithm in literature to tackle the MaxCut is the QAOA, a trotterized version of adiabatic computation. Within such formulation, the cost function is encoded by a target Hamiltonian, whose spectrum matches the energy landscape to be handled by an optimization process. In the field of classical machine learning, a recent tool introduced to deal with graphs is provided by Graph Neural Networks (GNNs), whose peculiar architecture allows graph data to be embedded into Euclidean spaces, exploiting their topological structure as an intrinsic feature. We exploit the predictive power of GNNs, in order to classically emulate the energy landscape of the QAOA target Hamiltonian. In order to assess the predictive capacity of GNNs, we trained our model on graphs scaling from 3 to 12 vertices and achieving an accuracy between 0.9 and 0.99. We trained and tested the models on different topologies to assure the algorithm performances do not depend on the specific instance of the problem. Furthermore, the trained model proves to extend the correctness of the predictions for graphs up to 20 vertices still keeping a high accuracy. Such result envisages further development by exploiting HPC infrastructures and adapting warm starting techniques.
The MaxCut is a combinatorial problem consisting of finding the best sub-partitions of a graph, in order to maximize the value of a tailored-suited cost function. Although such specific problem belongs to the NP-hard class, quantum computing could lower the underlying computational complexity. The paramount quantum algorithm in literature to tackle the MaxCut is the QAOA, a trotterized version of adiabatic computation. Within such formulation, the cost function is encoded by a target Hamiltonian, whose spectrum matches the energy landscape to be handled by an optimization process. In the field of classical machine learning, a recent tool introduced to deal with graphs is provided by Graph Neural Networks (GNNs), whose peculiar architecture allows graph data to be embedded into Euclidean spaces, exploiting their topological structure as an intrinsic feature. We exploit the predictive power of GNNs, in order to classically emulate the energy landscape of the QAOA target Hamiltonian. In order to assess the predictive capacity of GNNs, we trained our model on graphs scaling from 3 to 12 vertices and achieving an accuracy between 0.9 and 0.99. We trained and tested the models on different topologies to assure the algorithm performances do not depend on the specific instance of the problem. Furthermore, the trained model proves to extend the correctness of the predictions for graphs up to 20 vertices still keeping a high accuracy. Such result envisages further development by exploiting HPC infrastructures and adapting warm starting techniques.
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.
The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.
Approximate combinatorial optimisation has emerged as one of the most promising application areas for quantum computers, particularly those in the near term. In this work, we focus on the quantum approximate optimisation algorithm (QAOA) for solving the MaxCut problem. Specifically, we address two problems in the QAOA, how to initialise the algorithm, and how to subsequently train the parameters to find an optimal solution. For the former, we propose graph neural networks (GNNs) as a warm-starting technique for QAOA. We demonstrate that merging GNNs with QAOA can outperform both approaches individually. Furthermore, we demonstrate how graph neural networks enables warm-start generalisation across not only graph instances, but also to increasing graph sizes, a feature not straightforwardly available to other warm-starting methods. For training the QAOA, we test several optimisers for the MaxCut problem up to 16 qubits and benchmark against vanilla gradient descent. These include quantum aware/agnostic and machine learning based/neural optimisers. Examples of the latter include reinforcement and meta-learning. With the incorporation of these initialisation and optimisation toolkits, we demonstrate how the optimisation problems can be solved using QAOA in an end-to-end differentiable pipeline.
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 Computing promises to solve complex combinatorial optimization problems more efficiently than classical methods, with the Quantum Approximate Optimization Algorithm (QAOA) being a leading candidate. Recent fixed-parameter variations of QAOA eliminate costly run-time optimization, but determining their optimal initialization as well as the number of required layers (p) for a target solution remains a critical, unsolved challenge. In this work, we propose a novel approach using a Graph Neural Network (GNN) to predict QAOA performance: Based on a graph representation of the problem, the GNN forecasts the probability of the optimal solution in the resulting distribution across different parameter initializations and layer depths for a wide variety of combinatorial optimization problems. We demonstrate that the GNN accurately predicts QAOA performance within a 10% margin of the true values. Furthermore, the model exhibits strong generalization capabilities across unseen problem classes, larger problem sizes, and higher layer counts. Our approach allows to identify viable problem instances for QAOA and to select an adequate parameter initialization strategy with minimal layer depth, without the need of costly parameter optimization.
The integration of quantum algorithms into machine learning pipelines offers a promising direction for addressing complex combinatorial optimization problems inherent in graph-structured data. This study investigates the use of the Quantum Approximate Optimization Algorithm (QAOA) as a quantum subroutine within a hybrid quantum–classical framework to enhance machine learning solutions for graph-based tasks. QAOA is employed to solve NP-hard graph optimization problems such as Max-Cut, graph coloring, and community detection, which are reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The solutions provided by QAOA are then incorporated into machine learning models, such as Graph Neural Networks (GNNs) or clustering algorithms, as enriched features or optimized graph partitions. The hybrid approach is evaluated on benchmark datasets, demonstrating competitive accuracy and improved scalability in certain problem instances compared to purely classical methods. The findings highlight the potential of leveraging near-term quantum hardware for augmenting classical learning systems in domains such as logistics, social network analysis, and computational biology.