A Survey of Quantum Alternatives to Randomized Algorithms: Monte Carlo Integration and Beyond
For researchers in quantum computing and Monte Carlo methods, this survey provides a comprehensive overview of quantum alternatives, though it is a literature review without new results.
This survey reviews quantum algorithms for Monte Carlo integration, aiming to achieve a quantum speedup over classical methods. It covers existing quantum approaches and adaptive enhancements as alternatives to classical Monte Carlo.
Monte Carlo sampling is a powerful toolbox of algorithmic techniques widely used for a number of applications wherein some noisy quantity, or summary statistic thereof, is sought to be estimated. In this paper, we survey the literature for implementing Monte Carlo procedures using quantum circuits, focusing on the potential to obtain a quantum advantage in the computational speed of these procedures. We revisit the quantum algorithms that could replace classical Monte Carlo and then consider both the existing quantum algorithms and the potential quantum realizations that include adaptive enhancements as alternatives to the classical procedure.