acceptodds
Under review as a conference paper at ICLR 2027

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.

Primary area:
reinforcement learning
Keywords:
Quantum Computing, Monte Carlo Tree Search, Query Complexity, Fixed-confidence

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ypeEOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates quantum acceleration of Monte Carlo Tree Search (MCTS) in the fixed-confidence setting, where the goal is to identify an ϵ\epsilon-optimal root action in a MAX–MIN game tree with stochastic leaf rewards. The authors propose Quantum MCTS (QMCTS), which combines quantum mean estimation with a threshold-based subtree elimination procedure. They establish a high-probability correctness guarantee and derive an instance-dependent query-complexity upper bound, improving the dependence on the inverse leaf difficulty from quadratic to linear compared with a classical counterpart, up to logarithmic factors. The paper further develops an instance-dependent lower bound for adaptive quantum algorithms using a sequential quantum phase-testing argument and shows that the upper and lower bounds match up to logarithmic factors under additional structural assumptions on the tree. Finally, synthetic experiments, a chess-derived search tree, and a small-scale quantum hardware demonstration are presented to support the theoretical findings.

Critical strengths
  • Instance-dependent theoretical guarantees. The paper provides a rigorous fixed-confidence analysis of quantum MCTS, establishing correctness and an instance-dependent query-complexity upper bound that explicitly accounts for the MAX–MIN tree structure. The resulting improvement from quadratic to linear dependence on the inverse effective leaf difficulty provides a theoretical characterization of the potential quantum advantage in tree-structured decision problems.

  • Quantum query-complexity lower-bound analysis. The paper develops a lower-bound framework based on sequential quantum phase testing and pivotal leaf blocks. Under additional structural assumptions, the lower bound matches the proposed algorithm's upper bound up to logarithmic factors. Although the result is restricted to a particular class of tree instances, it provides theoretical insight into the fundamental query complexity of quantum tree search and represents a potentially valuable contribution beyond the algorithm itself.

Critical weaknesses
  • Limited algorithmic novelty. The proposed QMCTS algorithm largely follows an existing elimination-based MCTS framework, with classical mean estimation replaced by established quantum mean estimation techniques. The threshold-based elimination procedure, MAX–MIN value propagation, and instance-dependent difficulty measures are closely related to prior work on fixed-confidence MCTS (e.g., Kaufmann & Koolen, 2017). Consequently, the quadratic improvement in query complexity appears to follow primarily from the known advantage of quantum mean estimation rather than a fundamentally new tree-search strategy. This substantially limits the paper's algorithmic contribution.

  • Limited generality of the lower-bound results. Although the paper establishes an instance-dependent quantum query-complexity lower bound, the result relies on restrictive structural assumptions involving disjoint pivotal leaf blocks. The matching upper and lower bounds are established only for uniformly pivotal instances, and the paper does not sufficiently characterize how broadly these assumptions apply to general MAX–MIN trees. Moreover, the sequential quantum phase-testing argument builds on existing polynomial-method techniques. These limitations weaken the significance of the claimed near-optimality guarantees and leave the main theoretical contribution less compelling.

Questions for authors

See the weakness part.

1 comment

Thank you for your time and careful review of our work. We hope the following clarifications help address your questions.

Novelty in QMCTS

The quadratic speedup of quantum mean estimation is well known, but this advantage does not automatically translate into a query-complexity improvement for tree search. For example, the MCTS algorithms of Kaufmann and Koolen (2017) update the tree after each leaf sample to select the next leaf. Measuring the quantum state after each oracle call would destroy the coherence needed for quantum speedup. Therefore, directly replacing classical sampling with quantum mean estimation does not preserve this advantage.

We identify successive elimination as a suitable framework for infrequent measurement and design QMCTS to defer tree updates until quantum estimates are available. We further develop the error allocation, elimination rule, and stopping condition to ensure fixed-confidence correctness and preserve the quantum advantage at the root. Beyond the algorithm design, we prove that QMCTS matches the expected query-complexity lower bound up to logarithmic factors on uniformly pivotal instances, which specifies the conditions for its optimality.

