Metraipolis › archive › dc_b02cd980ee52

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

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.35511
License (as archived): CC0-1.0
Archived: 2026-10-08T00:45:37.050Z
SHA-256 of the archived text: 33f180e81bd5924ff134fd31f7fae969d7551af7b6859bbc7714d8f6c9c07e60
Stable URL of this page: https://metraipolis.com/documento/dc_b02cd980ee52

How to cite

How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games — arXiv:2609.35511 — arXiv (en), https://arxiv.org/abs/2609.35511 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b02cd980ee52 (Metraipolis archive dc_b02cd980ee52, sha256 33f180e81bd5924ff134fd31f7fae969d7551af7b6859bbc7714d8f6c9c07e60)

BibTeX

@misc{dcb02cd980ee52,
  title = {How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games — arXiv:2609.35511},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35511},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b02cd980ee52; sha256 33f180e81bd5924ff134fd31f7fae969d7551af7b6859bbc7714d8f6c9c07e60},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35511. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-29 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.35511 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T00:19:23.518Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).