Reduction of Qubits in Quantum Algorithm for Monte Carlo Simulation by Pseudo-random Number Generator

Abstract

It is known that quantum computers can speed up Monte Carlo simulation compared to classical counterparts. There are already some proposals of application of the quantum algorithm to practical problems, including quantitative finance. In many problems in finance to which Monte Carlo simulation is applied, many random numbers are required to obtain one sample value of the integrand, since those problems are extremely high-dimensional integrations, for example, risk measurement of credit portfolio. This leads to the situation that the required qubit number is too large in the naive implementation where a quantum register is allocated per random number. In this paper, we point out that we can reduce qubits keeping quantum speed up if we perform calculation similar to classical one, that is, estimate the average of integrand values sampled by a pseudo-random number generator (PRNG) implemented on a quantum circuit. We present not only the overview of the idea but also concrete implementation of PRNG and application to credit risk measurement. Actually, reduction of qubits is a trade-off against increase of circuit depth. Therefore full reduction might be impractical, but such a trade-off between speed and memory space will be important in adjustment of calculation setting considering machine specs, if large-scale Monte Carlo simulation by quantum computer is in operation in the future.

arXiv comment14 pages, 12 figures

References in corpus (13)

• Fault-tolerant quantum computation by anyons
• Surface codes: Towards practical large-scale quantum computation
• Quantum Amplitude Amplification and Estimation
• Quantum Networks for Elementary Arithmetic Operations
• Quantum speedup of Monte Carlo methods
• Quantum Risk Analysis
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Efficient Networks for Quantum Factoring
• Amplitude estimation without phase estimation
• Option Pricing using Quantum Computers
• Fast Quantum Modular Exponentiation
• Quantum algorithm and circuit design solving the Poisson equation
• Design of Efficient Reversible Logic Based Binary and BCD Adder Circuits

Cited by in corpus (11)

• Faster Amplitude Estimation
• Prospects and challenges of quantum finance
• Amplitude estimation via maximum likelihood on noisy quantum computer
• Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth
• Modified Grover operator for amplitude estimation
• Noisy quantum amplitude estimation without noise estimation
• Pricing multi-asset derivatives by finite difference method on a quantum computer
• Adaptive measurement strategy for noisy quantum amplitude estimation with variational quantum circuits
• Improving semi-device-independent randomness certification by entropy accumulation
• Classical post-processing approach for quantum amplitude estimation
• Quantum Speedup of Monte Carlo Integration with respect to the Number of Dimensions and its Application to Finance