Generality of the Lower Bound

We respectfully disagree that the structural conditions weaken the contribution of the lower bound. A key novelty of our analysis is that we exploit the MAX–MIN tree structure to identify pivotal blocks of leaves whose joint perturbations can change the root decision. The lower bound does not require every leaf to be pivotal. Full coverage by disjoint pivotal blocks is only a sufficient condition for matching the upper and lower bounds up to logarithmic factors. Appendix B.3 verifies this condition for two explicit tree families at depths one and two. For general MAX–MIN trees, we conjecture that matching upper and lower bounds may not be possible, as additional queries may be needed to learn the leaf means. This query gap reflects a fundamental challenge of MCTS rather than a limitation of the lower-bound analysis.

The main contribution of our lower-bound analysis is a new framework for deriving expected query lower bounds for fixed-confidence quantum tree search. Existing lower-bound analyses in the quantum bandit literature (Wang et al. 2021, 2025) consider deterministic query budgets and do not directly apply to algorithms with adaptive stopping times. Our analysis proceeds in three steps. First, we reduce the fixed-confidence QMCTS problem to phase testing. Second, we apply the polynomial method of Mande and de Wolf (2026) to establish a fixed-query lower bound. Third, we develop a stopping-time argument to extend this result to expected query complexity for adaptive quantum algorithms whose stopping times depend on their observations. This framework may also be useful for establishing lower bounds in other fixed-confidence quantum problems. Thus, our main contribution lies in the analytical framework. Similarly, classical bandit lower-bound analyses often rely on standard hypothesis-testing tools, such as the Bretagnolle–Huber inequality, while their contributions lie in the analytical frameworks developed to establish new lower bounds.

Reviewer_BnUgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies fixed-confidence Monte Carlo tree search in the model of Kaufmann & Koolen (2017). The goal is to return an ϵ\epsilon-optimal root move with probability at least 1−δ1-\delta using few leaf queries on MAX–MIN tree . The proposed QMCTS runs phased elimination with thresholds 2−r2^{-r}. In each round it re-estimates every active leaf by quantum mean estimation, propagates the estimates up the tree, and prunes children whose empirical gap is too large. The paper proves an upper bound of order ∑ℓ1/dℓ\sum_\ell 1/d_\ell (up to logarithms) and the classical analogue needs ∑ℓ1/dℓ2\sum_\ell 1/d_\ell^2. It also proves a lower bound of order log⁡(1/δ)∑ℓ pivotal1/dℓ\log(1/\delta)\sum_{\ell\ \mathrm{pivotal}}1/d_\ell from a sequential phase-testing lemma. Experiments cover a synthetic tree, a chess tree built from Lichess games, and a four-leaf instance on IBM hardware.

Critical strengths
  • As far as I can tell, this is the first instance-dependent analysis of quantum tree search with minimax backups. Earlier quantum MCTS work speeds up rollout estimation or sparse sampling, but it does not study fixed-confidence identification on a MAX–MIN tree. The paper is easy to follow, the algorithm is simple.

  • QMCTS measures only at the end of each round, and the threshold halves from one round to the next. Restarting quantum estimation therefore costs only a constant factor, because each leaf's cost is a geometric sum dominated by its last round. This technique seems to explain why elimination keeps the quadratic gain in the quantum setting.

  • Classical fixed-confidence lower bounds rely on change of measure, which has no direct quantum analogue. Lemma 5 bounds the expected number of phase queries of procedures that stop adaptively and measure in between, with the log⁡(1/ζ)\log(1/\zeta) factor.

