Mile Gu

Rare events, though infrequent, can have significant impacts across various domains. We present a quantum algorithm for efficiently sampling rare events from stochastic processes. Our algorithm constructs quantum sample states that superpose only rare events, defined as those occurring with probability below a threshold \(\Delta\). The algorithm consists of three key steps: (1) constructing an amplitude block encoding from the quantum sample state of the original process, (2) implementing quantum singular value transformation of a polynomial approximation of a thresholding function, and (3) performing measurement and post-selection. For sufficiently large sequence lengths, we prove that our algorithm achieves a quadratic speedup over classical methods, requiring only \(\Theta(1/\sqrt{\Delta})\) queries to prepare an even superposition over rare events, compared to the classical \(\mathcal{O}(1/\Delta)\) complexity. We demonstrate our algorithm's effectiveness through numerical simulations on the Dyson-Ising chain, showing successful identification and amplification of rare events while suppressing non-rare events.