Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

GNN-Based Performance Prediction of Quantum Optimization of Maximum Independent Set

Atefeh Sohrabizadeh, Wan-Hsuan Lin, Daniel Bochen Tan, Madelyn Cain, Sheng-Tao Wang, Mikhail D. Lukin, Jason Cong

Published Oct 27, 2024• 1 citation
Publisher

Abstract

Maximum Independent Set (MIS) is an NP-hard optimization problem with wide-ranging applications in science and technology. Recently, a super-linear speedup over classical simulated annealing in solving MIS was experimentally observed using a Rydberg atom array (RAA) quantum computer. The extent of the observed speedup depended on the graph instance and the circuit depth of the quantum algorithm. Due to the limited availability of RAA, it is beneficial to be able to efficiently predict the quantum optimization performance on a given graph and circuit depth prior to running it. In this work, we present a graph neural network (GNN)-based performance predictor of the RAA-based MIS optimizer. Our experimental results achieve accuracy with an average root mean squared error (RMSE) of 0.03 out of the range [0, 1]. We open source the experimental data collected for this study at https://github.com/UCLA-VAST/RAAMIS.

DOI
10.1145/3676536.3697129

Related papers

Quantum optimization of maximum independent set using Rydberg atom arrays

Sepehr Ebadi, Alexander Keesling, Madelyn Cain +21 more

Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.

arXiv:2202.09372•Science•May 5, 2022•423 citations

Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays

Hannes Pichler, Sheng-Tao Wang, Leo Zhou +2 more

We describe and analyze an architecture for quantum optimization to solve maximum independent set (MIS) problems using neutral atom arrays trapped in optical tweezers. Optimizing independent sets is one of the paradigmatic, NP-hard problems in computer science. Our approach is based on coherent manipulation of atom arrays via the excitation into Rydberg atomic states. Specifically, we show that solutions of MIS problems can be efficiently encoded in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg blockade mechanism. By studying the performance of leading classical algorithms, we identify parameter regimes, where computationally hard instances can be tested using near-term experimental systems. Practical implementations of both quantum annealing and variational quantum optimization algorithms beyond the adiabatic principle are discussed.

arXiv:1808.10816•Aug 31, 2018•34 citations

Graph Neural Network-Based Predictor for Optimal Quantum Hardware Selection

Antonio Tudisco, Deborah Volpe, Giacomo Orlandi +1 more

