pith. sign in

arxiv: 2606.06316 · v1 · pith:KAIZO33Xnew · submitted 2026-06-04 · 🪐 quant-ph · cs.AI· cs.DS

Quantum enhanced rare event discovery and sampling

Naixu Guo , Po-Wei Huang , Qisheng Wang , Jayne Thompson , Patrick Rebentrost , Mile Gu , Chengran Yang This is my paper

Pith reviewed 2026-06-28 01:09 UTC · model grok-4.3

classification 🪐 quant-ph cs.AIcs.DS
keywords quantum algorithmrare event samplingquantum speedupheavy-tailed distributionsstochastic processesamplitude amplificationquantum oracle
0
0 comments X

The pith

A quantum algorithm discovers and samples rare events without first identifying them

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a quantum algorithm for discovering and sampling events below a given probability threshold without needing to identify or flag those events ahead of time. This sidesteps the classical requirement of immense sampling overhead to encounter rare events by chance. The algorithm reaches the optimal quantum scaling set by the rarity threshold. It delivers quadratic speedup for heavy-tailed distributions whose tail carries nonvanishing total probability mass and produces polynomial speedup for stationary stochastic processes whose rate is fixed by the entropy-rate structure.

Core claim

The central claim is that a quantum algorithm for rare-event discovery and sampling exists which operates via an oracle permitting sampling and amplitude operations on the underlying probability distribution without any prior identification of the rare events. This algorithm attains optimal quantum scaling with the rarity threshold, quadratic speedup for heavy-tailed systems whose tail has nonvanishing total mass, and robust polynomial speedup for stationary stochastic processes whose exponent is set by the entropy-rate structure.

What carries the argument

Quantum oracle access model that supplies sampling and amplitude operations directly on the probability distribution, enabling amplification of unknown rare-event subsets.

If this is right

  • The algorithm attains optimal quantum scaling with the rarity threshold.
  • Quadratic speedup holds for heavy-tailed systems whose tail has nonvanishing total mass.
  • Polynomial speedup holds for stationary stochastic processes, with the exponent fixed by entropy-rate structure.
  • Rare-event sampling becomes feasible for applications such as financial crashes and infrastructure failures using quantum resources instead of exhaustive classical trials.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same oracle model could be applied to estimate tail probabilities in Monte Carlo simulations of physical or engineered systems.
  • Near-term quantum hardware tests on small heavy-tailed distributions would directly check the predicted query scaling.
  • Hybrid classical-quantum workflows could use the quantum subroutine only for the rare-event amplification step.

Load-bearing premise

The algorithm can be realized with a quantum oracle or access model that permits sampling and amplitude operations on the underlying probability distribution without any prior identification or flagging of the rare events.

What would settle it

Run the algorithm on a quantum simulator for a concrete heavy-tailed distribution such as a power-law tail, count the oracle queries needed to collect samples below a chosen rarity threshold, and check whether the observed scaling matches the claimed optimal quantum dependence rather than the classical 1/p scaling.

Figures

Figures reproduced from arXiv: 2606.06316 by Chengran Yang, Jayne Thompson, Mile Gu, Naixu Guo, Patrick Rebentrost, Po-Wei Huang, Qisheng Wang.

Figure 1
Figure 1. Figure 1: FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper introduces a quantum algorithm for rare-event discovery and sampling that does not require prior identification or flagging of the rare events. It claims to achieve the optimal quantum scaling with the rarity threshold, a quadratic speedup for heavy-tailed systems whose tail has nonvanishing total mass, and a robust polynomial speedup for stationary stochastic processes whose exponent is set by the entropy-rate structure.

Significance. If the central claims hold and the required oracle can be realized, the work would constitute a meaningful contribution to quantum algorithms for rare-event problems, with potential relevance to applications in risk analysis and stochastic modeling. The absence of any derivation, oracle definition, or proof sketch in the manuscript prevents confirmation that the stated speedups follow from the assumptions.

