QNSA: Quantum Neural Simulated Annealing for Combinatorial Optimization

Seongbin Kwon, Dohun Kim, Sunghye Park, Seojeong Kim, Seokhyeong Kang
Pohang University of Science and Technology


In the field of combinatorial optimization (CO), quantum computing is increasingly recognized for its potential to provide groundbreaking solutions. However, embedding the problems into quantum circuits presents significant challenges due to the complexities of scaling to large dimensions and the constraints in qubit count and circuit depth. In this paper, we introduce a quantum neural simulated annealing (QNSA) framework, combining both simulated annealing (SA) in the classical domain and quantum neural networks (QNNs) in the quantum domain to address the computational challenges for large-scale problems. By employing an SA algorithm, we can explore the vast combination space of optimization problems. In addition, by incorporating QNNs with proposed adaptive embedding and observable, our approach extends beyond the standalone capabilities of quantum computing, leaveraging the unique strengths of both quantum and classical computing paradigms. Our experimental results show that the QNSA framework significantly outperforms traditional classical computing methods, showcasing its potential for efficient problem-solving in complex scenarios.