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

arXiv:2609.35511 · quant-ph · Submitted 2026-09-28 · Read on arXiv

quant-ph

Submitted: 2026-09-28

Updated: 2026-09-28

Project page: https://yassine-hamoudi.github.io/files/other/PhDthesis

Terminology

• Accuracy — 16× in this paper · explained in 1 episode
• Query Complexity — 14× in this paper · explained in 2 episodes
• Pruning — 5× in this paper · explained in 4 episodes
• Sample Complexity — 3× in this paper · explained in 15 episodes
• Alternation — 1× in this paper · explained in 1 episode
• Annual ACM Symposium on Theory of Computing — 1× in this paper
• Annual ACM-SIAM Symposium on Discrete Algorithms — 1× in this paper
• Annual Symposium on Foundations of Computer Science — 1× in this paper
• Core — 1× in this paper · explained in 2 episodes

Sources

• Quantum Algorithms for Evaluating MIN-MAX Trees
• A lower bound on the quantum query complexity of read-once functions
• Mean estimation when you have the source code; or, quantum Monte Carlo methods
• Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation
• Quantum speedup of non-linear Monte Carlo problems
• Quantum Search on Bounded-Error Inputs
• Discrete-query quantum algorithm for NAND trees
• Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
• Faster quantum algorithm for evaluating game trees
• Quantum Amplitude Amplification and Estimation
• Quantum speedup of Monte Carlo methods
• Quantum walk speedup of backtracking algorithms
• Fast Amplification of QMA
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Quantum Approximate $k$-Minimum Finding
• The quantum query complexity of approximating the median and related statistics
• Negative weights make adversaries stronger
• Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
• Fixed-point quantum search with an optimal number of queries

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity