Quantum-enhanced analysis of discrete stochastic processes

Carsten Blank, Daniel K. Park, Francesco Petruccione

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


Discrete stochastic processes (DSP) are instrumental for modeling the dynamics of probabilistic systems and have a wide spectrum of applications in science and engineering. DSPs are usually analyzed via Monte-Carlo methods since the number of realizations increases exponentially with the number of time steps, and importance sampling is often required to reduce the variance. We propose a quantum algorithm for calculating the characteristic function of a DSP, which completely defines its probability distribution, using the number of quantum circuit elements that grows only linearly with the number of time steps. The quantum algorithm reduces the Monte-Carlo sampling to a Bernoulli trial while taking all stochastic trajectories into account. This approach guarantees the optimal variance without the need for importance sampling. The algorithm can be further furnished with the quantum amplitude estimation algorithm to provide quadratic speed-up in sampling. The Fourier approximation can be used to estimate an expectation value of any integrable function of the random variable. Applications in finance and correlated random walks are presented. Proof-of-principle experiments are performed using the IBM quantum cloud platform.

Original languageEnglish
Article number126
Journalnpj Quantum Information
Issue number1
Publication statusPublished - 2021 Dec

Bibliographical note

Publisher Copyright:
© 2021, The Author(s).

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Statistical and Nonlinear Physics
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Quantum-enhanced analysis of discrete stochastic processes'. Together they form a unique fingerprint.

Cite this