# Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems

arXiv: https://arxiv.org/abs/2604.25962 · HTML: https://mlsanity.com/paper/2604.25962/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2026.

## Built on by (most cited first, 1 of 1)

- [Quantum Monte Carlo Tree Search with Fixed Confidence](https://mlsanity.com/paper/2609.33132/) (2026)

## Abstract (arXiv)

Coherent quantum rollout for sequential decision problems requires a unitary simulator: randomness must live in explicit quantum registers, and basis-state selectors must be mapped to actions reversibly. With branch-dependent valid actions, this mapping is totalized coherent rank-select over an entangled N-bit validity mask: return the position of the r-th valid bit, or a sentinel if r is out of range. We give the first reversible-circuit complexity analysis of this primitive. For selector width w = lceil log2(N+1) rceil, rank-select admits an O(Nw)-gate low-ancilla bounded-span scan, proved gate-optimal in its model, and an O(Nlog w)-gate low-ancilla blocked construction when long-range gates are available; across all bounded-fan-in layouts, the unconditional gate lower bound is Omega(N). Composing rank-select with reversible transition and predicate-evaluation circuits gives an explicit polynomial-size coherent rollout oracle for finite-horizon planning problems satisfying these primitive assumptions. The resulting oracle satisfies the access model of the best-arm pipeline of Wang et al., yielding widetildeO(√k/varepsilon) coherent oracle calls against the standard classical Omega(k/varepsilon2) arm-pull lower bound. We give a bounded-influence lifting theorem that extends this lower-bound construction from a base configuration to an exponential family of configurations. We instantiate the construction on SIR epidemic intervention, with a stochastic placement-game sanity check, and machine-check the main results in Lean 4. Code and proofs: https://github.com/BinRoot/b01t/tree/main/demos/rollout.