Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth

This paper proposes a method of quantum Monte Carlo integration that retains the full quadratic quantum advantage, with-out requiring any arithmetic or quantum phase estimation to be performed on the quantum computer. No previous proposal for quantum Monte Carlo integration has achieved all of these at once. The heart of the proposed method is a Fourier series de-composition of the sum that approximates the expectation in Monte Carlo integra-tion, with each component then estimated individually using quantum amplitude es-timation. The main result is presented as theoretical statement of asymptotic ad-vantage, and numerical results are also in-cluded to illustrate the practical benefits of the proposed method. The method pre-sented in this paper is the subject of a patent application

Automated summary

This paper proposes a novel method for quantum Monte Carlo integration that utilizes Fourier series decomposition and quantum amplitude estimation to retain the full quadratic quantum advantage. The method is theoretically proven to have asymptotic advantage and is supported by numerical results showcasing its practical benefits.