Paper deep dive
Quantum Monte Carlo Tree Search with Fixed Confidence
Mingjie Hu, Jian-Qiang Hu, Enlu Zhou
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2609.33132v1
- Canonical: https://arxiv.org/abs/2609.33132v1
Trouble viewing inline? Open PDF directly →
Full Text
73,255 characters extracted from source content.
Expand or collapse full text
Quantum Monte Carlo Tree Search with Fixed Confidence Mingjie Hu Jian-Qiang Hu Enlu Zhou 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. keywordsQuantum computing, Monte Carlo tree search, Fixed confidence, Query complexity †runningauthor: Hu, Hu and Zhou†runningtitle: Quantum Monte Carlo Tree Search with Fixed Confidence†authors: School of Management, Fudan University H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology11 1 This work was done during Mingjie Hu’s visit at Georgia Institute of Technology. 23110690009@m.fudan.edu.cn School of Management, Fudan University, hujq@fudan.edu.cn H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, enlu.zhou@isye.gatech.edu †affiliation: †affiliation: †affiliation: †affiliation: †affiliation: †affiliation: 1 Introduction Monte Carlo three search (MCTS) is a search framework aiming to find the optimal decision based on the search tree built by random sampling of the decision space (Shah et al. 2022). It has achieved remarkable success in sequential decision making with a tree representation, such as the game of Go (Silver et al. 2017b), chess, and shogi (Silver et al. 2017a). The central statistical task is to compare candidate actions using noise simulation outcomes and take the optimal action. The effectiveness of MCTS, however, can be limited by the number of simulation required to identify the best move for a given node on the tree. Quantum computing has advanced rapidly and has shown promise in areas such as combinatorial optimization (Abbas et al. 2024), simulation optimization (Hu et al. 2025, Hu et al. 2026), and machine learning (Biamonte et al. 2017). For certain computational tasks, quantum algorithms can achieve substantial speedups over their classical counterparts. This naturally raises the following question: What can quantum computing offer to MCTS? This question is relevant to a broad range of learning and decision-making problems in which MCTS serves as a key computational tool. To answer this question, we adopt the fixed-confidence MCTS formulation of Kaufmann and Koolen (2017) and consider a two-player zero-sum game in which the possible sequences of play are represented by a maximin game tree. MAX nodes correspond to decisions made by the first player, while MIN nodes correspond to decisions made by the second player. The terminal payoffs are stochastic, and the objective is to identify a root move whose value is within ϵ>0ε>0 of the optimal root value with probability at least 1−δ1-δ. However, designing a quantum MCTS algorithm raises several fundamental technical challenges: • Quantum Information Extraction. The advantage of quantum computing relies on processing information encoded in quantum superposition. However, extracting classical information (such as the mean estimate) requires measurement, which collapses the quantum state and prevents its further use. This constraints makes many classical sequential algorithms unsuitable in the quantum setting and requires new algorithmic designs. • Tree-Structured Exploration. The recursive MAX-MIN structure couples the leaf values, and the effect of each leaf depends on its position in the tree. This structural dependence makes it difficult to characterize the intrinsic difficulty of a problem instance and to obtain matching upper and lower bounds on the query complexity. • Algorithm Performance Analysis. Classical query-complexity lower bounds often rely on change-of-measure arguments from sequential hypothesis testing (Lattimore and Szepesvári 2020). These arguments do not directly extend to the quantum setting, so new tools are needed to establish instance-dependent lower bounds for quantum algorithms. To aid the reader, we provide some intuitive interpretation of the quantum concepts used in this paper. Classical MCTS typically uses a simulation model to generate stochastic rollouts and estimate the values of left nodes and candidate moves. In the quantum setting, the simulation model is accessed through a quantum oracle model, which serves as the quantum counterpart of a classical simulator. A query to a classical simulator at a leaf node returns a random observation, while a query to a quantum oracle prepares a quantum sample, which is a superposition state that encodes the possible outcomes. Measuring this state produces a classical sample but collapses the quantum state and destroys the quantum advantage. Accordingly, classical sample complexity is replaced by quantum query complexity as the main measure of computational cost. This restriction on information extraction motivates the lazy-measurement principle used in our algorithm design. In this work, we assume access to the quantum oracle model and focus on the design and analysis of MCTS algorithm. This assumption is natural when the underlying simulator is implemented by a classical program with accessible source code. Such a program can be represented as a Boolean circuit and implemented reversibly as a quantum circuit with polynomial overhead (Wang et al. 2021a). Similar assumptions are widely used in the quantum algorithm literature (Wang et al. 2021b, Zhong et al. 2023, Hu et al. 2025). The main contributions of this paper are summarized as follows: • We formulate quantum MCTS in the fixed-confidence setting and propose a quantum MCTS algorithm (QMCTS) that combines quantum Monte Carlo (QMC) estimation with threshold-based elimination under a lazy-measurement principle. We prove that QMCTS identifies an ϵε-optimal root move with probability at least 1−δ1-δ. • We establish an instance-dependent query-complexity upper bound for QMCTS and derive a lower bound for adaptive quantum algorithms. We characterize conditions under which the upper and lower bounds match up to logarithmic factors. Both analyses depend explicitly on the tree structure. The lower-bound analysis also introduces a new sequential quantum phase-testing result that may be useful beyond MCTS. • We conduct numerical experiments to verify the theoretical results and evaluate the performance of the proposed algorithms. We also test the methods on a large tree constructed from the Lichess database (Lichess 2026). Based on this experiment, we develop a classical-quantum hybrid algorithm that combines the strengths of classical and quantum MCTS algorithms. Finally, we implement a small experiment on IBM quantum hardware to demonstrate the feasibility of QMCTS. Our study is related to two strands of literature: Best Arm Identification. Best arm identification (BAI) is one of the most extensively studied problem in the bandit literature (Kaufmann et al. 2016, Garivier and Kaufmann 2016). In the fixed-confidence setting, instance-dependent lower bounds and matching algorithms have been established (Degenne et al. 2019, Wang et al. 2021c). Recent work has also explored the use of quantum computing to improve BAI. Casalé et al. (2020) first formulated quantum BAI based on amplitude amplification. Wang et al. (2021b) established a quadratic speedup in query complexity under a strong quantum oracle model. More recently, Wang et al. (2025) studied BAI under quantum oracle models with different query structures. Our work differs from quantum BAI in two ways. First, we consider MCTS, where the goal is to identify the optimal move at the root, whose value is determined recursively by the MAX-MIN tree. This tree structure creates additional challenges for both algorithm design and query-complexity analysis. Second, we establish a new query-complexity lower bound for adaptive quantum MCTS algorithms. The BAI lower bound follows as a special case by considering a depth-one tree. Monte Carlo Tree-Search. Many classical MCTS methods, including UCT, are built on regret-minimizing bandit algorithms (Kocsis and Szepesvári 2006), while we consider a fixed-confidence formulation. Kaufmann and Koolen (2017) studied fixed-confidence MCTS and developed BAI-based algorithms with instance-dependent guarantees. Our work instead studies how quantum computing can reduce the query complexity of MCTS. Research on quantum acceleration for MCTS and related tree-search methods remains limited. Peters (2021) applied quantum mean estimation to rollout values, while Sequeira et al. (2021) studied quantum Sparse Sampling with coherent access to environment transitions. Shukla (2026) constructed coherent rollout oracles to compare root actions through expected returns, and Finet et al. (2026) used a neutral-atom subroutine in the expansion step of MCTS. These methods do not directly address our setting, where the tree is fixed, uncertainty arises from stochastic leaf values, and root decisions are determined by recursive MAX-MIN backups rather than rollout expectations. We further provide a complete query-complexity analysis, with instance-dependent upper and lower bounds for identifying an ϵε-optimal root move. 2 Quantum Monte Carlo Tree Search In this section, we first introduce the basic notation and concepts of quantum computing, and then formulate fixed-confidence MCTS under the quantum oracle model. 2.1 Preliminaries on Quantum Computing Quantum computing exploits physical phenomena such as superposition, entanglement, and interference to process information. These mechanisms enable quantum parallelism and, when combined with suitable algorithmic procedures, can lead to significant speedups for certain computational tasks. We introduce the basic notation below and refer readers to (Nielsen and Chuang 2010) for a comprehensive treatment. In quantum computing, Dirac’s bra-ket notation is used to represent vectors and linear operations in a complex Hilbert space. A quantum state is represented by a ket |ψ⟩∈ℂd|ψ ^d, and the corresponding bra, denoted by ⟨ψ| ψ|, is defined as the conjugate transpose of the ket, i.e., ⟨ψ|=|ψ⟩† ψ|=|ψ . For two quantum states |ψ⟩|ψ and |ϕ⟩|φ , the quantity ⟨ϕ|ψ⟩ φ|ψ denotes their inner product, while |ψ⟩⟨ϕ||ψ φ| denotes their outer product and defines a linear operator. Quantum operations are represented by unitary operators U satisfying U†U=UU†=IU U=U =I, and their action on a quantum state is written as |ψ⟩↦U|ψ⟩|ψ U|ψ . The basic unit of information in quantum computing is a qubit (quantum bit). A classical bit takes one of two values, 00 or 11, while a qubit is described by the corresponding computational basis states |0⟩|0 and |1⟩|1 . Unlike a classical bit, a qubit can exist in a superposition of these basis states and is generally written as |ψ⟩=α|0⟩+β|1⟩,|ψ =α|0 +β|1 , where α,β∈ℂα,β are the corresponding probability amplitudes satisfying |α|2+|β|2=1|α|^2+|β|^2=1. Upon measurement, the qubit collapses to the state |0⟩|0 with probability |α|2|α|^2 and to the state |1⟩|1 with probability |β|2|β|^2, respectively. 2.2 Problem Formulation Consider a fixed game tree T with root node s0s_0. Each node is labeled as either MAX or MIN, with s0s_0 being a MAX node. For each node s, let (s)C(s) denote the set of its children. Let ℒL be the set of leaf nodes and L:=|ℒ|L:=|L|. Each leaf ℓ∈ℒ is associated with a stochastic oracle that represents the leaf evaluation when ℓ is reached by the MCTS algorithm. For ease of presentation, we consider Bernoulli leaf oracles with unknown means μℓ∈(0,1) _ ∈(0,1), where μℓ _ represents the probability that the first player wins the game from leaf ℓ . Let μ:=(μℓ)ℓ∈ℒ∈(0,1)Lμ:=( _ )_ ∈(0,1)^L denote the vector of leaf means. The proposed algorithms extend directly to leaf distributions supported on [0,1][0,1] (see Appendix 9.2 for details). The value of each node s (for the first player) is defined recursively as a function of μ Vs(μ)=μs,s∈ℒ,maxc∈(s)Vc(μ),s is a MAX node,minc∈(s)Vc(μ),s is a MIN node.V_s(μ)= cases _s,&s ,\\[1.99997pt] _c (s)V_c(μ),&s is a MAX node,\\[1.99997pt] _c (s)V_c(μ),&s is a MIN node. cases (1) We suppress the dependence on μ when it is clear from the context. The optimal root move is the child of s0s_0 with the highest value s⋆∈argmaxs∈(s0)Vs.s ∈ *arg\,max_s (s_0)V_s. (2) with ties resolved according to a fixed ordering. To identify s⋆s or an ϵε-optimal root move, an algorithm adaptively queries leaf nodes and observes their stochastic outcomes. After a random number τ of queries, the algorithm stops and recommends a move s^∈(s0) s (s_0). Given a confidence level δ∈(0,1)δ∈(0,1) and a precision parameter ϵ∈(0,1]ε∈(0,1], the objective is to identify a move in (s0)C(s_0) whose value is within ϵε of the optimal root value with probability at least 1−δ1-δ, i.e., ℙ(Vs0−Vs^≤ϵ)≥1−δ,P(V_s_0-V_ s≤ε)≥ 1-δ, while minimizing the total number of queries. We formally introduce the quantum oracle model in Definition 2.1. Definition 2.1 (Quantum oracle model) For each leaf ℓ∈ℒ with Bernoulli mean μℓ∈(0,1) _ ∈(0,1), we assume access to a unitary quantum oracle UℓU_ satisfying Uℓ|0⟩=1−μℓ|0⟩+μℓ|1⟩.U_ 0 = 1- _ \, 0 + _ \, 1 . (3) The algorithm may query UℓU_ or its inverse Uℓ†U_ , and each call is counted as one quantum query. The quantum oracle model UℓU_ is the counterpart of a classical stochastic simulator. If Uℓ|0⟩U_ |0 is measured immediately, the outcome is 11 with probability μℓ _ and 00 with probability 1−μℓ1- _ , which reproduces one classical Bernoulli sample from leaf ℓ . Before measurement, the quantum state can be processed coherently. We next introduce several quantities that characterize the difficulty of the tree-search problem and will be used in the query-complexity analysis. Define the root performance gap Δ⋆=Vs⋆−maxs∈(s0)∖s⋆Vs≥0, _ =V_s - _s (s_0) \s \V_s≥ 0, which measures the difference between the optimal root move and the best competing move. For an edge (s,c)(s,c) directed from a node s to its child c, define the local edge gap g(s,c)=|Vs−Vc|=Vs−Vc,s is a MAX node,Vc−Vs,s is a MIN node.g(s,c)=|V_s-V_c|= casesV_s-V_c,&s is a MAX node,\\ V_c-V_s,&s is a MIN node. cases For a leaf ℓ∈ℒ , let path(ℓ)path( ) denote the set of edges on the path from the root to ℓ , and define Δℓ=max(s,c)∈path(ℓ)g(s,c), _ = _(s,c) ( )g(s,c), which is the largest local edge gap along the path of ℓ . 3 Quantum Algorithm and Query Complexity Analysis In this section, we first develop the quantum MCTS algorithm and its classical counterpart. We then provide a complete query-complexity analysis to characterize the resulting quantum advantage. 3.1 Quantum algorithm design To develop an efficient quantum algorithm for MCTS, we consider three key issues: (a) using quantum methods to improve the accuracy of leaf-value evaluation; (b) designing the algorithm under the lazy-measurement principle; and (c) exploiting the tree structure to design an effective elimination rule. We first introduce the QMC estimator (Kothari and O’Donnell 2023) in Lemma 3.1 and use it as a basic subroutine of QMCTS for leaf-value estimation. Compared with classical Monte Carlo method, QMC achieves a quadratic improvement in the dependence on the target accuracy while preserving the same confidence guarantee. Lemma 3.1 For each leaf ℓ∈ℒ , there exists a quantum algorithm, denoted by QMC(Uℓ,α,η)QMC(U_ ,α,η), that uses O(1αlog1η)O( 1α 1η) queries to UℓU_ and returns an estimate μ^ℓ μ_ satisfying ℙ(|μ^ℓ−μℓ|>α)≤η.P ( | μ_ - _ |>α )≤η. However, naively replacing classical Monte Carlo estimates with QMC estimates is not sufficient to obtain a quantum speedup for tree search. The main difficulty comes from the restriction on information extraction in quantum computing. Classical sequential MCTS methods (Kaufmann and Koolen 2017) repeatedly use intermediate estimates to decide which nodes to sample or eliminate. In the quantum setting, obtaining such estimates requires measurement, which collapses the quantum state and may reduce the query advantage of QMC. On the other hand, delaying the elimination of clearly suboptimal moves can lead to many unnecessary queries. Therefore, a quantum MCTS algorithm needs to balance measurement frequency and adaptivity. We design the quantum algorithm following a lazy-measurement principle. The algorithm proceeds in iterations, and the quantum state is measured only at the end of each iteration to obtain updated estimates. At iteration r, we first estimate the value of each active leaf and then propagate these estimates upward through the tree. Specifically, define V^s,r=μ^s,r,s∈ℒr−1,maxc∈r−1(s)V^c,r,s is a MAX node,minc∈r−1(s)V^c,r,s is a MIN node, V_s,r= cases μ_s,r,&s _r-1,\\[3.00003pt] _c _r-1(s) V_c,r,&s is a MAX node,\\[5.0pt] _c _r-1(s) V_c,r,&s is a MIN node, cases (4) where ℒr−1L_r-1 is the set of active leaves and r−1(s)C_r-1(s) is the active children of node s at the beginning of iteration r. For an active edge (s,c)(s,c), define the empirical local gap by g^r(s,c)=V^s,r−V^c,r,s is a MAX node,V^c,r−V^s,r,s is a MIN node, g_r(s,c)= cases V_s,r- V_c,r,&s is a MAX node,\\[3.00003pt] V_c,r- V_s,r,&s is a MIN node, cases (5) which measures how far the child c is from the currently optimal child of node s. We use the geometrically decreasing threshold γr=2−r _r=2^-r to eliminate suboptimal nodes. In each iteration, the internal nodes are processed in reverse topological order. For each active internal node s, any child c satisfying g^r(s,c)>γr g_r(s,c)> _r is removed together with all of its descendants. The remaining nodes then form the active subtree rT_r, with active leaf set ℒrL_r. We set the QMC precision and confidence parameters to αr=γr/2 _r= _r/2 and ηr=δ/(2Lr2) _r=δ/(2Lr^2), respectively. These choices allow clearly suboptimal nodes to be eliminated in early iterations without excessive query costs, while ensuring that all estimates used by the algorithm are accurate with probability at least 1−δ1-δ (see Appendix 6 for details). This high-probability event is used to establish the correctness of the algorithm. After the elimination step, let s^r s_r denote the remaining root child with the largest estimated value. The algorithm stops when either only one root move remains or γr≤ϵ _r≤ε, and returns s^r s_r. We call this algorithm QMCTS and summarize it in Algorithm 1. Algorithm 1 Quantum Monte Carlo Tree Search (QMCTS) 1: Finite MAX–MIN tree T, accuracy ϵ∈(0,1]ε∈(0,1], and confidence δ∈(0,1/2)δ∈(0,1/2) 2: 0←T_0 and L←|ℒ|L←|L| 3: for r=1,2,…r=1,2,… do 4: γr←2−r _r← 2^-r, αr←γr/2 _r← _r/2, and ηr←δ/(2Lr2) _r←δ/(2Lr^2) 5: for all ℓ∈ℒr−1 _r-1 do 6: μ^ℓ,r←QMC(Uℓ,αr,ηr) μ_ ,r (U_ , _r, _r) 7: end for 8: Propagate V^s,r V_s,r upward using (4) 9: for all internal nodes s, in reverse topological order do 10: Remove each child c satisfying g^r(s,c)>γr g_r(s,c)> _r 11: end for 12: Let rT_r be the remaining connected subtree, with active leaf set ℒrL_r 13: s^r∈argmaxs∈r(s0)V^s,r s_r∈ *arg\,max_s _r(s_0) V_s,r 14: if |r(s0)|=1|C_r(s_0)|=1 or γr≤ϵ _r≤ε then 15: return s^r s_r 16: end if 17: end for For comparison, we also develop a classical counterpart of QMCTS, called CMCTS, summarized in Algorithm 2. CMCTS follows the same elimination framework as QMCTS. Its main advantage is that samples collected in previous iterations can be reused when updating the leaf estimates. At each iteration, given the same precision αr _r and confidence ηr _r, CMCTS uses Hoeffding’s inequality to determine the the number of additional samples required for each active leaf. This motivates a Hybrid MCTS method that uses classical estimates until a fresh QMC estimate becomes more query-efficient than further classical sampling for each leaf. Since the query cost for each leaf depends only on the precision and confidence parameters, this comparison can be made before querying the oracles (see Algorithm 3 for details). The hybrid method avoids costly quantum estimation during coarse elimination while retaining the quantum query advantage at high precision. Algorithm 2 Classical Monte Carlo Tree Search (CMCTS) 1: Finite MAX-MIN tree T, precision ϵ∈(0,1]ε∈(0,1], and confidence δ∈(0,1/2)δ∈(0,1/2) 2: 0←T_0 and L←|ℒ|L←|L| 3: Nℓ←0N_ ← 0 for every ℓ∈ℒ 4: for r=1,2,…r=1,2,… do 5: γr←2−r _r← 2^-r, αr←γr/2 _r← _r/2, and ηr←δ/(2Lr2) _r←δ/(2Lr^2) 6: nr←⌈log(2/ηr)/(2αr2)⌉n_r← (2/ _r)/(2 _r^2) 7: for all ℓ∈ℒr−1 _r-1 do 8: Δℓ←max0,nr−Nℓ _ ← \0,n_r-N_ \ 9: Query leaf ℓ for Δℓ _ additional observations and retain them 10: Nℓ←Nℓ+ΔℓN_ ← N_ + _ 11: Construct μ^ℓ,rC μ^C_ ,r as the empirical mean of all NℓN_ retained observations 12: end for 13: Propagate V^s,rC V^C_s,r upward using (4) 14: for all internal nodes s, in reverse topological order do 15: Remove each child c satisfying g^rC(s,c)>γr g^C_r(s,c)> _r 16: end for 17: Let rT_r be the remaining connected subtree, with active leaf set ℒrL_r 18: s^rC∈argmaxs∈r(s0)V^s,rC s^C_r∈ *arg\,max_s _r(s_0) V^C_s,r 19: if |r(s0)|=1|C_r(s_0)|=1 or γr≤ϵ _r≤ε then 20: return s^rC s^C_r 21: end if 22: end for 3.2 Query Complexity Analysis In this subsection, we analyze the query complexity of QMCTS and CMCTS. We first derive the upper bounds. For each leaf ℓ∈ℒ and iteration r≥1r≥ 1, define the bad estimation event Fℓ,r:=ℓ∈ℒr−1:|μ^ℓ,r−μℓ|>αr.F_ ,r:=\ _r-1:| μ_ ,r- _ |> _r\. If ℓ has already been eliminated, we set Fℓ,r=∅F_ ,r= . We then define the good event =⋂r≥1⋂ℓ∈ℒFℓ,rc,G= _r≥ 1 _ F^c_ ,r, under which every estimate used by the algorithm is within its prescribed precision αr _r. Lemma 3.2 shows that the good event holds with probability at least 1−δ1-δ. Lemma 3.2 The probability of the good event G is at least 1−δ1-δ, that is, ℙ(c)≤δ.P(G^c)≤δ. On the good event G, we can further establish two auxiliary results, as detailed in Appendix 6. These results show that the estimation error remains controlled as values are propagated up the tree, and that the elimination step removes only suboptimal nodes while preserving at least one optimal child at every node. Based on these results, Theorem 3.3 shows that QMCTS identifies an ϵε-optimal move with probability at least 1−δ1-δ. Theorem 3.3 With probability at least 1−δ1-δ, QMCTS stops after finitely many iterations and returns an ϵε-optimal move for s0s_0, i.e., ℙ(Vs0−Vs^≤ϵ)≥1−δ.P(V_s_0-V_ s≤ε)≥ 1-δ. Theorem 3.4 establishes an upper bound on the query complexity of QMCTS. Theorem 3.4 With probability at least 1−δ1-δ, the total number of quantum oracle queries used by QMCTS satisfies Q=O(∑ℓ∈ℒ1dℓ,ϵ[log2Lδ+2log(2+log21dℓ,ϵ)]), Q=O ( _ 1d_ ,ε [ 2Lδ+2 (2+ _2 1d_ ,ε ) ] ), (6) where dℓ,ϵ=Δℓ∨Δ⋆∨ϵ.d_ ,ε= _ _ ε. The query complexity is determined by the effective difficulty dℓ,ϵd_ ,ε of each leaf. QMCTS scales linearly with the inverse difficulty, up to logarithmic factors. We also establishes the correctness of CMCTS and derive its query-complexity upper bound; see Theorems 8.1 and 8.2 in Appendix 8. The classical query-complexity upper bound is O(∑ℓ∈ℒ1dℓ,ϵ2[log4Lδ+2log(2+log21dℓ,ϵ)]).O ( _ 1d_ ,ε^2 [ 4Lδ+2 (2+ _2 1d_ ,ε ) ] ). (7) Comparing (6) and (7), QMCTS improves the dependence on the effective difficulty dℓ,ϵd_ ,ε of each leaf from quadratic to linear. Thus, QMCTS achieves a quadratic speedup up to logarithmic factors. We now turn to the query-complexity lower bound. Classical lower-bound analyses often rely on change-of-measure arguments from sequential hypothesis testing. These arguments do not directly extend to the quantum setting, so we develop a quantum counterpart. Theorem 3.5 (Informal) Consider a problem instance μ for which the root decision depends on a collection of decision-relevant leaves. For any δ∈(0,1/4]δ∈(0,1/4], every adaptive quantum algorithm that identifies an ϵε-optimal root move with probability at least 1−δ1-δ requires μ[τ]=Ω(log1δ∑ℓ∈ℒpiv1dℓ,ϵ),E_μ[τ]= ( 1δ _ _piv 1d_ ,ε ), oracle queries. Here, ℒpivL_piv denotes the set of pivotal leaves; see Definition 7.2 in Appendix 7. The formal version of Theorem 3.5 is stated in Theorem 7.3 in Appendix 7, where we specify the structural conditions required for the lower-bound analysis. The lower bound depends only on pivotal leaves because, in a tree-search problem, not every leaf can affect the root decision. Hence, the query complexity is determined by the parts of the tree that matter for distinguishing the best move. The dependence on the inverse difficulty dℓ,ϵd_ ,ε is linear, which shows that the quadratic speedup for each pivotal leaf is optimal up to logarithmic factors. Corollary 7.4 in the Appendix shows that, for uniformly pivotal instances with ℒpiv=ℒL_piv=L, the upper and lower bounds match up to logarithmic factors. Thus, QMCTS is near-optimal in this case. This also highlights a structural difference between MCTS and BAI. In BAI, every arm can directly affect the final decision, which corresponds to the uniformly pivotal case. For a general MCTS problem instance, however, which leaves are pivotal is not known in advance. As a result, the algorithm may need to query leaves that eventually turn out to be nonpivotal. This extra cost comes from identifying the decision-relevant parts of the tree and makes the remaining gap between the upper and lower bounds difficult to close. Technical Novelty. We conclude this section by highlighting the main technical ingredients in the query-complexity analysis. For the upper bound, we use induction on the tree to establish the validity of the elimination step and combine this argument with the QMC error guarantee to obtain the query-complexity bound. For the lower bound, we exploit the tree structure and introduce pivotal leaf blocks to characterize how individual leaves affect the root decision. We also develop a new sequential quantum phase-testing result (see Appendix 7.1 for details) and reduce the MCTS identification problem to a collection of quantum phase-testing problems. This result is then used to derive the query-complexity lower bound and may be of independent interest for other quantum lower-bound analyses. 4 Numerical Experiment In this section, we conduct numerical experiments to evaluate QMCTS. We use synthetic experiments to verify the theoretical results, a large-scale chess experiment to access the scalability of the algorithm on a practical problem, and a real quantum computer experiment to examine the feasibility of implementing QMCTS on a quantum processor. 4.1 Synthetic Experiment We first examine how the query complexity scales with the inverse root gap 1/Δ⋆1/ _ and the inverse precision 1/ϵ1/ε. We consider a fixed depth-two MAX-MIN tree in which the MAX root has eight actions, each leading to a MIN node with two leaves, for a total of 25 nodes and 16 Bernoulli leaves. We set δ=0.05δ=0.05 and run 100 independent replications for each setting. As a classical benchmark, we include UGapE-MCTS (Kaufmann and Koolen 2017). In our implementation, QMCTS is simulated using standard quantum amplitude estimation as the QMC subroutine (Brassard et al. 2000). Figure 1 reports the mean query complexity as the problem difficulty increases. In all tested settings, all three algorithms terminate and return an ϵε-optimal root action with a 100% empirical success rate. Panel (a) varies the inverse root gap with ϵ=2−15ε=2^-15 fixed, while panel (b) varies the inverse precision with Δ⋆=2−15 _ =2^-15 fixed. The fitted log-log slopes are 0.960.96 and 0.950.95 for QMCTS, 2.022.02 and 2.012.01 for CMCTS, and 1.951.95 and 2.012.01 for UGapE-MCTS, respectively. Thus, QMCTS exhibits approximately linear scaling with the inverse gap and inverse precision, while both classical methods exhibit approximately quadratic scaling. These results are consistent with the theoretical analysis and support the quantum advantage over the classical benchmarks. Figure 1: Query Complexity Scaling with Gap and Precision 4.2 Large-Scale Chess Experiment We next evaluate the algorithms on a large search tree constructed from the Lichess database (Lichess 2026). Historical games that follow the same move sequence from the selected root position are merged into a common path in the tree. Each leaf represents games that reach the same terminal position in the constructed tree. From the root player’s perspective, wins, draws, and losses are assigned scores of 11, 1/21/2, and 00, respectively, and the leaf value is defined as the empirical mean score of the associated games. A leaf-oracle query returns an independent Bernoulli reward with this mean. The experiment can be viewed as an offline policy-improvement problem in which historical outcomes define the stochastic leaf rewards. We first compare QMCTS and CMCTS on a depth-1111 tree with 95099509 nodes, 30723072 leaves, and 10 root moves. The root performance gap is Δ⋆=0.0020503 _ =0.0020503. We set δ=0.05δ=0.05, vary ϵε, and run 100100 independent replications for each setting. On this large tree, pure QMCTS is less query-efficient when the inverse precision is small. In the early iterations, thousands of leaves remain active, so QMCTS repeatedly applies QMC to many leaves. In contrast, CMCTS requires only a small number of additional classical samples and reuses all previous observations. As a result, QMCTS incurs a large query cost before eliminating enough leaves. Figure 2: Large-scale chess query complexity. Figure 2 reports the mean query complexity in the large-scale chess experiment. All methods terminate and return an ϵε-optimal root action with a 100%100\% empirical success rate. Panel (a) shows that, at small inverse precision, CMCTS and Hybrid MCTS require substantially fewer queries than QMCTS. At 1/ϵ=321/ε=32, the mean query complexities are 30.6430.64 million for QMCTS, 7.507.50 million for CMCTS, and 7.377.37 million for Hybrid MCTS. As the inverse precision increases, the query cost of CMCTS grows rapidly, while QMCTS benefits from its better scaling. At 1/ϵ=10241/ε=1024, the corresponding query complexities are 35.0735.07, 47.1147.11, and 11.7111.71 million. Panel (b) reports the ratios relative to Hybrid MCTS. At 1/ϵ=10241/ε=1024, the QMCTS-to-Hybrid and CMCTS-to-Hybrid ratios are 2.9942.994 and 4.0224.022, respectively. These results show that Hybrid MCTS reduces the overall query cost by using classical sampling when the inverse precision is small and switching to quantum estimation as the inverse precision increases. 4.3 Real Experiment We further evaluate QMCTS on an IBM Quantum processor using Qiskit (Javadi-Abhari et al. 2024). We consider a depth-two MAX–MIN tree with two root moves and four Bernoulli leaves, with Δ⋆=0.01640625 _ =0.01640625, ϵ=2−6ε=2^-6, and δ=0.05δ=0.05. We run QMCTS and CMCTS independently five times. Both algorithms terminate and return the unique ϵε-optimal root move in all replications. The mean query complexities are 6835268352 for QMCTS and 306444306444 for CMCTS. Thus, CMCTS uses about 4.484.48 times more oracle queries, corresponding to a 77.70%77.70\% reduction for QMCTS. These results provide a small-scale hardware demonstration that QMCTS maintains correctness and a query-complexity advantage on a physical quantum processor. 5 Conclusion and Limitations In this paper, we study how quantum computing can improve MCTS. We develop a quantum algorithm, QMCTS, and establish its correctness and query-complexity guarantees. Numerical experiments show a clear query advantage over classical benchmarks. The main limitations are twofold. First, the gap between the upper and lower query-complexity bounds remains open for general tree instances, and we conjecture that closing this gap may be difficult because of the tree structure of the problem. Second, query complexity does not fully capture the gate complexity and implementation cost on real quantum hardware. Future work may extend the framework to more general tree-search models, including broader leaf-value distributions, stochastic transitions, and additional sources of uncertainty, and develop hardware-level complexity analyses that account for circuit depth and gate complexity. References Abbas et al. (2024) A. Abbas, A. Ambainis, B. Augustino, A. Bärtschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko, D. J. Egger, B. G. Elmegreen, et al. Challenges and opportunities in quantum optimization. Nature Reviews Physics 6 (12), p. 718–735. Cited by: §1. Beals et al. (2001) R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. De Wolf Quantum lower bounds by polynomials. Journal of the ACM (JACM) 48 (4), p. 778–797. Cited by: §7.1. Biamonte et al. (2017) J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd Quantum machine learning. Nature 549 (7671), p. 195–202. Cited by: §1. Borwein and Erdélyi (2012) P. Borwein and T. Erdélyi Polynomials and polynomial inequalities. Springer Science & Business Media. Cited by: §7.1. Brassard et al. (2000) G. Brassard, P. Hoyer, M. Mosca, and A. Tapp Quantum amplitude amplification and estimation. arXiv preprint quant-ph/0005055. Cited by: §4.1. Casalé et al. (2020) B. Casalé, G. Di Molfetta, H. Kadri, and L. Ralaivola Quantum bandits. Quantum Machine Intelligence 2 (1), p. 11. Cited by: §1. Degenne et al. (2019) R. Degenne, W. M. Koolen, and P. Ménard Non-asymptotic pure exploration by solving games. Advances in Neural Information Processing Systems 32. Cited by: §1. Finet et al. (2026) Y. Finet, Y. Bérubé-Lauzière, and V. Drouin-Touchette Quantum-enhanced monte carlo tree search framework for combinatorial optimization problems. arXiv preprint arXiv:2606.30415. Cited by: §1. Garivier and Kaufmann (2016) A. Garivier and E. Kaufmann Optimal best arm identification with fixed confidence. In Conference on Learning Theory, p. 998–1027. Cited by: §1. Hu et al. (2026) M. Hu, J. Hu, and E. Zhou Quantum grover adaptive search for discrete simulation optimization. arXiv preprint arXiv:2604.26277. Cited by: §1. Hu et al. (2025) M. Hu, J. Hu, and T. Wang Quantum ranking and selection under stochastic constraints. Note: Available at SSRN 5948136 Cited by: §1, §1. Javadi-Abhari et al. (2024) A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, et al. Quantum computing with qiskit. arXiv preprint arXiv:2405.08810. Cited by: §4.3. Kaufmann et al. (2016) E. Kaufmann, O. Cappé, and A. Garivier On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research 17 (1), p. 1–42. Cited by: §1. Kaufmann and Koolen (2017) E. Kaufmann and W. Koolen Monte-carlo tree search by best arm identification. Advances in Neural Information Processing Systems 30. Cited by: §1, §1, §3.1, §4.1. Kocsis and Szepesvári (2006) L. Kocsis and C. Szepesvári Bandit based monte-carlo planning. In European conference on machine learning, p. 282–293. Cited by: §1. Kothari and O’Donnell (2023) R. Kothari and R. O’Donnell Mean estimation when you have the source code; or, quantum monte carlo methods. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 1186–1215. Cited by: §3.1. Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári Bandit algorithms. Cambridge University Press. Cited by: 3rd item. Lichess (2026) Lichess Lichess open database. Note: https://database.lichess.org/ Cited by: 3rd item, §4.2. Mande and de Wolf (2026) N. S. Mande and R. de Wolf Tight bounds for quantum phase estimation and related problems. Quantum 10, p. 2140. Cited by: §7.1, §7.1. Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang Quantum computation and quantum information. Cambridge university press. Cited by: §2.1. Peters (2021) O. R. L. Peters Quantum speedups for monte carlo tree search. Master’s thesis, Leiden University. Cited by: §1. Sequeira et al. (2021) A. Sequeira, L. P. Santos, and L. S. Barbosa Quantum tree-based planning. IEEE Access 9, p. 125416–125427. Cited by: §1. Shah et al. (2022) D. Shah, Q. Xie, and Z. Xu Nonasymptotic analysis of monte carlo tree search. Operations research 70 (6), p. 3234–3260. Cited by: §1. Shukla (2026) N. Shukla Coherent rollout oracles for finite-horizon sequential decision problems. arXiv preprint arXiv:2604.25962. Cited by: §1. Silver et al. (2017a) D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815. Cited by: §1. Silver et al. (2017b) D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature 550 (7676), p. 354–359. Cited by: §1. Wang et al. (2021a) D. Wang, A. Sundaram, R. Kothari, A. Kapoor, and M. Roetteler Quantum algorithms for reinforcement learning with a generative model. In International Conference on Machine Learning, p. 10916–10926. Cited by: §1. Wang et al. (2021b) D. Wang, X. You, T. Li, and A. M. Childs Quantum exploration algorithms for multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, p. 10102–10110. Cited by: §1, §1. Wang et al. (2021c) P. Wang, R. Tzeng, and A. Proutiere Fast pure exploration via frank-wolfe. Advances in Neural Information Processing Systems 34, p. 5810–5821. Cited by: §1. Wang et al. (2025) X. Wang, Y. J. Chen, M. G. de Andrade, J. Allcock, M. Hajiesmaili, J. C. Lui, and D. Towsley Quantum best arm identification with quantum oracles. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, p. 21321–21329. Cited by: §1. Zhong et al. (2023) H. Zhong, J. Hu, Y. Xue, T. Li, and L. Wang Provably efficient exploration in quantum reinforcement learning with logarithmic worst-case regret. arXiv preprint arXiv:2302.10796. Cited by: §1. 6 Query Complexity Analysis Proof of Lemma 3.2. Let ℱr−1F_r-1 be the sigma-field generated by all operations and measurement outcomes before iteration r. Condition on ℱr−1F_r-1, according to the Lemma 3.1, the estimators satisfy ℙ(Fℓ,r|ℱr−1)≤(ℓ∈ℒr−1)ηr≤ηr.P(F_ ,r|F_r-1) ( _r-1) _r≤ _r. Therefore, a union bound gives ℙ(c)≤∑r≥1∑ℓ∈ℒηr=δ2∑r≥1∑ℓ∈ℒ1Lr2=π212δ<δ. (G^c)≤ _r≥ 1 _ _r= δ2 _r≥ 1 _ 1Lr^2= π^212δ<δ. For an active node before iteration r, let Vsr−1V^r-1_s be its true value computed on the active subtree r−1T_r-1. Lemma 6.1 On the good event G, for each iteration r and every node s active before iteration r, |V^s,r−Vs(r−1)|≤αr. | V_s,r-V_s^(r-1) |≤ _r. Fix an iteration r. We prove the claim by induction on the height of s in the active tree r−1T_r-1, where the height of a node is the maximum number of edges from that node to an active descendant leaf. For an active leaf ℓ∈ℒr−1 _r-1, we have V^ℓ,r=μ^ℓ,r, V_ ,r= μ_ ,r, and Vℓ(r−1)=μℓ.V_ ^(r-1)= _ . By the definition of the good event G, |V^ℓ,r−Vℓ(r−1)|≤αr. | V_ ,r-V_ ^(r-1) |≤ _r. Now consider an active internal node s. Assume that the claim holds for every active child c∈r−1(s)c _r-1(s). Suppose first that s is a MAX node. By the recursive definitions of the empirical and true values, V^s,r=maxc∈r−1(s)V^c,r,Vs(r−1)=maxc∈r−1(s)Vc(r−1). V_s,r= _c _r-1(s) V_c,r, V_s^(r-1)= _c _r-1(s)V_c^(r-1). The induction hypothesis implies that, for every active child c, Vc(r−1)−αr≤V^c,r≤Vc(r−1)+αr.V_c^(r-1)- _r≤ V_c,r≤ V_c^(r-1)+ _r. Taking the maximum over c∈r−1(s)c _r-1(s) yields Vs(r−1)−αr≤V^s,r≤Vs(r−1)+αr.V_s^(r-1)- _r≤ V_s,r≤ V_s^(r-1)+ _r. Therefore, |V^s,r−Vs(r−1)|≤αr. | V_s,r-V_s^(r-1) |≤ _r. If s is a MIN node, then V^s,r=minc∈r−1(s)V^c,r,Vs(r−1)=minc∈r−1(s)Vc(r−1). V_s,r= _c _r-1(s) V_c,r, V_s^(r-1)= _c _r-1(s)V_c^(r-1). Applying the same inequalities and taking the minimum gives Vs(r−1)−αr≤V^s,r≤Vs(r−1)+αr,V_s^(r-1)- _r≤ V_s,r≤ V_s^(r-1)+ _r, and thus |V^s,r−Vs(r−1)|≤αr. | V_s,r-V_s^(r-1) |≤ _r. By induction, the claim holds for every node active before iteration r. Lemma 6.2 On the good event G, every deleted child is strictly suboptimal for its parent in the active true tree. Moreover, at least one optimal child of every active internal node is retained. Consequently, after every iteration, Vs(r)=Vs(r−1)=VsV_s^(r)=V_s^(r-1)=V_s for every retained node s. We proceed by induction over the iterations. Before the first iteration, the active tree is the original tree, so the result holds. Fix iteration r and suppose that Vs(r−1)=VsV_s^(r-1)=V_s for every node active before this iteration. Consider first a MAX node s. If a child c is deleted, then V^s,r−V^c,r>γr. V_s,r- V_c,r> _r. By Lemma 6.1 and 2αr=γr2 _r= _r, Vs(r−1)−Vc(r−1) V_s^(r-1)-V_c^(r-1) ≥V^s,r−V^c,r−2αr>γr−2αr=0. ≥ V_s,r- V_c,r-2 _r> _r-2 _r=0. Hence, c is strictly suboptimal for s. Let c⋆c be an optimal child of s, so that Vc⋆(r−1)=Vs(r−1).V_c ^(r-1)=V_s^(r-1). Then V^s,r−V^c⋆,r≤2αr=γr, V_s,r- V_c ,r≤ 2 _r= _r, so c⋆c is not deleted. The argument for a MIN node is identical, with the inequalities reversed. Therefore, every active internal node retains at least one child attaining its true MAX or MIN value. Applying this argument from the deepest internal nodes toward the root, we have Vs(r)=Vs(r−1)=Vs.V_s^(r)=V_s^(r-1)=V_s. The conclusion follows by induction over r. 6.1 Proof of Theorem 3.3 Because γr=2−r _r=2^-r, we have γr→0 _r→ 0 as r→∞r→∞. Since ϵ>0ε>0, there exists a finite iteration Rϵ:=minr≥1:γr≤ϵ.R_ε:= \r≥ 1: _r≤ε \. The stopping condition of Algorithm 1 is satisfied no later than iteration RϵR_ε. Hence, the algorithm terminates after finitely many iterations. Condition on the good event G. By Lemma 6.2, threshold elimination preserves the true value of every retained node. Moreover, at least one optimal root move remains active after every iteration. Consequently, for every iteration r, there exists an active root move sr⋆∈r(s0)s_r _r(s_0) such that Vsr⋆=Vs0.V_s_r =V_s_0. Consider the two possible stopping conditions. First, suppose that |τ(s0)|=1. |C_τ(s_0) |=1. Since at least one optimal root move remains active, the unique remaining move must be optimal. Therefore, Vs0−Vs^=0≤ϵ.V_s_0-V_ s=0≤ε. Now suppose that the algorithm stops because γτ≤ϵ. _τ≤ε. The returned move satisfies s^∈argmaxs∈τ(s0)V^s,τ. s∈ *arg\,max_s _τ(s_0) V_s,τ. Let sτ⋆s_τ be an optimal active root move. Then V^s^,τ≥V^sτ⋆,τ. V_ s,τ≥ V_s_τ ,τ. By Lemma 6.1, and because the true values of retained nodes are preserved by Lemma 6.2, |V^s,τ−Vs|≤ατ | V_s,τ-V_s |≤ _τ for every root move s active at iteration τ. Hence, Vs0−Vs V_s_0-V_ s =Vsτ⋆−Vs =V_s_τ -V_ s =(Vsτ⋆−V^sτ⋆,τ)+(V^sτ⋆,τ−V^s^,τ)+(V^s^,τ−Vs^) = (V_s_τ - V_s_τ ,τ )+ ( V_s_τ ,τ- V_ s,τ )+ ( V_ s,τ-V_ s ) ≤ατ+0+ατ ≤ _τ+0+ _τ =2ατ =2 _τ ≤γτ ≤ _τ ≤ϵ. ≤ε. Thus, on the event G, the algorithm returns an ϵε-optimal root move. Since ℙ()≥1−δ,P(G)≥ 1-δ, we conclude that ℙ(Vs0−Vs^≤ϵ)≥ℙ()≥1−δ.P\! (V_s_0-V_ s≤ε ) (G)≥ 1-δ. 6.2 Proof of Theorem 3.4 We prove the query bound on the good event G. For each leaf ℓ∈ℒ , let RℓR_ denote the last iteration in which ℓ is queried. Suppose first that Rℓ≥2R_ ≥ 2. Since ℓ is queried in iteration RℓR_ , it must remain active after iteration Rℓ−1R_ -1 and iteration Rℓ−1R_ -1 is nonterminal. Consider any edge (s,c)(s,c) on the active path from the root to ℓ . Since this edge survives iteration Rℓ−1R_ -1, its empirical gap satisfies g^Rℓ−1(s,c)≤γRℓ−1. g_R_ -1(s,c)≤ _R_ -1. By Lemma 6.1 and Lemma 6.2 |V^u,Rℓ−1−Vu|≤αRℓ−1 | V_u,R_ -1-V_u |≤ _R_ -1 for every active node u. Therefore, g(s,c)≤g^Rℓ−1(s,c)+2αRℓ−1.g(s,c)≤ g_R_ -1(s,c)+2 _R_ -1. Since 2αr=γr2 _r= _r, it follows that g(s,c)≤2γRℓ−1.g(s,c)≤ 2 _R_ -1. Taking the maximum over all edges on the path to ℓ gives Δℓ≤2γRℓ−1. _ ≤ 2 _R_ -1. Because iteration Rℓ−1R_ -1 is nonterminal, we have ϵ<γRℓ−1≤2γRℓ−1.ε< _R_ -1≤ 2 _R_ -1. Furthermore, at least two root moves remain after iteration Rℓ−1R_ -1. By Lemma 6.2, at least one optimal root move remains active. Let s⋆s be such an optimal move and let s≠s⋆s≠ s be another active root move. Since the edge (s0,s)(s_0,s) has not been eliminated, Vs⋆−Vs≤2γRℓ−1.V_s -V_s≤ 2 _R_ -1. By the definition of the root gap, Δ⋆≤Vs⋆−Vs≤2γRℓ−1. _ ≤ V_s -V_s≤ 2 _R_ -1. Combining these inequalities yields dℓ,ϵ=Δℓ∨Δ⋆∨ϵ≤2γRℓ−1.d_ ,ε= _ _ ε≤ 2 _R_ -1. Since γr=2−r _r=2^-r, γRℓ−1=2γRℓ, _R_ -1=2 _R_ , and thus dℓ,ϵ≤4γRℓ.d_ ,ε≤ 4 _R_ . (8) Equivalently, 1γRℓ≤4dℓ,ϵ. 1 _R_ ≤ 4d_ ,ε. (9) If Rℓ=1R_ =1, then 1γRℓ=2≤4dℓ,ϵ, 1 _R_ =2≤ 4d_ ,ε, because dℓ,ϵ≤1d_ ,ε≤ 1. Hence, (9) holds for every leaf. Equation (8) also implies dℓ,ϵ≤4⋅2−Rℓ,d_ ,ε≤ 4· 2^-R_ , so Rℓ≤2+log21dℓ,ϵ.R_ ≤ 2+ _2 1d_ ,ε. (10) We now bound the queries allocated to leaf ℓ . In iteration r, according to Lemma 3.1, QMC uses at most CQαrlog1ηr C_Q _r 1 _r queries to UℓU_ and Uℓ†U_ , where CQ>0C_Q>0 is constant. Since αr=γr/2,ηr=δ/2Lr2, _r= _r/2, _r=δ/2Lr^2, the total query complexity associated with ℓ satisfies Qℓ Q_ ≤CQ∑r=1Rℓ1αrlog1ηr=2CQ∑r=1Rℓ1γr[log2Lδ+2logr]. ≤ C_Q _r=1^R_ 1 _r 1 _r=2C_Q _r=1^R_ 1 _r [ 2Lδ+2 r ]. Then, we have Qℓ Q_ ≤2CQ[log2Lδ+2logRℓ]∑r=1Rℓ1γr. ≤ 2C_Q [ 2Lδ+2 R_ ] _r=1^R_ 1 _r. Since γr=2−r _r=2^-r, ∑r=1Rℓ1γr=∑r=1Rℓ2r<2Rℓ+1=2γRℓ. _r=1^R_ 1 _r= _r=1^R_ 2^r<2^R_ +1= 2 _R_ . Consequently, Qℓ<4CQγRℓ[log2Lδ+2logRℓ].Q_ < 4C_Q _R_ [ 2Lδ+2 R_ ]. Applying (9) and (10) gives Qℓ≤16CQdℓ,ϵ[log2Lδ+2log(2+log21dℓ,ϵ)].Q_ ≤ 16C_Qd_ ,ε [ 2Lδ+2 (2+ _2 1d_ ,ε ) ]. Finally, every oracle query is associated with exactly one active leaf. Summing the preceding inequality over ℓ∈ℒ proves (6). 7 Query Complexity Lower Bound 7.1 Sequential Quantum Phase Hypothesis Testing In this subsection, we present the quantum-information-theoretic tool used in the lower-bound analysis. This is independent of the tree search problem and considers only a sequential hypothesis-testing problem for an unknown phase. Let Pθ=|0⟩⟨0|+eiθ|1⟩⟨1|,θ∈[−π,π),P_θ=|0 0|+e^iθ|1 1|, θ∈[-π,π), be a one-qubit phase oracle. Fix a θc _c and a measurable set Θ⊆[−π,π) [-π,π) containing θc _c. We consider the testing problem H0:θ=θcvsH1:θ∈[−π,π)∖Θ.H_0:θ= _c H_1:θ∈[-π,π) . The set Θ plays the role of an indifference region: when θ∈Θ∖θc,θ∈ \ _c\, the testing procedure is not required to make either decision correctly. The procedure must distinguish θc _c from every phase outside Θ . Let LebLeb denote the Lebesgue measure on ℝR (i.e., length). Define s:=Leb(Θ).s:=Leb( ). A smaller s places admissible alternatives closer to the reference phase and makes the two hypotheses harder to distinguish. For example, if Θ=[θc−h,θc+h], =[ _c-h, _c+h], then the test is required to distinguish θc _c from all phases satisfying |θ−θc|>h,|θ- _c|>h, and s=2hs=2h. Consider an arbitrary sequential quantum procedure. Between oracle queries, the procedure may apply arbitrary θ-independent quantum operations and measurements, and its subsequent operations may depend on previous measurement outcomes. The procedure may query PθP_θ, Pθ†P_θ and stops at a random time. Upon stopping, it outputs D∈0,1D∈\0,1\, where D=0D=0 corresponds to accepting H0H_0 and D=1D=1 corresponds to accepting H1H_1. For a prescribed error level ζ∈(0,1/4]ζ∈(0,1/4], we require ℙθc(D=1)≤ζP_ _c(D=1)≤ζ and supθ∉Θℙθ(D=0)≤ζ. _θ∉ P_θ(D=0)≤ζ. Let N denote the random number of phase-oracle queries made by the procedure before it stops. The quantity θc[N]E_ _c[N] is therefore the average number of phase-oracle queries used when the true phase is θc _c. Lemma 7.1 Under the testing set above, if s∈(0,π2],s∈(0, π2], then θc[N]≥116slog14ζ−12.E_ _c[N]≥ 116s 14ζ- 12. If ζ>1/4ζ>1/4, then 116slog14ζ−12<0, 116s 14ζ- 12<0, and the claimed bound follows immediately. For a fixed integer n≥0n≥ 0, define an(θ):=ℙθ(D=0,N≤n),a_n(θ):=P_θ(D=0,\;N≤ n), which is the acceptance probability of the test truncated after n queries. By the polynomial method for quantum phase queries, an(θ)a_n(θ) is a real trigonometric polynomial of degree at most 2n2n; see, e.g., Beals et al. (2001), Mande and de Wolf (2026). Moreover, for every θ∉Θθ∉ , an(θ)≤ℙθ(D=0)≤ζ.a_n(θ) _θ(D=0)≤ζ. Since the set Θ has total angular length s, a trigonometric Remez inequality gives an(θc)≤ζe8ns;a_n( _c)≤ζ e^8ns; see, e.g., Borwein and Erdélyi (2012), Mande and de Wolf (2026). Choose n=⌊18slog14ζ⌋.n= 18s 14ζ . Then ζe8ns≤14,ζ e^8ns≤ 14, and hence an(θc)≤14.a_n( _c)≤ 14. On the other hand, correctness under the null hypothesis implies ℙθc(D=0)≥1−ζ.P_ _c(D=0)≥ 1-ζ. Therefore, ℙθc(N>n) _ _c(N>n) ≥ℙθc(D=0,N>n) _ _c(D=0,\;N>n) =ℙθc(D=0)−an(θc) =P_ _c(D=0)-a_n( _c) ≥1−ζ−14 ≥ 1-ζ- 14 ≥12, ≥ 12, where the last inequality uses ζ≤1/4ζ≤ 1/4. Consequently, θc[N]≥nℙθc(N>n)≥n2.E_ _c[N]≥ n\,P_ _c(N>n)≥ n2. Finally, using ⌊x⌋≥x−1 x ≥ x-1, θc[N]≥116slog14ζ−12.E_ _c[N]≥ 116s 14ζ- 12. 7.2 Lower Bound Analysis In this subection, we reduce the quantum MCTS identification problem to a sequential quantum phase hypothesis-testing problem and use the Lemma 7.1 to derive the query complexity lower bound. For any leaf-mean vector ν∈(0,1)Lν∈(0,1)^L, define the set of ϵε-optimal moves at the root s0s_0 by ℳϵ(ν):=s∈(s0):Vs0(ν)−Vs(ν)≤ϵ.M_ε(ν):= \s (s_0):V_s_0(ν)-V_s(ν)≤ε \. (11) The reduction starts by considering a family of leaf-mean vectors μ~(θ),θ∈[−π,π), μ(θ),θ∈[-π,π), constructed so that, for some reference phase θc _c, μ~(θc)=μ. μ( _c)=μ. (12) If ℳϵ(μ)∩ℳϵ(μ~(θ))=∅,M_ε(μ) _ε ( μ(θ) )= , (13) then no root move is simultaneously a valid recommendation for the original instance and the perturbed instance. Therefore, any algorithm that is (ϵ,δ)(ε,δ)-correct on both instances must distinguish between them. Define Θ:=θ∈[−π,π):ℳϵ(μ)∩ℳϵ(μ~(θ))≠∅. := \θ∈[-π,π):M_ε(μ) _ε ( μ(θ) )≠ \. (14) At θ=θcθ= _c the instance is μ, while every θ∉Θθ∉ produces an instance whose valid root recommendations are disjoint from those of μ. Consequently, a correct tree-search algorithm can be used to test H0:θ=θcvsH1:θ∉Θ.H_0:θ= _c H_1:θ∉ . In the Monte Carlo tree search problem, changing the mean of a single leaf does not necessarily change the optimal move at the root, because its effect may be masked by the MAX–MIN operations along the path to the root. Therefore, we group leaf nodes into blocks in Definition 7.2 and consider joint perturbations of the leaves within each block, so that the perturbation can change the set of ϵε-optimal moves at the root. Definition 7.2 Fix a tree instance μ=(μℓ)ℓ∈ℒ,μ=( _ )_ , an accuracy level ϵ∈(0,1]ε∈(0,1], and a constant C>0C>0. A collection of nonempty leaf sets ℬ1,…,ℬm⊆ℒB_1,…,B_m is called a disjoint C-pivotal-block family at μ if the blocks are pairwise disjoint and there exists a common reference phase θc _c such that, for every block ℬjB_j, there exists a valid leaf-mean vectors μ(j)(θ)=(μℓ(j)(θ))ℓ∈ℒ,θ∈[−π,π),μ^(j)(θ)= (μ^(j)_ (θ) )_ , θ∈[-π,π), satisfying the following properties. 1. Under θc _c, the perturbed instance is exactly the original instance: μ(j)(θc)=μ.μ^(j)( _c)=μ. For an arbitrary phase θ, every leaf outside the block remains unchanged: μℓ(j)(θ)=μℓ,∀ℓ∉ℬj.μ^(j)_ (θ)= _ ,∀\, _j. Hence, when θ≠θcθ≠ _c, only the means of leaves in ℬjB_j are allowed to differ from those of the original instance. 2. For every ℓ∈ℬj _j, let Uℓ(j)(θ)U^(j)_ (θ) denote the quantum leaf oracle corresponding to the Bernoulli mean μℓ(j)(θ)μ^(j)_ (θ). One call to Uℓ(j)(θ)U^(j)_ (θ), its inverse, or a controlled version can be implemented using at most one call to PθP_θ, its inverse, or a controlled version, together with quantum operations independent of θ. 3. Define the decision-preserving region Θj:=θ∈[−π,π):ℳϵ(μ)∩ℳϵ(μ(j)(θ))≠∅, _j:= \θ∈[-π,π):M_ε(μ) _ε (μ^(j)(θ) )≠ \, and let dℬj:=minℓ∈ℬjdℓ,ϵ.d_B_j:= _ _jd_ ,ε. The perturbation family satisfies 0<Leb(Θj)≤minπ2,Cdℬj.0<Leb( _j)≤ \ π2,Cd_B_j \. Let ℒpiv:=⋃j=1mℬj,b:=max1≤j≤m|ℬj|.L_piv:= _j=1^mB_j, b:= _1≤ j≤ m|B_j|. For x∈ℝx , write [x]+:=maxx,0.[x]_+:= \x,0\. Theorem 7.3 Suppose that μ admits a disjoint C-pivotal-block family with C and b bounded by universal constants. For δ∈(0,1/4]δ∈(0,1/4], the total number of leaf-oracle queries τ satisfies μ[τ]=Ω(log1δ∑ℓ∈ℒpiv1dℓ,ϵ).E_μ[τ]= ( 1δ _ _piv 1d_ ,ε ). For each leaf ℓ , let NℓN_ denote the number of queries to its oracle before the algorithm stops. For block ℬjB_j, define Nj:=∑ℓ∈ℬjNℓ.N_j:= _ _jN_ . Fix one block ℬjB_j and run the tree algorithm on the family μ(j)(θ)μ^(j)(θ) from Definition 7.2. Convert its recommendation s s into a binary decision by setting Dj=0⟺s^∈ℳϵ(μ).D_j=0 s _ε(μ). At θ=θcθ= _c, (ϵ,δ)(ε,δ)-correctness gives ℙθc(Dj=1)≤δ.P_ _c(D_j=1)≤δ. For every θ∉Θjθ∉ _j, the sets ℳϵ(μ)M_ε(μ) and ℳϵ(μ(j)(θ))M_ε(μ^(j)(θ)) are disjoint. Therefore, whenever the algorithm is correct on the perturbed instance, its recommendation cannot belong to ℳϵ(μ)M_ε(μ), and supθ∉Θjℙθ(Dj=0)≤δ. _θ∉ _jP_θ(D_j=0)≤δ. Thus, the tree algorithm induces the phase test of Lemma 7.1. By Definition 7.2, the induced test can be simulated using no more than NjN_j phase-oracle queries. Therefore, Lemma 7.1 and Leb(Θj)≤CdℬjLeb( _j)≤ Cd_B_j imply μ[Nj]≥116Cdℬjlog14δ−12,E_μ[N_j]≥ 116Cd_B_j 14δ- 12, (15) whenever δ≤1/4δ≤ 1/4. If δ>1/4δ>1/4, then log14δ<0. 14δ<0. The theorem then follows immediately. Since dℬj=minℓ∈ℬjdℓ,ϵ,d_B_j= _ _jd_ ,ε, we have 1dℬj 1d_B_j =maxℓ∈ℬj1dℓ,ϵ≥1|ℬj|∑ℓ∈ℬj1dℓ,ϵ≥1b∑ℓ∈ℬj1dℓ,ϵ. = _ _j 1d_ ,ε≥ 1|B_j| _ _j 1d_ ,ε≥ 1b _ _j 1d_ ,ε. Hence, τ≥∑j=1mNj.τ≥ _j=1^mN_j. Taking expectations, summing (15) over the blocks, and applying the preceding inequality gives μ[τ]≥116bClog14δ∑ℓ∈ℒpiv1dℓ,ϵ−m2.E_μ[τ]≥ 116bC 14δ _ _piv 1d_ ,ε- m2. Define HQ(μ,ϵ):=∑ℓ∈ℒ1dℓ,ϵ.H_Q(μ,ε):= _ 1d_ ,ε. We call an tree instance uniformly pivotal if it admits a disjoint pivotal-block family that covers ℒL and whose perturbation constant C and maximum block size b are bounded by universal constants. We use O~ O to suppress logarithmic factors. Corollary 7.4 On every uniformly pivotal instance, any (ϵ,δ)(ε,δ)-correct quantum algorithm satisfies μ[τ]=Ω(HQ(μ,ϵ)log1δ),E_μ[τ]= (H_Q(μ,ε) 1δ ), whereas QMCTS uses O~(HQ(μ,ϵ)log1δ) O (H_Q(μ,ε) 1δ ) queries with probability at least 1−δ1-δ. Therefore, the expected lower bound and the high-probability upper bound have the same leading instance dependence up to logarithmic factors. Uniform pivotality gives ℒpiv=ℒL_piv=L with bounded block constants, so Theorem 7.3 yields the stated lower bound. Theorem 3.4 yields the upper bound. Exact identification, best arm identification, and general trees. Although QMCTS is presented for ϵ∈(0,1]ε∈(0,1], the formulation and lower-bound analysis also cover exact identification by setting ϵ=0ε=0, provided Δ⋆>0 _ >0. For a depth-one MAX tree, this reduces to fixed-confidence exact BAI, while ϵ∈(0,1]ε∈(0,1] reduces to fixed-confidence ϵε-BAI. Thus, BAI is a special case of the tree-search problem studied here. 8 Classical MCTS Benchmark Theorem 8.1 With probability at least 1−δ1-δ, CMCTS stops after finitely many iterations and returns an ϵε-optimal root move for s0s_0, i.e., ℙ(Vs0−Vs^C≤ϵ)≥1−δ.P (V_s_0-V_ s^C≤ε )≥ 1-δ. For each leaf ℓ , let Xℓ,1,Xℓ,2,…X_ ,1,X_ ,2,… be an i.i.d. sequence of Bernoulli observations with mean μℓ _ . For n≥1n≥ 1, define X¯ℓ,n:=1n∑k=1nXℓ,k. X_ ,n:= 1n _k=1^nX_ ,k. Define the classical good event C:=⋂r≥1⋂ℓ∈ℒ|X¯ℓ,nr−μℓ|≤αr.G_C:= _r≥ 1 _ \ | X_ ,n_r- _ |≤ _r \. By Hoeffding’s inequality and the definition of nrn_r, ℙ(|X¯ℓ,nr−μℓ|>αr)≤2exp(−2nrαr2)≤ηr.P ( | X_ ,n_r- _ |> _r )≤ 2 (-2n_r _r^2)≤ _r. Consequently, ℙ(Cc)≤∑r≥1∑ℓ∈ℒηr=δ2∑r≥11r2<δ.P(G_C^c)≤ _r≥ 1 _ _r= δ2 _r≥ 1 1r^2<δ. Condition on CG_C. Every active classical leaf estimate has error at most αr _r. The proofs of Lemmas 6.1 and 6.2 therefore apply with μ^ℓ,rC μ^C_ ,r and V^s,rC V^C_s,r in place of their quantum counterparts. Because γr=2−r _r=2^-r and ϵ>0ε>0, CMCTS stops no later than the first iteration r for which γr≤ϵ _r≤ε. If it stops with only one root move remaining, that move is optimal. Otherwise, let sr⋆s_r be an active optimal root move. Since CMCTS returns the active root move with the largest propagated estimate, Vs0−Vs^C V_s_0-V_ s^C ≤|Vsr⋆−V^sr⋆,rC|+|V^s^C,rC−Vs^C|≤2αr=γr≤ϵ. ≤ |V_s_r - V^C_s_r ,r |+ | V^C_ s^C,r-V_ s^C |≤ 2 _r= _r≤ε. Since ℙ(C)≥1−δP(G_C)≥ 1-δ, the result follows. Theorem 8.2 With probability at least 1−δ1-δ, the total number of leaf-oracle queries used by CMCTS is O(∑ℓ∈ℒ1dℓ,ϵ2[log4Lδ+2log(2+log21dℓ,ϵ)]),O ( _ 1d_ ,ε^2 [ 4Lδ+2 (2+ _2 1d_ ,ε ) ] ), (16) where dℓ,ϵ=Δℓ∨Δ⋆∨ϵ.d_ ,ε= _ _ ε. Condition on the classical good event CG_C, and let RℓR_ be the final iteration in which leaf ℓ is queried. The arguments in the proof of Theorem 3.4 give 1γRℓ≤4dℓ,ϵ,Rℓ≤2+log21dℓ,ϵ. 1 _R_ ≤ 4d_ ,ε, R_ ≤ 2+ _2 1d_ ,ε. (17) Using αr=γr2,ηr=δ2Lr2, _r= _r2, _r= δ2Lr^2, we obtain nRℓ n_R_ ≤1+12αRℓ2log2ηRℓ=1+2γRℓ2[log4Lδ+2logRℓ]. ≤ 1+ 12 _R_ ^2 2 _R_ =1+ 2 _R_ ^2 [ 4Lδ+2 R_ ]. Applying (17) yields nRℓ≤1+32dℓ,ϵ2[log4Lδ+2log(2+log21dℓ,ϵ)].n_R_ ≤ 1+ 32d_ ,ε^2 [ 4Lδ+2 (2+ _2 1d_ ,ε ) ]. Summing over all leaves proves (16). Finally, ℙ(C)≥1−δ,P(G_C)≥ 1-δ, so the bound holds with probability at least 1−δ1-δ. 9 Quantum Algorithm Design 9.1 Hybrid Algorithm In this subsection, we provide implementation details for the Hybrid MCTS algorithm. Algorithm 3 Hybrid Monte Carlo Tree Search (Hybrid MCTS) 1: Finite MAX–MIN tree T, accuracy ϵ∈(0,1]ε∈(0,1], and confidence δ∈(0,1/2)δ∈(0,1/2) 2: 0←T_0 and L←|ℒ|L←|L| 3: Nℓ←0N_ ← 0 for every ℓ∈ℒ 4: n0←0n_0← 0 and r←1r← 1 ⊳ Classical phase 5: while true do 6: γr←2−r _r← 2^-r, αr←γr/2 _r← _r/2, and ηr←δ/(2Lr2) _r←δ/(2Lr^2) 7: nr←⌈log(2/ηr)/(2αr2)⌉n_r← (2/ _r)/(2 _r^2) 8: if a fresh QMC estimate with parameters αr _r and ηr _r uses fewer than nr−nr−1n_r-n_r-1 queries then 9: break 10: end if 11: for all ℓ∈ℒr−1 _r-1 do 12: Δℓ←max0,nr−Nℓ _ ← \0,n_r-N_ \ 13: Query leaf ℓ for Δℓ _ additional observations and retain them 14: Nℓ←Nℓ+ΔℓN_ ← N_ + _ 15: Construct μ^ℓ,r μ_ ,r as the empirical mean of all NℓN_ retained observations 16: end for 17: Propagate V^s,r V_s,r upward using (4) 18: for all internal nodes s, in reverse topological order do 19: Remove each child c satisfying g^r(s,c)>γr g_r(s,c)> _r 20: end for 21: Let rT_r be the remaining connected subtree, with active leaf set ℒrL_r 22: s^r∈argmaxs∈r(s0)V^s,r s_r∈ *arg\,max_s _r(s_0) V_s,r 23: if |r(s0)|=1|C_r(s_0)|=1 or γr≤ϵ _r≤ε then 24: return s^r s_r 25: end if 26: r←r+1r← r+1 27: end while⊳ Quantum phase 28: while true do 29: γr←2−r _r← 2^-r, αr←γr/2 _r← _r/2, and ηr←δ/(2Lr2) _r←δ/(2Lr^2) 30: for all ℓ∈ℒr−1 _r-1 do 31: μ^ℓ,r←QMC(Uℓ,αr,ηr) μ_ ,r (U_ , _r, _r) 32: end for 33: Propagate V^s,r V_s,r upward (4) 34: for all internal nodes s, in reverse topological order do 35: Remove each child c satisfying g^r(s,c)>γr g_r(s,c)> _r 36: end for 37: Let rT_r be the remaining connected subtree, with active leaf set ℒrL_r 38: s^r∈argmaxs∈r(s0)V^s,r s_r∈ *arg\,max_s _r(s_0) V_s,r 39: if |r(s0)|=1|C_r(s_0)|=1 or γr≤ϵ _r≤ε then 40: return s^r s_r 41: end if 42: r←r+1r← r+1 43: end while 9.2 Query Complexity under Different Leaf Distributions In this section, we provide additional numerical results to show that our algorithms also apply to more general leaf distributions. We consider two additional distributional settings in the synthetic experiment. The first is a bounded three-point distribution supported on 00, 1/21/2 and 11, with probabilities chosen to match the mean in the Bernoulli setting. The second is a bounded five-point discrete distribution with equally spaced support points chosen to preserve the same mean. All other experimental settings remain unchanged. As shown in Figures 3 and 4, the results are consistent with those obtained under Bernoulli distributions, which suggests that our methods are robust to the choice of output distribution. Figure 3: Query Complexity Scaling under A Bounded Three-point Distribution Figure 4: Query Complexity Scaling under A Bounded Five-point Discrete Uniform Distribution