Cina Aghamohammdi, Samuel P. Loomis, John R. Mahoney, and James P. Crutchfield |

**ABSTRACT: **
We introduce a quantum algorithm for memory-efficient biased
sampling of rare events generated by classical memoryful
stochastic processes. Two efficiency metrics are used to compare
quantum and classical resources for rare-event sampling. For a
fixed stochastic process, the first is the classical-to-quantum
ratio of required memory. We show for two example processes that
there exists an infinite number of rare-event classes for which
the memory ratio for sampling is larger than r, for any large real
number r. Then, for a sequence of processes each labeled by an
integer size N, we compare how the classical-to-quantum required
memory ratio scales with N. In this setting, since both memories
can diverge as N → ∞, the efficiency metric tracks how
fast they diverge. An extreme quantum memory advantage exists when
the classical memory diverges in the limit N → ∞, but the
quantum memory has a finite bound. We then show that finite-state
Markov processes and spin chains exhibit extreme memory advantage
for sampling of almost all of their rare-event classes.

Cina Aghamohammdi, Samuel P. Loomis, John R. Mahoney, and James P. Crutchfield, “Extreme Quantum Memory Advantage for Rare-Event Sampling”, Physical Review X

doi:10.1103/PhysRevX.8.011025.

[pdf]

Santa Fe Institute Working Paper 2017-08-029.

arxiv.org:1707.09553 [quant-ph].