Critical weaknesses
  • QMCTS is successive elimination with standard quantum mean estimation. The quadratic gain is what quantum mean estimation typically gives and this part is not novel.

  • Lemma 5 is close to the phase-estimation lower bound of Mande & de Wolf, Ω((1/s)log⁡(1/ζ))\Omega((1/s)\log(1/\zeta)), which is also proved with trigonometric polynomials. Allowing a random stopping time adds a short Markov-type step. Calling it a new tool of independent interest overstates its novelty.

  • The lower bound rests on conditions that are never shown to hold. Definition 2 is not checked on any concrete instance. Each perturbed leaf oracle uses one phase query, so each perturbed leaf mean has the form a+bcos⁡(θ+φ)a+b\cos(\theta+\varphi). For a two-armed instance, the set of phases on which the original answer stays valid is then an arc of length at least 22d2\sqrt{2d}. Condition 3 (Leb(Θj)≤Cd\mathrm{Leb}(\Theta_j)\le Cd) therefore fails for small gaps, whatever the blocks are. So Theorem 4 says nothing about the simplest best-arm case, although the introduction states that the BAI lower bound follows as a special case. It is also unclear which trees are uniformly pivotal, for example the 8×2 tree of Section 4.1. As a result, the near-optimality claim of Corollary 1 has no verified instance.

Questions for authors
  1. Apart from the expected stopping time, what does Lemma 5 add to Mande & de Wolf?
  2. Many chess leaves have means close to 0 or 1. Quantum mean estimation is cheaper there because its cost scales with the standard deviation. Would a variance-aware estimator change the 1/dℓ1/d_\ell dependence, and how would the lower bound change? 3- Can authors clarify the concern about the lower bounds above?
3 comments

We appreciate your thoughtful feedback and valuable suggestions. We provide further explanations below to clarify the key points raised in your review.

Novelty in QMCTS

The quadratic speedup of quantum mean estimation is well known, but this estimation advantage does not directly translate into a query-complexity improvement for optimization problems. A key challenge is that extracting information from quantum states requires measurement, which destroys the coherence needed for quantum speedup. Therefore, directly combining classical MCTS algorithms with quantum mean estimation does not automatically preserve this advantage. We find that successive elimination provides a framework that satisfies the principle of infrequent measurement in quantum algorithm design. We design QMCTS based on successive elimination to defer tree updates until quantum estimates are available. We further develop its error allocation, elimination rule, and stopping condition to ensure fixed-confidence correctness and preserve the quantum advantage. We also prove that QMCTS matches the query-complexity lower bound up to logarithmic factors for a class of uniformly pivotal instances, which specifies the conditions for its optimality.

Concerns About the Lower Bound

We strengthened the lower-bound analysis in Appendix B by replacing the full-circle construction with an interval of perturbations that satisfy Definition 1. In Appendix B.3, we provide two concrete tree examples at depths one and two and verify that both satisfy the revised conditions. The depth-one family includes two-arm best-arm identification with arbitrarily small gaps, which was not covered by the original analysis. We also clarify that an instance is uniformly pivotal if a collection of disjoint blocks satisfying the conditions of Theorem 4 covers all leaves. Both tree families in Appendix B.3 satisfy this condition, and their upper and lower bounds in Corollary 1 match up to logarithmic factors.

Technical Novelty in Lower Bound

The main contribution of our lower-bound analysis is a new framework for deriving expected query lower bounds for fixed-confidence quantum tree search. Existing lower-bound analyses in the quantum bandit literature (Wang et al. 2021, 2025) consider fixed query budgets and do not directly apply to algorithms with adaptive stopping times. Our analysis proceeds in three steps. First, we reduce the fixed-confidence QMCTS problem to phase testing. Second, we apply the polynomial method of Mande and de Wolf (2026) to establish a fixed-query lower bound. Third, we develop a stopping-time argument to extend this result to expected query complexity for adaptive quantum algorithms whose stopping times depend on their observations. This framework may also be useful for establishing lower bounds in other fixed-confidence quantum problems. Thus, our main contribution lies in the analytical framework rather than the individual mathematical tools. Similarly, classical bandit lower-bound analyses often rely on standard hypothesis-testing tools, such as the Bretagnolle–Huber inequality, while their contributions lie in the analytical frameworks developed to establish new lower bounds.

