A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
arXiv:2408.12648 · doi:10.1088/1367-2630/adc765
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 (VQA) 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 QAOA parameter optimization as a sequential decision-making problem and tackle it with an adaptation of Monte Carlo Tree Search (MCTS), a common 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.
12+9 pages, 6+6 figures
References in corpus (46)
- Quantum Machine Learning
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms
- Ising formulations of many NP problems
- Supervised learning with quantum enhanced feature spaces
- QuTiP 2: A Python framework for the dynamics of open quantum systems
- Barren plateaus in quantum neural network training landscapes
- The theory of variational hybrid quantum-classical algorithms
- QuTiP: An open-source Python framework for the dynamics of open quantum systems
- Noisy intermediate-scale quantum (NISQ) algorithms
- Quantum Amplitude Amplification and Estimation
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quantum optimization using variational algorithms on near-term quantum devices
- Training variational quantum algorithms is NP-hard
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Quantum-assisted quantum compiling
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- Warm-starting quantum optimization
- Effect of barren plateaus on gradient-free optimization
- Noise Resilience of Variational Quantum Compiling
- Sequential minimal optimization for quantum-classical hybrid algorithms
- Quantum annealing initialization of the quantum approximate optimization algorithm
- Reachability Deficits in Quantum Approximate Optimization
- Variational Quantum State Eigensolver
- An Adaptive Optimizer for Measurement-Frugal Variational Algorithms
- Digitized-counterdiabatic quantum approximate optimization algorithm
- Parameter Concentration in Quantum Approximate Optimization
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- Global optimization of quantum dynamics with AlphaZero deep exploration
- Reinforcement Learning for Many-Body Ground-State Preparation Inspired by Counterdiabatic Driving
- Reinforcement Learning assisted Quantum Optimization
- Low depth mechanisms for quantum optimization
- Quantum approximate optimization via learning-based adaptive optimization
- Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
- Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
- Two-dimensional lattice gauge theory on a near-term quantum simulator: variational quantum optimization, confinement, and topological order
- QAOA Performance in Noisy Devices: The Effect of Classical Optimizers and Ansatz Depth
- Pulse variational quantum eigensolver on cross-resonance based hardware
- Warm-Starting and Quantum Computing: A Systematic Mapping Study
- Surrogate-based optimization for variational quantum algorithms
- Squeezing and quantum approximate optimization
- Connecting the Hamiltonian structure to the QAOA energy and Fourier landscape structure
- Reusability Report: Comparing gradient descent and monte carlo tree search optimization of quantum annealing schedules
- MCTS Based Agents for Multistage Single-Player Card Game