Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

quant-phcond-mat.stat-mechSubmitted Oct 2, 2026• Announced Oct 5, 2026• 1 citation
arXivHTMLPDF

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.

Little sign of AI-generated textIncrementalOverclaimsMissing comparison

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

Related papers

Quantum enhanced rare event discovery and sampling

Naixu Guo, Po-Wei Huang, Qisheng Wang +4 more

Financial crashes, cascading failures in infrastructure, and critical errors in AI systems are frequently triggered by events that occur with extremely small probability. Efficiently discovering and sampling events with probability below a threshold is therefore of critical interest. Yet this task is highly non-trivial using existing classical or quantum methods. Being rare, such events require an immense sampling overhead to collect sufficient data samples. Moreover, because the rare events are not known in advance, they cannot be flagged for amplification using standard techniques. Here, we introduce a quantum algorithm for rare-event discovery and sampling without first learning which events are rare. The algorithm achieves the optimal quantum scaling with the rarity threshold. We further demonstrate that this can achieve a quadratic speedup for heavy-tailed systems whose tail has nonvanishing total mass, and translates into a robust polynomial speedup for stationary stochastic processes, with the exponent determined by its entropy-rate structure.

quant-pharXiv:2606.06316•Jun 5, 2026•5 citations

Quantum-Enhanced Inference of Conditional Future Probabilities with Reduced Memory Cost

Jianjun Chen, Akshat Gupta, Chengran Yang +4 more

Many potential future events have devastating consequences, from the onset of earthquakes to financial black swan events. Accurate predictions of their probability of occurrence are vital. Yet as the stochastic systems underlying such events become increasingly complex, these probabilities can depend on ever-growing amounts of past data, which require ever more memory to track. The accuracy of our estimates is ultimately limited by both computational and memory constraints; the former to reduce sampling error, the latter to avoid sampling bias. Traditional quantum algorithms -- such as amplitude estimation -- address only the former, and become untenable especially in near-future quantum devices where quantum memory is a premium. Here, we offer quantum-algorithmic means to reduce systematic bias while maintaining a quadratic speed-up. Our results thus advance the timeline for the practical deployment of quantum technologies, and illustrate their additional benefits when simulating processes of growing complexity.

quant-pharXiv:2610.10756•Quantum Science and Technology•Oct 9, 2026•0 citations

Dimension reduction in quantum sampling of stochastic processes

Chengran Yang, M. Florido-Llinas, Mile Gu +1 more

Abstract Quantum technologies offer a promising route to the efficient sampling and analysis of stochastic processes, with potential applications across the sciences. Such quantum advantages rely on the preparation of a quantum sample state of the stochastic process, which requires a memory system to propagate correlations between the past and future of the process. Here, we introduce a method of lossy quantum dimension reduction that allows this memory to be compressed, not just beyond classical limits, but also beyond current state-of-the-art quantum stochastic sampling approaches. We investigate the trade-off between the saving in memory resources from this compression, and the distortion it introduces. We show that our approach can be highly effective in low distortion compression of both Markovian and strongly non-Markovian processes alike. We further discuss the application of our results to quantum stochastic modelling more broadly.

arXiv:2404.10338•npj Quantum Information•Feb 28, 2025•5 citations

Quantum Coarse Graining for Extreme Dimension Reduction in Modeling Stochastic Temporal Dynamics

Thomas J. Elliott

Stochastic modeling of complex systems plays an essential, yet often computationally intensive, role across the quantitative sciences.Recent advances in quantum information processing have elucidated the potential for quantum simulators to exhibit memory advantages for such tasks.Heretofore, the focus has been on lossless memory compression, wherein the advantage is typically in terms of lessening the amount of information tracked by the model, while-arguably more practical-reductions in memory dimension are not always possible.Here, we address the case of lossy compression for quantum stochastic modeling of continuous-time processes, introducing a method for coarse graining in quantum state space that drastically reduces the requisite memory dimension for modeling temporal dynamics while retaining near-exact statistics.In contrast to classical coarse graining, this compression is not based on sacrificing temporal resolution and brings memory-efficient high-fidelity stochastic modeling within reach of present quantum technologies.

arXiv:2105.06831•PRX Quantum•Jun 16, 2021•11 citations

Implementing quantum dimensionality reduction for non-Markovian stochastic simulation

