Quantum Monte Carlo Tree Search with Fixed Confidence

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. We 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 a complete instance-dependent query-complexity analysis, including upper and lower bounds; the lower-bound proof introduces a new quantum phase-testing result that may be useful beyond MCTS. We validate the theoretical results through simulation experiments.