Quantum-enhanced analysis of discrete stochastic processes

Discrete stochastic processes (DSP) are instrumental for modelling the dynamics of probabilistic systems and have wide 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 using the number of quantum circuit elements that grows only linearly with the number of time steps. The quantum algorithm reduces the sampling to a Bernoulli trial while taking all realizations into account. This approach guarantees the optimal variance without the need of importance sampling. The algorithm can be furnished with quantum amplitude estimation to provide additional speed-up. The Fourier approximation can be used to estimate an expectation value of any integrable function of the random variable. We present an application in finance, and demonstrate the proof-of-principle using a IBM quantum device.