Kang‐Da Wu, Chengran Yang, Ren-Dong He +5 more

Complex systems are embedded in our everyday experience. Stochastic modelling enables us to understand and predict the behaviour of such systems, cementing its utility across the quantitative sciences. Accurate models of highly non-Markovian processes - where the future behaviour depends on events that happened far in the past - must track copious amounts of information about past observations, requiring high-dimensional memories. Quantum technologies can ameliorate this cost, allowing models of the same processes with lower memory dimension than corresponding classical models. Here we implement such memory-efficient quantum models for a family of non-Markovian processes using a photonic setup. We show that with a single qubit of memory our implemented quantum models can attain higher precision than possible with any classical model of the same memory dimension. This heralds a key step towards applying quantum technologies in complex systems modelling.

arXiv:2208.12744•Nature Communications•May 6, 2023•16 citations

Sample-Based Quantum Diagonalization with Amplitude Amplification

Nina Stockinger, Ludwig Nützel, Michael J. Hartmann

Recently, sample-based quantum diagonalization (SQD) has emerged as a promising approach to compute ground and excited states of problem Hamiltonians.This method classically diagonalizes a Hamiltonian in a subspace that is spanned by samples obtained from a quantum computer. However, by its nature, SQD suffers from a fundamental sampling problem, as some basis states that are required for a targeted accuracy may only be sampled extremely rarely. To alleviate this limitation, we introduce the SQD-AA algorithm that combines SQD with amplitude amplification (AA). SQD-AA uses AA to sequentially reduce probabilities of already measured bitstrings, thus making the observation of new ones more likely. We observe a reduction in the total query complexity of more than a factor 100 for algebraically and exponentially decaying model distributions, and analytically show a quadratic advantage for the latter. Moreover, we evaluate real molecules in an early fault-tolerant scenario and compare SQD-AA to SQD and iterative quantum phase estimation (iQPE). For all considered examples, we observe the lowest total number of T-gates for SQD-AA while only requiring circuits that are 3-4 orders of magnitude shallower than those needed for iQPE. Given this substantial reduction in circuit depth compared to iQPE while saving 2 orders of magnitude in total runtime compared to SQD, we expect a significant regime in early fault-tolerance where SQD-AA runs feasibly, but iQPE circuits are too deep to execute confidently.

