Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This work establishes a quantum algorithm for evaluating two-player stochastic game trees (expectiminimax) across alternating adversarial and chance layers. Solving a longstanding composition hurdle where error propagation typically degrades nested quantum speedups, the framework proves that quantum acceleration across deterministic and stochastic nodes can be tightly combined. For constant depth $D=2m$, the algorithm evaluates the game to $\epsilon$-precision in $\widetilde O(deg^{m/2}\epsilon^{-1})$ queries compared to the classical $\widetilde O(deg^{m}\epsilon^{-2})$, simultaneously preserving quadratic advantages in both branching factor and error tolerance.
Quadratic quantum speedups for minimax search and Monte Carlo expectation don't destroy each other when nested: stochastic game trees can be solved with simultaneous quadratic reductions in both branching factor and precision error.
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.