[1] Daochen Wang, Xuchen You, Tongyang Li, and Andrew M. Childs. 2021. Quantum Exploration Algorithms for Multi-Armed Bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 35(11), 10102–10110. AAAI

[2] Xuchuang Wang, Yu-Zhen Janice Chen, Matheus Guedes de Andrade, Jonathan Allcock, Mohammad Hajiesmaili, John C. S. Lui, and Don Towsley. 2025. Quantum Best Arm Identification with Quantum Oracles. Proceedings of the AAAI Conference on Artificial Intelligence, 39(20), 21321–21329. AAAI

Variance-aware Estimator Our upper bound already covers leaf means close to 0 or 1. We use 1/2 as a uniform upper bound on the Bernoulli standard deviation, so the stated dependence on dℓ,ϵd_{\ell,\epsilon} remains valid. A variance-aware estimator could provide a tighter upper bound for low-variance leaves. The lower bound also retains its stated dependence on dℓ,ϵd_{\ell,\epsilon} whenever the conditions of Theorem 4 hold.

I thank the authors for their response.

I agree that the existing framework does not lead to the result in the paper in a straightforward way and I find the application to be novel.

However, most of these techniques are well known. The authors used these tools in a nontrivial way (especially the lower bound) to apply in their analysis. I find this a useful contribution, yet I am doubtful about the paper's impact for the broader community. That is, the speedup is quadratic which is typical for such problems. The problem (hence the modified techniques) are a bit niche so that it is hard for me to imagine other people using it for different problems. For this reason, I'll maintain my score.

We thank the reviewer for their response and for recognizing the technical contributions of our work.

The quadratic speedup of quantum Monte Carlo estimation is well known. However, extending this speedup from estimation to optimization is not straightforward. In MCTS, both our upper and lower bounds depend on the tree structure, and the bounds do not match for certain tree structures. These results reveal new theoretical properties of quantum tree search beyond the standard quadratic speedup in estimation.

As quantum computing continues to develop, understanding the theoretical limits of quantum speedups for different classes of problems becomes increasingly important. Our lower-bound analysis can handle adaptive quantum algorithms that determine their queries and stopping times based on observations. This framework has the potential to support complexity analysis for a broader class of quantum stochastic decision problems, including bandits and reinforcement learning.

We have also demonstrated the effectiveness of our method through practical applications. We hope these points help clarify the broader theoretical significance and potential impact of our work.

Reviewer_9TSoOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The goal of this paper is to study fixed-confidence identification of a near-optimal root "move" in a fixed max-min tree with unknown stochastic leaf values. An easy example can help understand what this paper is about. Suppose for simplicity that the tree is binary and it has depth 3. So, there are 8 leaves at the bottom and assume that the values of the leaves are mu(l) \in (0,1). Recursively, we start in depth 3 defining, V(l) = mu(l) for the 8 leaf nodes is equal to mu_(l) and if p is a node in depth 2 of the tree we compute V(p) = max_{c \in C(p)}{V(c)} = max_{c \in C(p)}{mu(c)}, where C(p) is the set of children of the node p. Then, at depth 1 we compute V(e) = min_{c \in C(e)}{V(c)} and, finally, at the root we compute V(root) = max_{c \in C(root)}{V(c)}. So, this is a big iterated non-linear function of expectations, in particular for my example this would be

V(root) = max { min { max( mu_1, mu_2), max( mu_3, mu_4) }, min{ max( mu_5, mu_6), max( mu_7, mu_8) } }.

Then, let's say c* \in C(root) is optimal (i.e. c* \in argmax { V(c) : c \in C(root)}. We want to find a decision (i.e. a child c in C(root)) so that V(c) has a suboptimality gap with respect to V(c*) not larger than epsilon with probability at least 1-delta. The child "c" is a random outcome resulting from the algorithm.