quant-pharXiv:2605.02565•May 5, 2026•3 citations
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.
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-LLL trajectory, memory dimension ddd, and output alphabet X\mathcal XX, the recurrent construction prepares the sample state with depth O(Ld2∣X∣2)O(Ld^2|\mathcal X|^2)O(Ld2∣X∣2). An event of probability ppp can then be sampled using O(p−1/2)O(p^{-1/2})O(p−1/2) amplification iterations, compared with O(p−1)O(p^{-1})O(p−1) trajectories for classical rejection sampling. Including the stated reflection costs gives depth O([Ld2∣X∣2+(log⁡2d+Llog⁡2∣X∣)2]/p)O([Ld^2|\mathcal X|^2+(\log_2d+L\log_2|\mathcal X|)^2]/\sqrt p)O([Ld2∣X∣2+(log2​d+Llog2​∣X∣)2]/p​). Memory compression applies to the model register; storing outputs still requires Llog⁡2∣X∣L\log_2|\mathcal X|Llog2​∣X∣ qubits. The paper also derives probability-estimation query complexity O(p−1/2δ−2)O(p^{-1/2}\delta^{-2})O(p−1/2δ−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−610^{-6}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≈2.445×10−15p\approx2.445\times10^{-15}p≈2.445×10−15 to probability approximately 0.9920.9920.992 after 2242^{24}224 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.
Financial crashes, cascading failures in infrastructure, and critical errors in AI systems are frequently triggered by events that occur with extremely small probability. Efficiently discovering and sampling events with probability below a threshold is therefore of critical interest. Yet this task is highly non-trivial using existing classical or quantum methods. Being rare, such events require an immense sampling overhead to collect sufficient data samples. Moreover, because the rare events are not known in advance, they cannot be flagged for amplification using standard techniques. Here, we introduce a quantum algorithm for rare-event discovery and sampling without first learning which events are rare. The algorithm achieves the optimal quantum scaling with the rarity threshold. We further demonstrate that this can achieve a quadratic speedup for heavy-tailed systems whose tail has nonvanishing total mass, and translates into a robust polynomial speedup for stationary stochastic processes, with the exponent determined by its entropy-rate structure.
Many potential future events have devastating consequences, from the onset of earthquakes to financial black swan events. Accurate predictions of their probability of occurrence are vital. Yet as the stochastic systems underlying such events become increasingly complex, these probabilities can depend on ever-growing amounts of past data, which require ever more memory to track. The accuracy of our estimates is ultimately limited by both computational and memory constraints; the former to reduce sampling error, the latter to avoid sampling bias. Traditional quantum algorithms -- such as amplitude estimation -- address only the former, and become untenable especially in near-future quantum devices where quantum memory is a premium. Here, we offer quantum-algorithmic means to reduce systematic bias while maintaining a quadratic speed-up. Our results thus advance the timeline for the practical deployment of quantum technologies, and illustrate their additional benefits when simulating processes of growing complexity.
Abstract Quantum technologies offer a promising route to the efficient sampling and analysis of stochastic processes, with potential applications across the sciences. Such quantum advantages rely on the preparation of a quantum sample state of the stochastic process, which requires a memory system to propagate correlations between the past and future of the process. Here, we introduce a method of lossy quantum dimension reduction that allows this memory to be compressed, not just beyond classical limits, but also beyond current state-of-the-art quantum stochastic sampling approaches. We investigate the trade-off between the saving in memory resources from this compression, and the distortion it introduces. We show that our approach can be highly effective in low distortion compression of both Markovian and strongly non-Markovian processes alike. We further discuss the application of our results to quantum stochastic modelling more broadly.
Stochastic modeling of complex systems plays an essential, yet often computationally intensive, role across the quantitative sciences.Recent advances in quantum information processing have elucidated the potential for quantum simulators to exhibit memory advantages for such tasks.Heretofore, the focus has been on lossless memory compression, wherein the advantage is typically in terms of lessening the amount of information tracked by the model, while-arguably more practical-reductions in memory dimension are not always possible.Here, we address the case of lossy compression for quantum stochastic modeling of continuous-time processes, introducing a method for coarse graining in quantum state space that drastically reduces the requisite memory dimension for modeling temporal dynamics while retaining near-exact statistics.In contrast to classical coarse graining, this compression is not based on sacrificing temporal resolution and brings memory-efficient high-fidelity stochastic modeling within reach of present quantum technologies.
Complex systems are embedded in our everyday experience. Stochastic modelling enables us to understand and predict the behaviour of such systems, cementing its utility across the quantitative sciences. Accurate models of highly non-Markovian processes - where the future behaviour depends on events that happened far in the past - must track copious amounts of information about past observations, requiring high-dimensional memories. Quantum technologies can ameliorate this cost, allowing models of the same processes with lower memory dimension than corresponding classical models. Here we implement such memory-efficient quantum models for a family of non-Markovian processes using a photonic setup. We show that with a single qubit of memory our implemented quantum models can attain higher precision than possible with any classical model of the same memory dimension. This heralds a key step towards applying quantum technologies in complex systems modelling.
Recently, sample-based quantum diagonalization (SQD) has emerged as a promising approach to compute ground and excited states of problem Hamiltonians.This method classically diagonalizes a Hamiltonian in a subspace that is spanned by samples obtained from a quantum computer. However, by its nature, SQD suffers from a fundamental sampling problem, as some basis states that are required for a targeted accuracy may only be sampled extremely rarely. To alleviate this limitation, we introduce the SQD-AA algorithm that combines SQD with amplitude amplification (AA). SQD-AA uses AA to sequentially reduce probabilities of already measured bitstrings, thus making the observation of new ones more likely. We observe a reduction in the total query complexity of more than a factor 100 for algebraically and exponentially decaying model distributions, and analytically show a quadratic advantage for the latter. Moreover, we evaluate real molecules in an early fault-tolerant scenario and compare SQD-AA to SQD and iterative quantum phase estimation (iQPE). For all considered examples, we observe the lowest total number of T-gates for SQD-AA while only requiring circuits that are 3-4 orders of magnitude shallower than those needed for iQPE. Given this substantial reduction in circuit depth compared to iQPE while saving 2 orders of magnitude in total runtime compared to SQD, we expect a significant regime in early fault-tolerance where SQD-AA runs feasibly, but iQPE circuits are too deep to execute confidently.