Quantum Monte Carlo Tree Search with Fixed Confidence

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.

All Paths All at Once: A Quantum Monte Carlo and Neural Committor Approach to Reaction Pathway Search
Chien-Chai Chang
arXiv1 Nov 2026PreprintCC BY 4.0Full textPhysical chemistry Quantum physics & quantum informationarXiv
FluxDisco: Symbolic Regression for Stoichiometric Dynamical Systems via Monte Carlo Graph Search
Cassandra Durr, Alvaro Köhn-Luque, Chris Jewell +1
arXiv4 Sep 2026PreprintCC BY 4.0Full textStatistics Computational physicsarXiv
Reformulating Pfaffian Quantum Monte Carlo with the Hybrid Monte Carlo formalism
Thomas Hauschild, Lin Wang, Finn L. Temmen +1
arXiv12 Oct 2026PreprintCC BY 4.0Full textCondensed matterarXiv
Quantum Monte Carlo calculation of δ_C in the superallowed beta decay of ¹⁰C
Maria Piarulli, R. B. Wiringa, Alessandro Lovato +2
arXiv13 May 2026PreprintarXiv licenceFull textNuclear physicsarXiv
Efficiency of Continuous-Time Quantum Monte Carlo Updates in the Ferromagnetic State of the Doped SU(3) Fermi-Hubbard Model
Juntaro Fujii, Kazuki Yamamoto, Akihisa Koga
arXiv21 Sep 2026PreprintarXiv licenceFull textCondensed matterarXiv

Cite

BibTeX RIS

BibTeX

@misc{hu2026quantum,
  title = {{Quantum Monte Carlo Tree Search with Fixed Confidence}},
  author = {Mingjie Hu and Jian-Qiang Hu and Enlu Zhou},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.33132},
  eprint = {2609.33132},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.33132},
}

RIS

TY  - UNPB
TI  - Quantum Monte Carlo Tree Search with Fixed Confidence
AU  - Mingjie Hu
AU  - Jian-Qiang Hu
AU  - Enlu Zhou
PY  - 2026
DA  - 2026/09/27
PB  - arXiv
DO  - 10.48550/arxiv.2609.33132
UR  - https://arxiv.org/abs/2609.33132
AB  - 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.
ER  -

Abstract

Related

Cite