We want to have P(V(c*) - V(c) <= eps) >= 1-delta, the convention is that the root always starts maximizing by assumption.

The paper offers an "instance-dependent" upper bound (meaning depending on gap between leave mean values and V values along the recursion, but that's hard to track as a primitive). When considering the worst case of the leave values collapses to \tilde O (L/eps) where L is the number of leaves. This offers a quadratic speed up in eps (and the instance-dependent gaps) as well relative to a natural classical algorithm.

Critical strengths

See above, already indicated: The paper offers an "instance-dependent" upper bound (meaning depending on gap between leave mean values and V values along the recursion, but that's hard to track as a primitive). When considering the worst case of the leave values collapses to \tilde O (L/eps) where L is the number of leaves. This offers a quadratic speed up in eps (and the instance-dependent gaps) as well relative to a natural classical algorithm.

On the side of the experiments, which are appreciated, the authors are able to identify when quantum estimation helps and when classical sample reuse is preferable. On the Lichess-drived tree, pure QMCTS is more expensive at coarse precision.

Critical weaknesses
  1. The lower-bound construction is not justified in the stated oracle model. Definition 2 requires phase-dependent leaf oracles that seem at odds with the exact state preparation given in Definition 1. This makes the matching lower bound argument and the near optimality incomplete.

  2. Results our Teraoke et al. (2014) "Efficient Sampling Method for Monte Carlo Tree Search Problem" seem very closely related and not discussed in the reference.

  3. Results by Sun et al (2026) "Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation" on nonlinear quantum Monte Carlo also appear related, but the techniques and the results here are different, in principle the value estimation problem offers the indication of a near quadratic speedup even when the mean rewards are unbounded.

  4. I don't see why the rewards need to be bounded, this feels quite artificial.

Questions for authors
  1. What new argument is required to get the QMCTS upper bound beyond combining the tree-pruning methods of Teraoka et al?
  2. Can you provide a non-constant perturbation family satisfying Def. 2 under the exact oracle model of Dec. 1?
  3. Provide enough information about the IBM infrastructure used and how the experiment was run to allow reproducibility of Section 4.3.
  4. On Theorem 4, I think there is an issue with the bound involving log(1/4delta)), the lower bound obtained in equation (15) doesn't say anything useful if delta = 1/4, but then below there is an argument about adding in blocks, which need more details.
  5. There is a small discrepancy in Cor. 1 in that the lower bound involves expected query count and the upper bound is a high probability bound, can you please address this?
2 comments

Thank you for taking the time to review our paper and for your thoughtful comments. I hope the following clarifications address your concerns.

Related Work

Thank you for pointing out these papers. We have added both references to the related work subsection and clarified how they differ from our work. Teraoka et al. (2014) study the fixed-confidence MCTS under classical computing, while Sun et al. (2026) use quantum mean estimation to evaluate nested conditional expectations. Neither work addresses our problem of identifying an ϵ\epsilon-optimal root move in a MAX--MIN tree with fixed confidence using quantum computing.

Bounded Reward

Bernoulli rewards arise naturally in win/loss games, where the mean reward at each leaf represents the probability of winning from that position. This model has also been adopted in classical MCTS by Teraoka et al. (2014) and Kaufmann and Koolen (2017).

The Bernoulli assumption also plays a role in our theoretical analysis. Specifically, we establish the lower bound by constructing hard instances with Bernoulli leaf oracles. Bernoulli rewards are also commonly used in lower-bound analyses in the classical bandit literature (e.g., Mannor and Tsitsiklis, 2004).

Our tree search method can also be extended to unbounded rewards with finite variance. We can use the quantum mean estimator of Kothari and O'Donnell (2023) with a suitable query budget to achieve the required accuracy and confidence at each leaf. Establishing a matching lower bound under these more general assumptions remains challenging.

[1] Kazuki Teraoka, Kohei Hatano, and Eiji Takimoto. “Efficient Sampling Method for Monte Carlo Tree Search Problem.” IEICE Transactions on Information and Systems, E97-D(3), 392–398, 2014.

[2] Emilie Kaufmann and Wouter M. Koolen. “Monte-Carlo Tree Search by Best Arm Identification.” Advances in Neural Information Processing Systems, 30, 4898–4907, 2017.

[3] Shie Mannor and John N. Tsitsiklis. “The Sample Complexity of Exploration in the Multi-Armed Bandit Problem.” Journal of Machine Learning Research, 5, 623–648, 2004.

[4] Robin Kothari and Ryan O’Donnell. “Mean Estimation When You Have the Source Code; or, Quantum Monte Carlo Methods.” Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1186–1215, 2023.

Additional Details on the Hardware Experiment We have expanded Appendix D.3 to provide further details on the IBM quantum hardware setup and explain how the hardware measurements were used to estimate leaf values in QMCTS.

Expected Query Complexity Upper Bound The high-probability query-complexity bound in Theorem 2 follows the convention in classical fixed-confidence MCTS (Teraoka et al. 2014; Kaufmann and Koolen 2017). In our setting, an upper bound on the expected number of queries can also be obtained through a further analysis by setting the confidence parameter to δˉ=δϵ\bar{\delta}=\delta\epsilon, which allows us to control the contribution of the failure event to the expected query count. This adjustment adds log⁡(1/ϵ)\log(1/\epsilon) to the logarithmic confidence factor in the query bound. We have included this expected query-complexity bound in Appendix A.3 of the revised manuscript.

New argument beyond Teraoka et al(2014)

Teraoka et al. (2014) update each leaf estimate using all the classical samples collected for that leaf so far. To use the same update with a quantum oracle, we would have to measure the output of each oracle call to obtain a classical sample. Measuring after each call destroys the quantum coherence that quantum Monte Carlo (QMC) needs for its speedup.

QMCTS follows a lazy-measurement principle. In each iteration, we obtain a fresh QMC estimate for each active leaf before updating node values and pruning the tree. We allocate the failure probability across leaves and iterations so that, with probability at least 1−δ1-\delta, every estimate used in the search meets its target accuracy. This allocation keeps the confidence term logarithmic in the iteration index.

In Teraoka et al. (2014), the sample count for a leaf in its final iteration already includes all samples collected earlier. For QMCTS, we must account for the queries used by each fresh estimate. Appendix A.2 uses the tree gaps and the stopping rule to bound the final iteration in which each leaf is queried. Since the target error halves at each iteration, the sum of the query budgets for all estimates at a leaf is at most a constant multiple of the budget for its final iteration. This carries the quadratic improvement in the dependence on leaf difficulty over to the full tree search, up to logarithmic factors.

Justification of the Lower Bound

We justify the lower-bound construction in Appendix B.2 by showing how the query-complexity analysis under the stated oracle model in Definition 1 reduces to a quantum phase testing problem. Every oracle used in the reduction satisfies the model’s exact state-preparation requirement of Definition 1. In Appendix B.3, we provide two concrete tree examples, one at depth one and one at depth two, and verify that each admits a nonconstant perturbation family that satisfies Definition 2. We also verify that both examples satisfy the conditions required for the lower bound. This confirms that the lower bound applies to both tree families under the stated oracle model.

A Technical Issue in Theorem 4

We strengthened the proof in Appendix B.1 to replace the factor log⁡(1/(4δ))\log(1/(4\delta)) with log⁡(1/δ)\log(1/\delta), so the lower bound remains nontrivial at δ=1/4\delta=1/4. In Appendix B.2, we sum the per-block lower bounds because the blocks are disjoint and their expected query counts, evaluated on the same reference tree, sum to at most the total expected query count.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.