Quantum‐Enhanced Simulated Annealing Using Rydberg Atoms
- 28 July 2025
- journal article
- Published by Wiley in Advanced Quantum Technologies
- Vol. 8 (12)
Abstract
Hybrid quantum‐classical algorithms offer a promising strategy for tackling computationally challenging problems, such as the maximum independent set (MIS) problem that plays a crucial role in areas like network design and data analysis. This study experimentally demonstrates that a Rydberg hybrid quantum‐classical algorithm, termed as quantum‐enhanced simulated annealing (QESA), provides a computational time advantage over standalone simulated annealing (SA), a classical heuristic optimization method. The performance of QESA is evaluated based on the approximation ratio and the Hamming distance, relative to the graph size. The analysis shows that QESA outperforms standalone SA by leveraging a warm‐start input derived from two types of Rydberg atomic array experimental data: quench evolution (QE) (implemented on the QuEra Aquila machine) and adiabatic quantum computing (AQC) (using the experimental dataset archived in K. Kim et al., Scientific Data 2024 , 11, 111). Based on these results, an estimate is provided for the maximum graph size that can be handled within a one‐day computational time limit on a standard personal computer. These findings suggest that QESA has the potential to offer a computational advantage over classical methods for solving complex optimization problems efficiently.Keywords
All Related Versions
This publication has 51 references indexed in Scilit:
- Approximating Maximum Independent Set on Rydberg Atom Arrays Using Local DetuningsAdvanced Quantum Technologies, 2024
- Rydberg‐Atom Graphs for Quadratic Unconstrained Binary Optimization ProblemsAdvanced Quantum Technologies, 2024
- Rydberg quantum wires for maximum independent set problemsNature Physics, 2022
- Quantum phases of matter on a 256-atom programmable quantum simulatorNature, 2021
- Quantum supremacy using a programmable superconducting processorNature, 2019
- Quantum Computation and Quantum Information2012
- On the Hamming distance in combinatorial optimization problems on hypergraph matchingsOptimization Letters, 2010
- Computational Complexity2009
- Finding a Maximal Weighted Independent Set in Wireless NetworksTelecommunication Systems, 2001
- Simulating physics with computersInternational Journal of Theoretical Physics, 1982