Stochastic processes play a fundamental role in physics, mathematics, engineering and finance. One potential application of quantum computation is to better approximate properties of stochastic processes. For example, quantum algorithms for Monte Carlo estimation combine a quantum simulation of a stochastic process with amplitude estimation to improve mean estimation. In this work we study quantum algorithms for simulating stochastic processes which are compatible with Monte Carlo methods. We introduce a new ``analog'' quantum representation of stochastic processes, in which the value of the process at time t is stored in the amplitude of the quantum state, enabling an exponentially efficient encoding of process trajectories. We show that this representation allows for highly efficient quantum algorithms for simulating certain stochastic processes, using spectral properties of these processes combined with the quantum Fourier transform. In particular, we show that we can simulate
T timesteps of fractional Brownian motion using a quantum circuit with gate complexity
polylog(T), which coherently prepares the superposition over Brownian paths. We then show this can be combined with quantum mean estimation to create end to end algorithms for estimating certain time averages over processes in time
O(polylog(T)ε−c) where $3/2
Abstract The formulation of the dynamics of open quantum systems by means of stochastic processes in Hilbert space leads to efficient Monte–Carlo simulation techniques which are introduced and examined in this chapter. Depending on whether the stochastic process is a piecewise deterministic process or a diffusion process, the corresponding individual realizations consist of intervals of deterministic evolution periods interrupted by instantaneous quantum jumps, or of continuous, nowhere differentiable paths. Various Monte Carlo algorithms for both types of processes are described in detail, and their convergence behaviour and their numerical performance is investigated for a number of applications, such as the damped harmonic oscillator, the driven two-level system, and the damped driven Morse oscillator.
This thesis work deals with Monte Carlo (MC) simulations with the focus on quantum mechanical systems. I start with an introduction about Monte-Carlo methods in general and their application to the classical Ising model. The second, most important part deals with the problem in quantum mechanics, and presents a possible simulation method, the Stochastic Series Expansion (SSE). I give an introduction about the idea behind that method and give some results obtained for simulations for finite spin chains. All programming was performed in FORTRAN.