{"id":"arxiv/2609.35511","url":"https://arxiv.org/abs/2609.35511","tags":["quant-ph"],"score":0,"title":"How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games","domain":"quant-ph","source":"arxiv","authors":["Marien Raat","Merlin Incerti-Medici","James R. Wootton","Evert van Nieuwenburg","Daniel Bultrini"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}