A quantum spectral method for simulating stochastic processes, with
applications to Monte Carlo
- URL: http://arxiv.org/abs/2303.06719v1
- Date: Sun, 12 Mar 2023 17:54:38 GMT
- Title: A quantum spectral method for simulating stochastic processes, with
applications to Monte Carlo
- Authors: Adam Bouland, Aditi Dandapani and Anupam Prakash
- Abstract summary: We introduce a new analog'' quantum representation of processes, in which the value of the process at time t is stored in the amplitude of the quantum state.
We show that we can simulate $T$ timesteps of fractional Brownian motion using a quantum circuit with gate complexity $textpolylog(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(textpolylog(Tepsilon
- Score: 4.134846879110833
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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
$\text{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(\text{polylog}(T)\epsilon^{-c})$ where $3/2<c<2$ for certain variants of
fractional Brownian motion, whereas classical Monte Carlo runs in time
$O(T\epsilon^{-2})$ and quantum mean estimation in time $O(T\epsilon^{-1})$.
Along the way we give an efficient algorithm to coherently load a quantum
state with Gaussian amplitudes of differing variances, which may be of
independent interest.
Related papers
- Estimating quantum amplitudes can be exponentially improved [11.282486674587236]
Estimating quantum amplitudes is a fundamental task in quantum computing.
We present a novel framework for estimating quantum amplitudes by transforming pure states into their matrix forms.
Our framework achieves the standard quantum limit $epsilon-2$ and the Heisenberg limit $epsilon-1$, respectively.
arXiv Detail & Related papers (2024-08-25T04:35:53Z) - Evaluation of phase shifts for non-relativistic elastic scattering using quantum computers [39.58317527488534]
This work reports the development of an algorithm that makes it possible to obtain phase shifts for generic non-relativistic elastic scattering processes on a quantum computer.
arXiv Detail & Related papers (2024-07-04T21:11:05Z) - Robust Extraction of Thermal Observables from State Sampling and
Real-Time Dynamics on Quantum Computers [49.1574468325115]
We introduce a technique that imposes constraints on the density of states, most notably its non-negativity, and show that this way, we can reliably extract Boltzmann weights from noisy time series.
Our work enables the implementation of the time-series algorithm on present-day quantum computers to study finite temperature properties of many-body quantum systems.
arXiv Detail & Related papers (2023-05-30T18:00:05Z) - Sublinear scaling in non-Markovian open quantum systems simulations [0.0]
We introduce a numerically exact algorithm to calculate process tensors.
Our approach requires only $mathcalO(nlog n)$ singular value decompositions for environments with infinite memory.
arXiv Detail & Related papers (2023-04-11T15:40:33Z) - Gradient-descent quantum process tomography by learning Kraus operators [63.69764116066747]
We perform quantum process tomography (QPT) for both discrete- and continuous-variable quantum systems.
We use a constrained gradient-descent (GD) approach on the so-called Stiefel manifold during optimization to obtain the Kraus operators.
The GD-QPT matches the performance of both compressed-sensing (CS) and projected least-squares (PLS) QPT in benchmarks with two-qubit random processes.
arXiv Detail & Related papers (2022-08-01T12:48:48Z) - Probing finite-temperature observables in quantum simulators of spin
systems with short-time dynamics [62.997667081978825]
We show how finite-temperature observables can be obtained with an algorithm motivated from the Jarzynski equality.
We show that a finite temperature phase transition in the long-range transverse field Ising model can be characterized in trapped ion quantum simulators.
arXiv Detail & Related papers (2022-06-03T18:00:02Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory.
We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z) - Quantum Markov Chain Monte Carlo with Digital Dissipative Dynamics on
Quantum Computers [52.77024349608834]
We develop a digital quantum algorithm that simulates interaction with an environment using a small number of ancilla qubits.
We evaluate the algorithm by simulating thermal states of the transverse Ising model.
arXiv Detail & Related papers (2021-03-04T18:21:00Z) - Quantum-enhanced analysis of discrete stochastic processes [0.8057006406834467]
We propose a quantum algorithm for calculating the characteristic function of a Discrete processes (DSP)
It completely defines its probability distribution, using the number of quantum circuit elements that grows only linearly with the number of time steps.
The algorithm takes all trajectories into account and hence eliminates the need of importance sampling.
arXiv Detail & Related papers (2020-08-14T16:07:35Z) - Algorithms for quantum simulation at finite energies [0.7734726150561088]
We introduce two kinds of quantum algorithms to explore microcanonical and canonical properties of many-body systems.
One is a hybrid quantum algorithm that computes expectation values in a finite energy interval around its mean energy.
The other is a quantum-assisted Monte Carlo sampling method to compute other quantities.
arXiv Detail & Related papers (2020-06-04T17:40:29Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.