major comments (1)
  1. [Abstract] Abstract, paragraph 3: the algorithm is asserted to achieve optimal quantum scaling and the listed speedups, yet no oracle model, amplitude amplification construction, or complexity analysis is supplied; without these the central claims cannot be verified or shown to be non-circular with respect to the sampling access assumed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review and for identifying the absence of explicit technical details supporting the central claims. We address the comment below and will revise the manuscript to incorporate the requested elements.

read point-by-point responses

  1. Referee: [Abstract] Abstract, paragraph 3: the algorithm is asserted to achieve optimal quantum scaling and the listed speedups, yet no oracle model, amplitude amplification construction, or complexity analysis is supplied; without these the central claims cannot be verified or shown to be non-circular with respect to the sampling access assumed.

    Authors: We agree that the submitted manuscript lacks an explicit oracle definition, amplitude amplification construction, and complexity analysis. In the revised version we will add a dedicated technical section that (i) defines the oracle as a standard quantum sampling oracle providing coherent access to the underlying probability distribution (without any prior flagging of rare events), (ii) presents the amplitude amplification construction that marks and amplifies events below a rarity threshold on the fly, and (iii) supplies the query-complexity analysis establishing the optimal O(1/sqrt(p)) scaling with rarity threshold p. The analysis will demonstrate that the quadratic speedup for heavy-tailed distributions and the polynomial speedup for stationary processes follow directly from this construction without circularity in the assumed access model. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The supplied material consists solely of an abstract with no equations, derivation steps, fitted parameters, or self-citations. No load-bearing claim reduces by construction to its own inputs, and the oracle model is stated without internal definitions that would create self-definitional or fitted-input circularity. The derivation chain cannot be walked because no technical sections or equations are present; the central claims therefore remain self-contained against external benchmarks with no evidence of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger records the minimal high-level assumptions required to state the central claim. No free parameters, invented entities, or detailed axioms are extractable.

axioms (1)
  • domain assumption Quantum access to the probability distribution is available via an oracle that supports sampling and amplitude amplification without event pre-identification.
    Required to realize the claimed scaling; stated implicitly in the abstract description of the algorithm.

pith-pipeline@v0.9.1-grok · 5693 in / 1340 out tokens · 20203 ms · 2026-06-28T01:09:26.551364+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

