Quantum Monte Carlo Tree Search with Fixed Confidence

Mingjie Hu; Jian-Qiang Hu; Enlu Zhou

quant-phSep 27, 2026

Quantum Monte Carlo Tree Search with Fixed Confidence

Authors: Mingjie Hu, Jian-Qiang Hu, Enlu Zhou

Organizations: School of Management, Fudan University · H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology

Abstract

Recent advances in quantum computing are opening new opportunities for computationally intensive decision problems. This paper studies how quantum computing can improve Monte Carlo tree search (MCTS) in the fixed-confidence setting, where the goal is to identify a near-optimal move in a given game tree with high probability while minimizing query complexity. We first formulate MCTS under a quantum oracle model. We then develop a quantum MCTS algorithm (QMCTS) that combines threshold-based elimination on the search tree with quantum Monte Carlo estimation to reduce the cost of evaluating stochastic leaf values. We establish an instance-dependent lower bound on the query complexity and derive a corresponding upper bound for QMCTS. The lower-bound analysis introduces a new quantum phase-testing result that may also be useful beyond MCTS. We validate the theoretical results through simulation experiments and further demonstrate the feasibility of QMCTS on real quantum hardware.

Figures & tables

Figure 1: Query Complexity Scaling with Gap and Precision

Figure 2: Large-scale chess query complexity.

Figure 3: Query Complexity Scaling under A Bounded Three-point Distribution

Figure 4: Query Complexity Scaling under A Bounded Five-point Discrete Uniform Distribution

Explore similar work

Magic-Informed Quantum Architecture Search
May 5, 2026Vincenzo Lipardi, Domenica Dibenedetto, Georgios Stamoulis +1
Department of Advanced Computing Sciences Maastricht University Maastricht, The Netherlands
Multi-primitive in-memory computing for Monte Carlo tree search
Jul 24, 2026Tergel Molom-Ochir, Benjamin F. Morris, Yintao He +6Compute-in-Memory Energy-Efficient ML
Department of Electrical and Computer Engineering, Duke University, Durham, 27708, NC, USA. · Hewlett Packard Labs, Milpitas, 95035, CA, USA.
AlphaCNOT: Learning CNOT Minimization with Model-Based Planning
Apr 15, 2026Jacopo Cossio, Daniele Lizzio Bosco, Riccardo Romanello +2Quantum Circuit Compilation Quantum RL
University of Udine, Italy · University of Udine & University “Federico II” of Naples, Italy

May 5, 2026J/K move · Enter open · S save

Magic-Informed Quantum Architecture Search

Vincenzo Lipardi, Domenica Dibenedetto, Georgios Stamoulis, Mark H. M. Winands

Department of Advanced Computing Sciences Maastricht University Maastricht, The Netherlands

Open paper AskPDF arXiv

Nonstabilizerness, commonly referred to as magic, is a fundamental resource underpinning quantum advantage. In this paper, we propose a magic-informed quantum architecture search (QAS) technique that enables control over a quantum resource within the general framework of circuit design. Inspired by the AlphaGo approach, we tackle the problem with a Monte Carlo Tree Search technique equipped with a Graph Neural Network (GNN) that estimates the magic of candidate quantum circuits. The GNN model induces a magic-based bias that steers the search toward either high- or low-magic regimes, depending on the target objective. We benchmark the proposed magic-informed QAS technique on both the structured ground-state energy problem and on the more general quantum state approximation problem, spanning different sizes and target magic levels. Experimental results show that the proposed technique effectively influences the magic across the search tree and notably also on the resulting final circuit, even in regimes where the GNN operates on out-of-distribution instances. Although introducing a problem-agnostic magic bias could, in principle, constrain the search dynamics, we observe consistent improvements in solution quality across all problems tested.

Abstract

Explore similar work

Magic-Informed Quantum Architecture Search

Multi-primitive in-memory computing for Monte Carlo tree search

AlphaCNOT: Learning CNOT Minimization with Model-Based Planning