arXiv:2610.03026 · Physical Review Letters
Spatiotemporal quantum advantages for rare-event sampling
Akshat Gupta, Jianjun Chen, Chengran Yang, Mile Gu, Caterina Doglioni, Jayne Thompson, Thomas J. Elliott
Abstract
In a world fraught with uncertainty, it behooves us to consider the most disastrous possible outcomes, in order that we can best mitigate against them. Often these are extreme risk events -- of high consequence, but low probability. Yet, the rarity of such events limits our ability to study them; there is a paucity of past occurrences to draw upon, and sampling such rare events from models is typically costly in time. Here, we introduce an approach for rare-event sampling based on quantum stochastic models. This integrates the memory advantages of quantum stochastic modelling -- and its associated efficient means of preparing quantum sample states -- with the `speed-ups' of quantum amplitude amplification, to yield simultaneous reductions in spatial and temporal computational complexity compared to classical Monte Carlo-based approaches.
AI Summary
The paper asks whether quantum stochastic models can support rare-event trajectory sampling with simultaneous memory and runtime reductions relative to classical rejection-based Monte Carlo. It combines quantum hidden Markov models (QHMMs) with quantum amplitude amplification, using coherent model evolution to prepare trajectory superpositions and its inverse to implement the amplification reflections. For a length-$L$ trajectory, memory dimension $d$, and output alphabet $\mathcal X$, the recurrent construction prepares the sample state with depth $O(Ld^2|\mathcal X|^2)$. An event of probability $p$ can then be sampled using $O(p^{-1/2})$ amplification iterations, compared with $O(p^{-1})$ trajectories for classical rejection sampling. Including the stated reflection costs gives depth $O([Ld^2|\mathcal X|^2+(\log_2d+L\log_2|\mathcal X|)^2]/\sqrt p)$. Memory compression applies to the model register; storing outputs still requires $L\log_2|\mathcal X|$ qubits. The paper also derives probability-estimation query complexity $O(p^{-1/2}\delta^{-2})$ for relative accuracy $\delta$. The construction is illustrated numerically on two toy processes. A modified Nemo process uses quantum memory dimension two versus three classical states; for events of probability around $10^{-6}$, 1,024 amplification iterations yield 8,796 target samples in 10,000 shots. A renewal-process example uses one memory qubit versus 25 classical states and amplifies an event with $p\approx2.445\times10^{-15}$ to probability approximately $0.992$ after $2^{24}$ iterations. Extensions cover arbitrary QHMMs through coherent Kraus dilations. Retaining dilation ancillas can reduce the spatial advantage, and very rare events still require deep circuits. Circuit recompilation and extensions to input-output processes are left for future work.
Central claim may not hold: The claimed temporal advantage is established over rejection sampling, not classical rare-event methods generally, and both toy examples admit direct classical conditional sampling that avoids the asserted O(1/p) rejection cost. The definition R₀ = I − |0⟩⟨0| is a nonunitary projector rather than the required reflection and must be corrected to I − 2|0⟩⟨0|.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 8+3 pages, 3+5 figures