How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games

Title: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 $\epsilon$ with \[ O\!\left( K^{D}\, deg^{\frac{D}{4}} \, \frac{N}{\epsilon} \, D^{4D} \log\left( \frac{deg N}{\epsilon} \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}\epsilon^{-1})$ against the classical $\widetilde O(deg^{m}\epsilon^{-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.

F.2.2; F.1.2; I.2.8

arXiv:2609.35511 [quant-ph]

(or arXiv:2609.35511v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.35511 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.