arXiv:2609.35511
How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games
Marien Raat, Merlin Incerti-Medici, James R. Wootton, Evert van Nieuwenburg, Daniel Bultrini
Abstract
We give a quantum algorithm for stochastic $2$-player games. Their game trees are the expectiminimax trees of classical game search: $m$ adversarial layers alternate with $m$ chance layers, every node has $deg$ children, and the leaf values lie in an interval of length $N$. The algorithm estimates the value of the game to root mean square error $ε$ with \[ O\!\left( K^{D}\, deg^{\frac{D}{4}} \, \frac{N}ε \, D^{4D} \log\left( \frac{deg N}ε \right)^{4D} \right), \qquad D = 2m \] queries to the leaf values, where $K$ is an absolute constant. If we treat the depth $D$ as a constant as is sometimes done in the literature, the bound is $\widetilde O(deg^{m/2}ε^{-1})$ against the classical $\widetilde O(deg^{m}ε^{-2})$. So the quadratic speedup in the branching factor known for adversarial trees and the quadratic speedup in the accuracy known for a single expectation both survive when we nest one inside the other. We use a derandomised multilevel Monte Carlo estimator for chance layers and a coherent binary search for adversarial layers. The composition is done by introducing a conversion between root-mean-square and uniform error guarantees, and a composition to nest it with quantum mean estimation. We state the algorithm for stochastic games, but it is valid for the following conditions: the value of a parent is a Lipschitz function of the values of its children and the value at a chance vertex is linear in its children, however the speedup is preserved only if the deterministic step has a quantum subroutine with sublinear query complexity.
AI Summary
The paper studies quantum query complexity for approximately evaluating expectiminimax trees, where adversarial max/min layers alternate with chance layers. The input is a leaf-value oracle; the goal is to estimate the root value with root-mean-square error $\epsilon$. For depth $D=2m$, branching factor at most $b$, and leaf values in an interval of length $N$, it gives a bound of $O(K^D b^{D/4}(N/\epsilon)D^{4D}\log^{4D}(bN/\epsilon))$, with absolute constant $K$. At constant depth and normalized range, this is $\widetilde O(b^{m/2}\epsilon^{-1})$, compared with a classical multilevel baseline of $\widetilde O(b^m\epsilon^{-2})$. The classical product bound is not proved optimal. The construction combines derandomized multilevel quantum mean estimation at chance nodes with coherent binary search and amplitude amplification at adversarial nodes. Reversible median boosting converts child RMSE guarantees into high-probability accuracy guarantees, avoiding a $\sqrt b$ error amplification at extrema. Telescoping level differences prevents repeated chance layers from multiplying inverse-accuracy costs. An abstract formulation also covers linear chance transitions and deterministic transitions admitting suitable coherent subroutines. A composed adversary argument gives $\Omega(b^{(m-1)/2}\epsilon^{-1})$ for $1/(4b)\leq\epsilon\leq1/8$ and $m\geq2$, leaving a $\sqrt b$ gap apart from logarithmic factors. The gap grows at finer accuracy. Depth-dependent overheads restrict the branching-factor advantage to very wide, shallow trees; the stated constants preclude practical game-search gains. Other stated open problems include adaptive composition, matching product lower bounds, and bounded-memory implementations.
Error found: The main theorem omits degree-dependent logarithmic overhead that its deterministic routine explicitly incurs, although the abstract's larger logarithm accommodates it. The general theorem miscounts transitions by one and consequently gives a false degree-independent bound for a final maximum or minimum step. The stochastic-games pseudocode recurses at the same depth instead of constructing the next-depth estimator at accuracy ε/8. The appendix incorrectly telescopes independently prepared random outputs samplewise and treats mean-estimation targets as random quantities, while the main-text proof sketch correctly telescopes expectations.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 32 pages, 3 algorithms