The growing variety of quantum hardware technologies, each with unique peculiarities such as connectivity and native gate sets, creates challenges when selecting the best platform for executing a specific quantum circuit. This selection process usually involves a brute-force approach: compiling the circuit on various devices and evaluating performance based on factors such as circuit depth and gate fidelity. However, this method is computationally expensive and does not scale well as the number of available quantum processors increases. In this work, we propose a Graph Neural Network (GNN)based predictor that automates hardware selection by analyzing the Directed Acyclic Graph (DAG) representation of a quantum circuit. Our study evaluates 498 quantum circuits (up to 27 qubits) from the MQT Bench dataset, compiled using Qiskit on four devices: three superconducting quantum processors (IBM-Kyiv, IBM-Brisbane, IBM-Sherbrooke) and one trappedion processor (IONQ-Forte). Performance is estimated using a metric that integrates circuit depth and gate fidelity, resulting in a dataset where 93 circuits are optimally compiled on the trappedion device, while the remaining circuits prefer superconducting platforms. By exploiting graph-based machine learning, our approach avoids extracting the circuit features for the model evaluation but directly embeds it as a graph, significantly accelerating the optimal target decision-making process and maintaining all the information. Experimental results prove$\mathbf{9 4. 4 \%}$accuracy and an$\mathbf{8 5. 5 \%}$F1 score for the minority class, effectively predicting the best compilation target. The developed code is publicly available on GitHub (https://github.com/antotu/GNN-Model-Quantum-Predictor).

arXiv:2507.19093•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Quantum Computing Dataset of Maximum Independent Set Problem on King's Lattice of over Hundred Rydberg Atoms

Kangheun Kim, Minhyuk Kim, Juyoung Park +2 more

Finding the maximum independent set (MIS) of a large-size graph is a nondeterministic polynomial-time (NP)-complete problem not efficiently solvable with classical computations. Here, we present a set of quantum adiabatic computing data of Rydberg-atom experiments performed to solve the MIS problem of up to 141 atoms randomly arranged on the King's lattice. A total of 582,916 events of Rydberg-atom measurements are collected for experimental MIS solutions of 733,853 different graphs. We provide the raw image data along with the entire binary determinations of the measured many-body ground states and the classified graph data, to offer bench-mark testing and advanced data-driven analyses for validation of the performance and system improvements of the Rydberg-atom approach.

arXiv:2311.13803•Nov 23, 2023•0 citations

Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms

Lucas T. Brady, Stuart Hadfield

Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study a new class of hybrid approaches to quantum optimization, termed Iterative Quantum Algorithms, which in particular generalizes the Recursive Quantum Approximate Optimization Algorithm. This paradigm can incorporate hard problem constraints, which we demonstrate by considering the Maximum Independent Set (MIS) problem. We show that, for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper $p>1$ circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.

arXiv:2309.13110•Sep 22, 2023•4 citations

QAOA-Predictor: Forecasting Success Probabilities and Minimal Depths for Efficient Fixed-Parameter Optimization

Rodrigo Coelho, Georg Kruse, Jeanette Miriam Lorenz

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.

quant-pharXiv:2603.02990•Mar 4, 2026•0 citations
Maximum Independent Set (MIS) is an NP-hard optimization problem with wide-ranging applications in science and technology. Recently, a super-linear speedup over classical simulated annealing in solving MIS was experimentally observed using a Rydberg atom array (RAA) quantum computer. The extent of the observed speedup depended on the graph instance and the circuit depth of the quantum algorithm. Due to the limited availability of RAA, it is beneficial to be able to efficiently predict the quantum optimization performance on a given graph and circuit depth prior to running it. In this work, we present a graph neural network (GNN)-based performance predictor of the RAA-based MIS optimizer. Our experimental results achieve accuracy with an average root mean squared error (RMSE) of 0.03 out of the range [0, 1]. We open source the experimental data collected for this study at https://github.com/UCLA-VAST/RAAMIS.
Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.
We describe and analyze an architecture for quantum optimization to solve maximum independent set (MIS) problems using neutral atom arrays trapped in optical tweezers. Optimizing independent sets is one of the paradigmatic, NP-hard problems in computer science. Our approach is based on coherent manipulation of atom arrays via the excitation into Rydberg atomic states. Specifically, we show that solutions of MIS problems can be efficiently encoded in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg blockade mechanism. By studying the performance of leading classical algorithms, we identify parameter regimes, where computationally hard instances can be tested using near-term experimental systems. Practical implementations of both quantum annealing and variational quantum optimization algorithms beyond the adiabatic principle are discussed.
The growing variety of quantum hardware technologies, each with unique peculiarities such as connectivity and native gate sets, creates challenges when selecting the best platform for executing a specific quantum circuit. This selection process usually involves a brute-force approach: compiling the circuit on various devices and evaluating performance based on factors such as circuit depth and gate fidelity. However, this method is computationally expensive and does not scale well as the number of available quantum processors increases. In this work, we propose a Graph Neural Network (GNN)based predictor that automates hardware selection by analyzing the Directed Acyclic Graph (DAG) representation of a quantum circuit. Our study evaluates 498 quantum circuits (up to 27 qubits) from the MQT Bench dataset, compiled using Qiskit on four devices: three superconducting quantum processors (IBM-Kyiv, IBM-Brisbane, IBM-Sherbrooke) and one trappedion processor (IONQ-Forte). Performance is estimated using a metric that integrates circuit depth and gate fidelity, resulting in a dataset where 93 circuits are optimally compiled on the trappedion device, while the remaining circuits prefer superconducting platforms. By exploiting graph-based machine learning, our approach avoids extracting the circuit features for the model evaluation but directly embeds it as a graph, significantly accelerating the optimal target decision-making process and maintaining all the information. Experimental results prove94.4%\mathbf{9 4. 4 \%}94.4%accuracy and an85.5%\mathbf{8 5. 5 \%}85.5%F1 score for the minority class, effectively predicting the best compilation target. The developed code is publicly available on GitHub (https://github.com/antotu/GNN-Model-Quantum-Predictor).
Finding the maximum independent set (MIS) of a large-size graph is a nondeterministic polynomial-time (NP)-complete problem not efficiently solvable with classical computations. Here, we present a set of quantum adiabatic computing data of Rydberg-atom experiments performed to solve the MIS problem of up to 141 atoms randomly arranged on the King's lattice. A total of 582,916 events of Rydberg-atom measurements are collected for experimental MIS solutions of 733,853 different graphs. We provide the raw image data along with the entire binary determinations of the measured many-body ground states and the classified graph data, to offer bench-mark testing and advanced data-driven analyses for validation of the performance and system improvements of the Rydberg-atom approach.
Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study a new class of hybrid approaches to quantum optimization, termed Iterative Quantum Algorithms, which in particular generalizes the Recursive Quantum Approximate Optimization Algorithm. This paradigm can incorporate hard problem constraints, which we demonstrate by considering the Maximum Independent Set (MIS) problem. We show that, for QAOA with depth p=1p=1p=1, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper p>1p>1p>1 circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.
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.