How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games
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 ( KD degD/4 N/ε D4D log( (deg N)/ε )4D ), 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 Õ(degm/2ε−1) against the classical Õ(degmε−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.
Related
- Quantum algorithm for high-dimensional nonlinear stochastic differential equations based on Carleman linearization
- Improved estimate of local Markovianity for quantum Gibbs states
- Model Fractional Quantum Hall States on Lattices: Exact Parent Hamiltonians and Routes to Realization
- What does quantum parameter estimation estimate? A no-go result for true quantity values
- Kitaev, semi-Dirac, and spinon quantum spin Hall liquids on the square-hexagon-dodecagon lattice: A parent projective symmetry group classification
BibTeX
@misc{raat2026fast,
title = {{How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games}},
author = {Marien Raat and Merlin Incerti-Medici and James R. Wootton and Evert van Nieuwenburg and Daniel Bultrini},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35511},
eprint = {2609.35511},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35511},
}
RIS
TY - UNPB
TI - How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games
AU - Marien Raat
AU - Merlin Incerti-Medici
AU - James R. Wootton
AU - Evert van Nieuwenburg
AU - Daniel Bultrini
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35511
UR - https://arxiv.org/abs/2609.35511
AB - 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 ( K^D deg^D/4 N/ε D^4D log( (deg N)/ε )^4D ), 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 Õ(deg^m/2ε^−1) against the classical Õ(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.
ER -