71 extracted references · 2 linked inside Pith

  1. [1]

    J. van Apeldoorn, Quantum probability oracles & mul- tidimensional amplitude estimation, in16th Conference on the Theory of Quantum Computation, Communica- tion and Cryptography (TQC 2021), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 197, edited by M.-H. Hsieh (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, Dagstuhl, Germany, 202...

    2021

  2. [2]

    Bar-Yossef,The Complexity of Massive Data Set Com- putations, Ph.D

    Z. Bar-Yossef,The Complexity of Massive Data Set Com- putations, Ph.D. thesis, University of California, Berkeley (2002)

    2002

  3. [3]

    Brassard, P

    G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, inQuantum com- putation and information, Contemporary Mathematics, Vol. 305 (American Mathematical Society, Providence, RI, USA, 2002) pp. 53–74

    2002

  4. [4]

    N. Guo, K. Mitarai, and K. Fujii, Nonlinear transforma- tion of complex amplitudes via quantum singular value transformation, Phys. Rev. Res.6, 043227 (2024)

    2024

  5. [5]

    A. G. Rattew and P. Rebentrost, Non-linear transforma- tions of quantum amplitudes: Exponential improvement, generalization, and applications (2023), arXiv:2309.09839 [quant-ph]

    arXiv 2023

  6. [6]

    N. Guo, Z. Yu, M. Choi, Y. Han, A. Agrawal, K. Nakaji, A. Aspuru-Guzik, and P. Rebentrost, Quantum trans- former: Accelerating model inference via quantum linear algebra (2024), arXiv:2402.16714 [quant-ph]

    arXiv 2024

  7. [7]

    A. G. Rattew, P.-W. Huang, N. Guo, L. Pira, and P. Rebentrost, Accelerating inference for multilayer neu- ral networks with quantum computers, inThe Fourteenth International Conference on Learning Representations 8 (2026)

    2026

  8. [8]

    Y. Du, X. Wang, N. Guo, Z. Yu, Y. Qian, K. Zhang, M. Hsieh, P. Rebentrost, and D. Tao,A Gentle Introduc- tion to Quantum Machine Learning, Artificial Intelligence (R0) (Springer Nature Singapore, 2025)

    2025

  9. [9]

    C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM J. Comput.26, 1510 (1997)

    1997

  10. [10]

    A. Belovs, Quantum algorithms for classical probability distributions, in27th Annual European Symposium on Algorithms (ESA 2019), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 144, edited by M. A. Bender, O. Svensson, and G. Herman (Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Informatik, Dagstuhl, Germany, 2019) pp. 16:1–16:11

    2019

  11. [11]

    Bollerslev, V

    T. Bollerslev, V. Todorov, and S. Z. Li, Jump tails, ex- treme dependencies, and the distribution of stock returns, J. Econom.172, 307–324 (2013)

    2013

  12. [12]

    Dobson, B

    I. Dobson, B. A. Carreras, V. E. Lynch, and D. E. New- man, Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization, Chaos17(2007)

    2007

  13. [13]

    C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J.27, 379 (1948)

    1948

  14. [14]

    Aghamohammadi, S

    C. Aghamohammadi, S. P. Loomis, J. R. Mahoney, and J. P. Crutchfield, Extreme quantum memory advantage for rare-event sampling, Phys. Rev. X8, 011025 (2018)

    2018

  15. [15]

    Blanchet, F

    J. Blanchet, F. He, and K. Murthy, On distributionally robust extreme value analysis, Extremes23, 317–347 (2020)

    2020

  16. [16]

    F. C. Binder, J. Thompson, and M. Gu, Practical unitary simulator for non-Markovian complex processes, Phys. Rev. Lett.120, 240502 (2018)

    2018

  17. [17]

    C. Yang, F. C. Binder, V. Narasimhachar, and M. Gu, Matrix product states for quantum stochastic modeling, Phys. Rev. Lett.121, 260602 (2018)

    2018

  18. [18]

    Layden, R

    D. Layden, R. Sweke, V. Havl´ ıˇ cek, A. Chowdhury, and K. Neklyudov, Wavefunction flows: Efficient quan- tum simulation of continuous flow models (2025), arXiv:2510.08462 [quant-ph]

    arXiv 2025

  19. [19]

    C. Yang, M. Florido-Llin` as, M. Gu, and T. J. Elliott, Dimension reduction in quantum sampling of stochastic processes, npj Quantum Inf.11(2025)

    2025

  20. [20]

    G. H. Low and I. L. Chuang, Optimal Hamiltonian sim- ulation by quantum signal processing, Phys. Rev. Lett. 118, 010501 (2017)

    2017

  21. [21]

    Gily´ en, Y

    A. Gily´ en, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics, inPro- ceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 (Association for Computing Machinery, New York, NY, USA, 2019) pp. 193–204

    2019

  22. [22]

    Chakraborty, A

    S. Chakraborty, A. Gily´ en, and S. Jeffery, The power of block-encoded matrix powers: Improved regression tech- niques via faster Hamiltonian simulation, in46th Interna- tional Colloquium on Automata, Languages, and Program- ming (ICALP 2019), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 132, edited by C. Baier, I. Chatzigiannakis, P. ...

    2019

  23. [23]

    C. W. Helstrom, Detection theory and quantum mechan- ics, Inf. Control10, 254–291 (1967)

    1967

  24. [24]

    Holevo, Statistical decision theory for quantum sys- tems, J

    A. Holevo, Statistical decision theory for quantum sys- tems, J. Multivar. Anal.3, 337–394 (1973)

    1973

  25. [25]

    Watrous,The Theory of Quantum Information(Cam- bridge University Press, 2018)

    J. Watrous,The Theory of Quantum Information(Cam- bridge University Press, 2018)

    2018

  26. [26]

    Lin and Y

    L. Lin and Y. Tong, Near-optimal ground state prepara- tion, Quantum4, 372 (2020)

    2020

  27. [27]

    Y. Dong, X. Meng, K. B. Whaley, and L. Lin, Efficient phase-factor evaluation in quantum signal processing, Phys. Rev. A103, 042419 (2021)

    2021

  28. [28]

    Durr and P

    C. Durr and P. Høyer, A quantum algorithm for finding the minimum (1999), arXiv:quant-ph/9607014 [quant-ph]

    Pith/arXiv arXiv 1999

  29. [29]

    van Apeldoorn and A

    J. van Apeldoorn and A. Gily´ en, Improvements in quan- tum SDP-solving with applications, in46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Leibniz International Proceedings in In- formatics (LIPIcs), Vol. 132, edited by C. Baier, I. Chatzi- giannakis, P. Flocchini, and S. Leonardi (Schloss Dagstuhl – Leibniz-Zentrum f...

    2019

  30. [30]

    Ahuja and S

    A. Ahuja and S. Kapoor, A quantum algorithm for finding the maximum (1999), arXiv:quant-ph/9911082 [quant- ph]

    Pith/arXiv arXiv 1999

  31. [31]

    Y. Dong, L. Lin, and Y. Tong, Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of uni- tary matrices, PRX Quantum3, 040305 (2022)

    2022

  32. [32]

    Buhrman, S

    H. Buhrman, S. Gharibian, Z. Landau, F. Le Gall, N. Schuch, and S. Tamaki, Beating the natural Grover bound for low-energy estimation and state preparation, Phys. Rev. Lett.135, 030601 (2025)

    2025

  33. [33]

    Rabiner and B

    L. Rabiner and B. Juang, An introduction to hidden Markov models, IEEE ASSP Mag.3, 4 (1986)

    1986

  34. [34]

    P. H. Algoet and T. M. Cover, A sandwich proof of the Shannon–McMillan–Breiman theorem, Ann. Probab.16, 899 (1988)

    1988

  35. [35]

    Aghamohammadi and J

    C. Aghamohammadi and J. P. Crutchfield, Minimum memory for generating rare events, Phys. Rev. E95, 032101 (2017)

    2017

  36. [36]

    R. Chao, D. Ding, A. Gilyen, C. Huang, and M. Szegedy, Finding angles for quantum signal processing with ma- chine precision (2020), arXiv:2003.02831 [quant-ph]

    arXiv 2020

  37. [37]

    J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, Grand unification of quantum algorithms, PRX Quantum 2, 040203 (2021)

    2021

  38. [38]

    G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum3, 163 (2019)

    2019

  39. [39]

    Quantum enhanced rare event discovery and sampling

    J. Wang, Y. Dong, and L. Lin, On the energy landscape of symmetric quantum signal processing, Quantum6, 850 (2022). 9 Appendices for “Quantum enhanced rare event discovery and sampling” CONTENTS A. Notations 9 B. Problem definition of rare event sampling 10 C. Preliminary to quantum linear algebra 11 D. Quantum and classical algorithm for rare event sampling 12

    2022

  40. [40]

    Classical algorithm 12

  41. [41]

    Discussion 21

    Quantum algorithm 16 E. Discussion 21

  42. [42]

    Polynomial approximation 21

  43. [43]

    Phase transition of quantum advantages in power-law tails 23

    Related works 22 F. Phase transition of quantum advantages in power-law tails 23

  44. [44]

    Rank-frequency power-law model 23

  45. [45]

    Evaluation of the rare-event mass 24

  46. [46]

    Application to stochastic process 29

    Summary of quantum advantages and interpretations 29 G. Application to stochastic process 29

  47. [47]

    Stochastic processes and the Asymptotic Equipartition Property 29

  48. [48]

    Thermodynamic mapping for rare events 31

  49. [49]

    Quantum rare event sampling for stochastic processes 32

  50. [50]

    Numerical results 34

    Quantum stochastic modeling 33 H. Numerical results 34

  51. [51]

    Give me samples fromQ, but only if they are unlikely underP

    Perturbed coin model 35 Appendix A: Notations In this appendix, we collect the notation used throughout the paper. When we need to distinguish them, we reserve Ω for a generic finite sample space and X for the alphabet of a stochastic process. A generic finite distribution is written asP, Q: Ω→[0,1], with Ω ={x 1, . . . , xN }and X x∈Ω P(x) = 1, X x∈Ω Q(x...

  52. [52]

    If prare ≥p 1, then construct a sampler for a distribution that isΘ( ϵ + ζ)-close to QR in total variation distance, whereζ=q ∆/prare and QR = ( Q(xi)/prare, x i ∈ R, 0, x i /∈ R. (B.2)

  53. [53]

    Impossible

    Ifp rare ≤p 2, then output “Impossible”. The rare-event sampling problem considered in the main text is recovered as a special case of Problem S1. In the generalized formulation, the distribution P defines which events are rare, while the distribution Q defines how these rare events should be sampled. The main text focuses on the natural self-sampling cas...

  54. [54]

    Impossible

    Classical algorithm Theorem S2(Classical algorithm for general rare event sampling).There exists a classical algorithm that solves Problem S1 using O min 1 ∆ log N ϵ , 1 ∆2 log 1 ϵ (D.1) samples fromPandO(max{1/(p 1 −p 2 −q ∆)2,1/p rare})samples fromQ. Proof. We first construct a set of candidate rare events, which will be used to distinguish between the ...

  55. [55]

    impossible

    Quantum algorithm Theorem S4(Quantum algorithm for rare event sampling).There exists a quantum algorithm that solves Problem S1 using O max 1√p1 − √p2 , 1√prare 1√ ∆ log 1 ϵ (D.28) queries to UP and O max n 1√p1−√p2 , 1√prare o queries to UQ with O(n)ancilla qubits. Here, UP and UQ denote the quantum samplers forPandQ, respectively. Proof. By Theorem S1, ...

  56. [56]

    By Theorem S1, use c- UP /U † P a constant number of times to construct the diagonal block encoding of amplitudes UA

  57. [57]

    Implement a polynomial approximation of the rectangle function f(x) via Lemma S1, using O(1/ √ ∆ log(1/ϵ)) applications ofU A

  58. [58]

    Impossible

    Feed the quantum sample state |P⟩ into the constructed quantum circuit, and use amplitude amplification to boost the success probability and prepare the target state |PR⟩. This further uses O(1/√prare) applications of the constructed quantum circuit. In total, the algorithm usesO(1/ √∆prare log(1/ϵ)) applications of c-U P /U † P . FIG. S1. Description of ...

  59. [59]

    In this paper, we focus on the stochastic process, which implies that all quantum amplitudes (corresponding to the square root of the classical distribution) are real and positive

    Polynomial approximation Here, we provide some discussions of the polynomial approximation used in the quantum algorithm. In this paper, we focus on the stochastic process, which implies that all quantum amplitudes (corresponding to the square root of the classical distribution) are real and positive. To achieve the rare event-related tasks, we need a goo...

  60. [60]

    Our quantum algorithm achieves efficiency by performing these steps coherently, thereby avoiding the need to explicitly read out or measure the rare events

    Related works The rare event sampling problem can be decomposed into two distinct tasks: first, identifying the rare events, and second, sampling from them. Our quantum algorithm achieves efficiency by performing these steps coherently, thereby avoiding the need to explicitly read out or measure the rare events. In contrast, relying on the standard amplit...

  61. [61]

    The events are ordered so that P (x1) ≥P (x2) ≥ · · · ≥P (xN)

    Rank-frequency power-law model We consider a rank-ordered family of distributions overNevents, P(x k) = k−γ ZN,γ ,(F.4) 24 where γ≥ 0 is the tail exponent and ZN,γ := PN j=1 j−γ is the generalized harmonic number (also the partition function). The events are ordered so that P (x1) ≥P (x2) ≥ · · · ≥P (xN). Since the probabilities are monotone decreasing, t...

  62. [62]

    The case γ = 0 is the uniform case, and one cannot reasonably distinguish which event is rare

    Evaluation of the rare-event mass We now evaluate prare in the three tail regimes γ > 1, γ = 1, and 0 < γ < 1. The case γ = 0 is the uniform case, and one cannot reasonably distinguish which event is rare. Regime 1:γ >1.In this regime, the generalized harmonic number converges: ZN,γ =ζ(γ) +O(N 1−γ) = Θ(1),(F.11) whereζ(·) is the zeta function. Therefore, ...

  63. [63]

    the rare set is non-empty, and

  64. [64]

    The first requirement is that at least one state lies below the threshold

    the rare set does not coincide with the entire support. The first requirement is that at least one state lies below the threshold. Because P (xk) decreases with k, this is equivalent to demanding that the least probable state be rare: P(x N)≤∆.(F.39) Using Eq. (F.33) atk=N, we find P(x N) = N −γ ZN,γ = 1−γ N 1 +o(1) .(F.40) Hence, the rare set is non-empt...

  65. [65]

    The quantum algorithm always pays the thresholding cost Θ(∆ −1/2), but it pays an additional amplification factorp −1/2 rare

    Summary of quantum advantages and interpretations The preceding case analysis shows that the critical quantity is not merely the number of rare states, but the total probability mass carried by those states. The quantum algorithm always pays the thresholding cost Θ(∆ −1/2), but it pays an additional amplification factorp −1/2 rare . Thus: •ifp rare vanish...

  66. [66]

    A consecutive L output sequence xt:t+L := xt, xt+1,· · ·x t+L−1 is governed by the joint probability distribution Pr(x t:t+L)

    Stochastic processes and the Asymptotic Equipartition Property A discrete stochastic process generates a random output Xt at each time step t, which takes value xt from an alphabet X of finite alphabet size. A consecutive L output sequence xt:t+L := xt, xt+1,· · ·x t+L−1 is governed by the joint probability distribution Pr(x t:t+L). Stochastic processes c...

  67. [67]

    energy density

    Thermodynamic mapping for rare events By definition, rare events are events that are less likely to happen than typical events. The AEP theorem, per Lemma S6, claims that all of the typical sequences happen with probability roughly 2 −LH(X). Definition S6(Rare event for stochastic process).For a stochastic process X with entropy rate H(X), we define the s...

  68. [68]

    This corresponds to a special case of Theorem S4 when Q = P and p1 −p 2 =O(1)

    Quantum rare event sampling for stochastic processes In the following, we detail the applications of our algorithm to stochastic processes, which have additional properties provided by the AEP theorem and β-mapping. This corresponds to a special case of Theorem S4 when Q = P and p1 −p 2 =O(1). Given sampling access to a stochastic process, our goal is to ...

  69. [69]

    The ε-machine consists of a set of hidden memory states Siwith transition probability Pr(Sj, x|Si)

    Quantum stochastic modeling Given a stochastic process governed by distribution Pr(x0:L), we can always find a unifilar hidden Markov model, called ε-machine. The ε-machine consists of a set of hidden memory states Siwith transition probability Pr(Sj, x|Si). At each time step, the memory state updates to Sj from Si and outputs x with probability Pr(Sj, x|...

  70. [70]

    Setup We simulate the results of our algorithm using numpy by directly obtaining the matrix representation of the block-encoding unitaries and operating on them. For simulations on small-scale systems, we first construct a (1 , (L + χ) log|X | + 2, 0)-block encoding where diagonal encodes the amplitudes of the output quantum state of the recurrent quantum...

  71. [71]

    At each time step, the coin flips with probability p, otherwise remains at its original state, as shown in Fig

    Perturbed coin model We apply our example to a simple Markovian process that can be generated by a perturbed coin. At each time step, the coin flips with probability p, otherwise remains at its original state, as shown in Fig. S4. As time evolves, one may 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Event 0.0 0.019 0.038...

    2000