  Discrete stochastic processes (DSP) are instrumental for modelling 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 takes all stochastic trajectories into account and
hence eliminates the need of importance sampling. The algorithm can be further
furnished with the quantum amplitude estimation algorithm to provide quadratic
speed-up in sampling. Both of these strategies improve variance beyond
classical capabilities. The quantum method can be combined with Fourier
approximation to estimate an expectation value of any integrable function of
the random variable. Applications in finance and correlated random walks are
presented to exemplify the usefulness of our results. Proof-of-principle
experiments are performed using the IBM quantum cloud platform.
