A Survey of Quantum Alternatives to Randomized Algorithms: Monte Carlo Integration and Beyond

March 08, 2023 · The Cartographer · 🏛 arXiv.org

"No code URL or promise found in abstract"
"Title-pattern auto-detect: A Survey of Quantum Alternatives to Randomized Algorithms: Monte Carlo Integration and Beyond"

Evidence collected by the PWNC Scanner

Authors Philip Intallura, Georgios Korpas, Sudeepto Chakraborty, Vyacheslav Kungurtsev, Jakub Marecek arXiv ID 2303.04945 Category quant-ph: Quantum Computing Cross-listed cs.DS, math.NA, math.ST Citations 16 Venue arXiv.org Last Checked 2 days ago

Abstract

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.