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.
Comments
29 pages, submitted to Quantum Machine Intelligence
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.
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.
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.
To mitigate the barren plateau problem, effective parameter initialization is crucial for optimizing the Quantum Approximate Optimization Algorithm (QAOA) in the near-term Noisy Intermediate-Scale Quantum (NISQ) era. Prior physicsdriven approaches leveraged the optimal parameter concentration phenomenon, utilizing medium values of previously optimized QAOA parameters stored in databases as initialization for new graphs. However, this medium-value-based strategy lacks generalization capability. Conversely, prior computer-sciencebased approaches employed graph neural networks (GNNs) trained on previously optimized QAOA parameters to predict initialization values for new graphs. However, these approaches neglect key physics-informed QAOA principles, such as parameter concentration, symmetry, and adiabatic evolution, resulting in suboptimal parameter predictions and limited performance improvements. Furthermore, no existing GNN-based methods support parameter initialization for QAOA circuits with variable depths or for solving weighted Max-Cut problems. This paper introduces QSeer, a quantum-inspired GNN designed for accurate QAOA parameter prediction. First, we propose a quantum-inspired input data normalization technique to ensure a consistent input scale and mitigate the influence of varying feature magnitudes. By integrating key physics-informed QAOA principles, such as parameter concentration, symmetry, and adiabatic evolution, this approach enhances QSeer's training stability and convergence. Second, we encode Max-Cut edge weights as edge attributes in QSeer's GNN framework, enabling parameter prediction for QAOA circuits solving both unweighted and weighted Max-Cut problems. Third, we incorporate the circuit depthpas an input, allowing QSeer to generalize parameter predictions across different QAOA depths. Compared to prior physics- and computer-science-driven methods, QSeer improves the initial approximation ratio and convergence speed of QAOA circuits across diverse graphs by6%∼68%and5×∼10×, respectively. The source code is publicly available at https://github.com/UnchartedRLab/QSeer.
Abstract The Quantum Approximate Optimization Algorithm (QAOA), a pivotal paradigm in the realm of variational quantum algorithms (VQAs), offers promising computational advantages for tackling combinatorial optimization problems. Well-defined initial circuit parameters, responsible for preparing a parameterized quantum state encoding the solution, play a key role in optimizing QAOA. However, classical optimization techniques encounter challenges in discerning optimal parameters that align with the optimal solution. In this work, we propose a hybrid optimization approach that integrates Gated Recurrent Units (GRU), Convolutional Neural Networks (CNN), and a bilinear strategy as an innovative alternative to conventional optimizers for predicting optimal parameters of QAOA circuits. GRU serves to stochastically initialize favorable parameters for depth-1 circuits, while CNN predicts initial parameters for depth-2 circuits based on the optimized parameters of depth-1 circuits. To assess the efficacy of our approach, we conducted a comparative analysis with traditional initialization methods using QAOA on Erdős-Rényi graph instances, revealing superior optimal approximation ratios. We employ the bilinear strategy to initialize QAOA circuit parameters at greater depths, with reference parameters obtained from GRU-CNN optimization. This approach allows us to forecast parameters for a depth-12 QAOA circuit, yielding a remarkable approximation ratio of 0.998 across 10 qubits, which surpasses that of the random initialization strategy and the PPN2 method at a depth of 10. The proposed hybrid GRU-CNN bilinear optimization method significantly improves the effectiveness and accuracy of parameters initialization, offering a promising iterative framework for QAOA that elevates its performance.
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.