A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
Year: 2025
Authors: Agirre A., van Nieuwenburg E., Wauters M.M.
Autors Affiliation: Donostia Int Phys Ctr DIPC, Manuel Lardizabal Pasealekua 4, Donostia San Sebastian 20018, Spain; Univ Copenhagen, Niels Bohr Inst, Ctr Quantum Devices, Univ Pk 5, DK-2100 Copenhagen, Denmark; Univ Basque Country UPV EHU, Dept PMAS Phys Chem & Technol, Manuel Lardizabal Pasealekua 3, Donostia San Sebastian 20018, Spain; Leiden Univ, Lorentz Inst, POB 9506, NL-2300 RA Leiden, Netherlands; Leiden Univ, Leiden Inst Adv Comp Sci, POB 9506, NL-2300 RA Leiden, Netherlands; Univ Trento, CNR INO Pitaevskii BEC Ctr, Via Sommar 14, I-38123 Trento, Italy; Univ Trento, Dept Phys, Via Sommar 14, I-38123 Trento, Italy; Trento Inst Fundamental Phys & Applicat, INFN TIFPA, Via Sommar 14, I-38123 Trento, Italy.
Abstract: The search for quantum algorithms to tackle classical combinatorial optimization problems has long been one of the most attractive yet challenging research topics in quantum computing. In this context, variational quantum algorithms (VQAs) are a promising family of hybrid quantum-classical methods tailored to cope with the limited capability of near-term quantum hardware. However, their effectiveness is hampered by the complexity of the classical parameter optimization which is prone to getting stuck either in local minima or in flat regions of the cost-function landscape. The clever design of efficient optimization methods is therefore of fundamental importance for fully leveraging the potential of VQAs. In this work, we approach parameter optimization as a sequential decision-making problem and tackle it with an adaptation of Monte Carlo Tree Search, a powerful artificial intelligence technique designed for efficiently exploring complex decision graphs. We show that leveraging regular parameter patterns deeply affects the decision-tree structure and allows for a flexible and noise-resilient optimization strategy suitable for near-term quantum devices. Our results shed further light on the interplay between artificial intelligence and quantum information and provide a valuable addition to the toolkit of variational quantum circuits.
Journal/Review: NEW JOURNAL OF PHYSICS
Volume: 27 (4) Pages from: 43014-1 to: 43014-23
More Information: We warmly thank M Burrello and G Giedke for useful discussions and advice. AA acknowledges funding by the Department of Education of the Basque Government through the Project PIBA_2023_1_0021 (TENINT), and that this work has been produced with the support of a 2023 Leonardo Grant for Researchers in Physics, BBVA Foundation. The BBVA Foundation is not responsible for the opinions, comments and contents included in the project and/or the results derived therefrom, which are the total and absolute responsibility of the authors. MW has received funding from the European Union’s Horizon Europe research and innovation programme under Grant Agreement No. 101080086 NeQST. This project has been supported by the Provincia Autonoma di Trento and Q@TN, the joint lab between the University of Trento, FBK-Fondazione Bruno Kessler, INFN-National Institute for Nuclear Physics, and CNR-National Research Council. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Commission. Neither the European Union nor the granting authority can be held responsible for them. This work was supported by the Dutch National Growth Fund (NGF), as part of the Quantum Delta NL programme.KeyWords: variational quantum algorithms; quantum optimization; artificial intelligence; NISQ algorithmsDOI: 10.1088/1367-2630/adc765
