Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation

Abstract

Quantum Monte Carlo integration (QMCI) is a quantum algorithm to estimate expectations of random variables, with applications in various industrial fields such as financial derivative pricing. When QMCI is applied to expectations concerning a stochastic process $X(t)$, e.g., an underlying asset price in derivative pricing, the quantum circuit $U_{X(t)}$ to generate the quantum state encoding the probability density of $X(t)$ can have a large depth. With time discretized into $N$ points, using state preparation oracles for the transition probabilities of $X(t)$, the state preparation for $X(t)$ results in a depth of $O(N)$, which may be problematic for large $N$. Moreover, if we estimate expectations concerning $X(t)$ at $N$ time points, the total query complexity scales on $N$ as $O(N^2)$, which is worse than the $O(N)$ complexity in the classical Monte Carlo method. In this paper, to improve this, we propose a method to divide $U_{X(t)}$ based on orthogonal series density estimation. This approach involves approximating the densities of $X(t)$ at $N$ time points with orthogonal series, where the coefficients are estimated as expectations of the orthogonal functions by QMCI. By using these approximated densities, we can estimate expectations concerning $X(t)$ by QMCI without requiring deep circuits. Our error and complexity analysis shows that to obtain the approximated densities at $N$ time points, our method achieves the circuit depth and total query complexity scaling as $O(\sqrt{N})$ and $O(N^{3/2})$, respectively.

17 pages, 3 figures, 1 table

References in corpus (20)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Amplitude Amplification and Estimation
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Quantum speedup of Monte Carlo methods
• Quantum Risk Analysis
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Amplitude estimation without phase estimation
• Option Pricing using Quantum Computers
• Black-box quantum state preparation without arithmetic
• A Threshold for Quantum Advantage in Derivative Pricing
• Low depth algorithms for quantum amplitude estimation
• Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth
• Quantum algorithms for approximate function loading
• The Efficient Preparation of Normal Distributions in Quantum Registers
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• The Problem with Grover-Rudolph State Preparation for Quantum Monte-Carlo
• Accelerated quantum circuit Monte-Carlo simulation for heavy quark thermalization
• Option pricing under stochastic volatility on a quantum computer
• Quantum mean estimation for lattice field theory
• Quantum self-learning Monte Carlo with quantum Fourier transform sampler

Cited by in corpus (1)

• Quantum algorithm for solving McKean-Vlasov stochastic differential equations