Quantum Speedup of Monte Carlo Integration with respect to the Number of Dimensions and its Application to Finance

• URL: http://arxiv.org/abs/2011.02165v2
• Date: Mon, 24 May 2021 01:56:54 GMT
• Title: Quantum Speedup of Monte Carlo Integration with respect to the Number of Dimensions and its Application to Finance
• Authors: Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda, Kazuyoshi Yoshino
• Abstract summary: In Monte Carlo integration, many random numbers are used for calculation of the integrand. In this paper, we point out that we can reduce the number of such repeated operations by a combination of the nested QAE and the use of pseudorandom numbers. We pick up one use case of this method in finance, the credit portfolio risk measurement, and estimate to what extent the complexity is reduced.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Monte Carlo integration using quantum computers has been widely investigated, including applications to concrete problems. It is known that quantum algorithms based on quantum amplitude estimation (QAE) can compute an integral with a smaller number of iterative calls of the quantum circuit which calculates the integrand, than classical methods call the integrand subroutine. However, the issues about the iterative operations in the integrand circuit have not been discussed so much. That is, in the high-dimensional integration, many random numbers are used for calculation of the integrand and in some cases similar calculations are repeated to obtain one sample value of the integrand. In this paper, we point out that we can reduce the number of such repeated operations by a combination of the nested QAE and the use of pseudorandom numbers (PRNs), if the integrand has the separable form with respect to contributions from distinct random numbers. The use of PRNs, which the authors originally proposed in the context of the quantum algorithm for Monte Carlo, is the key factor also in this paper, since it enables parallel computation of the separable terms in the integrand. Furthermore, we pick up one use case of this method in finance, the credit portfolio risk measurement, and estimate to what extent the complexity is reduced.

Related papers

• Quantum Fourier Iterative Amplitude Estimation [0.0]
  We present Quantum Fourier Iterative Amplitude Estimation (QFIAE) to build a new tool for estimating Monte Carlo integrals. QFIAE decomposes the target function into its Fourier series using a Parametrized Quantum Circuit (PQC) and a Quantum Neural Network (QNN) We show that QFIAE achieves comparable accuracy while being suitable for execution on real hardware.
  arXiv  Detail & Related papers  (2023-05-02T18:00:05Z)
• Calculating the many-body density of states on a digital quantum computer [58.720142291102135]
  We implement a quantum algorithm to perform an estimation of the density of states on a digital quantum computer. We use our algorithm to estimate the density of states of a non-integrable Hamiltonian on the Quantinuum H1-1 trapped ion chip for a controlled register of 18bits.
  arXiv  Detail & Related papers  (2023-03-23T17:46:28Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• A Generalized Quantum Inner Product and Applications to Financial Engineering [0.0]
  We present a canonical quantum computing method to estimate the weighted sum w(k)f(k) of the values taken by a discrete function f and real weights w(k) We further expand this framework by mapping function values to hashes in order to estimate weighted sums w(k)h(f(k)) of hashed function values with real hashes h.
  arXiv  Detail & Related papers  (2022-01-24T18:09:13Z)
• Numerical Simulations of Noisy Quantum Circuits for Computational Chemistry [51.827942608832025]
  Near-term quantum computers can calculate the ground-state properties of small molecules. We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
  arXiv  Detail & Related papers  (2021-12-31T16:33:10Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth [0.8122270502556371]
  The heart of the proposed method is a series decomposition of the sum that approximates the expectation in Monte Carlo integration. No previous proposal for quantum Monte Carlo integration has achieved all of these at once.
  arXiv  Detail & Related papers  (2021-05-19T12:47:14Z)
• 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)
• Model Evidence with Fast Tree Based Quadrature [0.0]
  We present a new algorithm called Tree Quadrature (TQ) TQ places no qualifications on how the samples provided to it are obtained, allowing it to use state-of-the-art sampling algorithms. On a set of benchmark problems, we show that TQ provides accurate approximations to integrals in up to 15 dimensions.
  arXiv  Detail & Related papers  (2020-05-22T17:48:06Z)

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.