Quantum optimization algorithms are some of the most promising algorithms expected to show a quantum advantage. When solving quadratic unconstrained binary optimization problems, quantum optimization algorithms usually provide an approximate solution. The solution quality, however, is not guaranteed to be good enough to warrant selecting it over the classical optimizer solution, as it depends on the problem instance. Here, we present an algorithm based on a graph neural network that can choose between a quantum optimizer and classical optimizer using performance prediction. In addition, we present an approach that predicts the optimal parameters of a variational quantum optimizer. We tested our approach with a specific quantum optimizer, the quantum approximate optimization algorithm, applied to the Max-Cut problem, which is an example of a quadratic unconstrained binary optimization problem. We observed qualitatively and quantitatively that graph neural networks are suited for a performance prediction of up to nine-vertex Max-Cut instances with a quantum approximate optimization algorithm with a depth of up to three. For the performance prediction task, the average difference between the actual quantum algorithm performance and the predicted performance is below 19.7% and, for the parameter prediction task, the solution using the predicted parameters is within 2.7% of the optimal parameter solution. Our method therefore has the capacity to find problems that are best suited for quantum solvers. The proposed method and the corresponding algorithm can be used for hybrid quantum algorithm selection.
Quantum optimization algorithms are some of the most promising algorithms expected to show a quantum advantage. When solving quadratic unconstrained binary optimization problems, quantum optimization algorithms usually provide an approximate solution. The solution quality, however, is not guaranteed to be good enough to warrant selecting it over the classical optimizer solution, as it depends on the problem instance. Here, we present an algorithm based on a graph neural network that can choose between a quantum optimizer and classical optimizer using performance prediction. In addition, we present an approach that predicts the optimal parameters of a variational quantum optimizer. We tested our approach with a specific quantum optimizer, the quantum approximate optimization algorithm, applied to the Max-Cut problem, which is an example of a quadratic unconstrained binary optimization problem. We observed qualitatively and quantitatively that graph neural networks are suited for a performance prediction of up to nine-vertex Max-Cut instances with a quantum approximate optimization algorithm with a depth of up to three. For the performance prediction task, the average difference between the actual quantum algorithm performance and the predicted performance is below 19.7% and, for the parameter prediction task, the solution using the predicted parameters is within 2.7% of the optimal parameter solution. Our method therefore has the capacity to find problems that are best suited for quantum solvers. The proposed method and the corresponding algorithm can be used for hybrid quantum algorithm selection.
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.
Quadratic unconstrained binary optimization (QUBO) tasks are very important in chemistry, finance, job scheduling, and so on, which can be represented using graph structures, with the variables as nodes and the interaction between them as edges. Variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) and its variants, present a promising way, potentially exceeding the capabilities of classical algorithms, for addressing QUBO tasks. However, the possibility of using message-passing machines, inspired by classical graph neural networks, to enhance the power and performance of these quantum algorithms for QUBO tasks was not investigated. This study introduces a novel variational quantum graph optimization algorithm that integrates the message-passing mechanism, which demonstrates significant improvements in performance for solving QUBO problems in terms of resource efficiency and solution precision, compared to QAOA, its variants, and other quantum graph neural networks. Furthermore, in terms of scalability on QUBO tasks, our algorithm shows superior performance compared to QAOA, presenting a substantial advancement in the field of quantum approximate optimization.
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.
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.
Abstract The Quantum approximate optimization algorithm (QAOA) is a quantum-classical hybrid algorithm aiming to produce approximate solutions for combinatorial optimization problems. In the QAOA, the quantum part prepares a quantum parameterized state that encodes the solution, where the parameters are optimized by a classical optimizer. However, it is difficult to find optimal parameters when the quantum circuit becomes deeper. Hence, there is numerous active research on the performance and the optimization cost of QAOA. In this work, we build a convolutional neural network to predict parameters of depth p + 1 QAOA instance by the parameters from the depth p QAOA counterpart. We propose two strategies based on this model. First, we recurrently apply the model to generate a set of initial values for a certain depth QAOA. It successfully initiates depth 10 QAOA instances, whereas each model is only trained with the parameters from depths less than 6. Second, the model is applied repetitively until the maximum expected value is reached. An average approximation ratio of 0.9759 for Max-Cut over 264 Erdős–Rényi graphs is obtained, while the optimizer is only adopted for generating the first input of the model.
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.