Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2303.04945

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

Philip Intallura, Georgios Korpas, Sudeepto Chakraborty, Lawrence, Rufus, Wodecki, Ales, Vyacheslav Kungurtsev, Jakub Mareček

Published Mar 8, 2023• 21 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2303.04945

Related papers

Quantum computing for chemistry and physics applications from a Monte Carlo perspective

Guglielmo Mazzola

This Perspective focuses on the several overlaps between quantum algorithms and Monte Carlo methods in the domains of physics and chemistry. We will analyze the challenges and possibilities of integrating established quantum Monte Carlo solutions into quantum algorithms. These include refined energy estimators, parameter optimization, real and imaginary-time dynamics, and variational circuits. Conversely, we will review new ideas for utilizing quantum hardware to accelerate the sampling in statistical classical models, with applications in physics, chemistry, optimization, and machine learning. This review aims to be accessible to both communities and intends to foster further algorithmic developments at the intersection of quantum computing and Monte Carlo methods. Most of the works discussed in this Perspective have emerged within the last two years, indicating a rapidly growing interest in this promising area of research.

arXiv:2308.07964•The Journal of Chemical Physics•Jan 2, 2024•48 citations

Quantum speedup of Monte Carlo methods

Ashley Montanaro

Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.

arXiv:1504.06987•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Aug 26, 2015•431 citations

Some programming aspects of quantum Monte Carlo calculations

B. J. Alder, David M. Ceperley

The Monte Carlo method is a powerful scheme to solve many mathematical equations and is in fact, made practical only through high speed computers, particularly for those physical problems that are of high dimensionality. Alternative numerical schemes of spanning high dimensional spaces uniformly with a grid, increase in computational time exponentially with the dimensionality and thus became rapidly impractical as the dimensionality increases. The key to success of a Monte Carlo scheme is that it samples the space selectively, not with some uniform random distribution but where it matters most, by a probability density called an importance function. Furthermore, the Monte Carlo scheme is well adapted to computers since it consists of a simple, highly repetitive algorithm that takes advantage of the fast arithmetic capabilities of the machines. Consideration of how to arrange such calculations efficiently on various machines of different architecture is discussed.

•Jul 28, 1981•1 citation

Quantum algorithms for Monte Carlo integration using pseudo-random numbers

Koichi Miyamoto

Quantum algorithms for Monte Carlo integration (QMCI), which are based on quantum amplitude estimation (QAE), provide quadratic speed-up compared with classical counterparts, and are therefore widely investigated, along with applications to industries such as finance. One typical feature of problems in finance is high dimensionality, or, in other words, the necessity to create numerous random numbers (RNs) to calculate the integrand. In such a situation, the original implementation of QMCI, in which states encoding the probability distributions of the RNs are generated on different quantum registers, requires a large number of qubits. In this poster, we propose an implementation of QMCI, in which pseudo-random numbers (PRNs) are sequentially generated on one register, and therefore the qubit number is tremendously reduced. Moreover, we show that, when the integrand has the form such that contributions from different RNs are separable into different terms, we can also achieve time complexity reduction with respect to the number of dimensions by combining the nested QAE and use of PRNs.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2021•3 citations

Quantum Algorithm for Exact Monte Carlo Sampling

Nicolas Destainville, Bertrand Georgeot, Olivier Giraud

We build a quantum algorithm which uses the Grover quantum search procedure in order to sample the exact equilibrium distribution of a wide range of classical statistical mechanics systems. The algorithm is based on recently developed exact Monte Carlo sampling methods, and yields a polynomial gain compared to classical procedures.

arXiv:1003.1862•Physical Review Letters•Jun 23, 2010•5 citations

Bounding the speedup of the quantum-enhanced Markov-chain Monte Carlo algorithm

Alev Orfi, Dries Sels

Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [D. Layden et al., Nature (London) 619, 282 (2023).] proposed a quantum-enhanced Markov-chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.

arXiv:2403.03087•Physical Review A•Nov 12, 2024•17 citations
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.
This Perspective focuses on the several overlaps between quantum algorithms and Monte Carlo methods in the domains of physics and chemistry. We will analyze the challenges and possibilities of integrating established quantum Monte Carlo solutions into quantum algorithms. These include refined energy estimators, parameter optimization, real and imaginary-time dynamics, and variational circuits. Conversely, we will review new ideas for utilizing quantum hardware to accelerate the sampling in statistical classical models, with applications in physics, chemistry, optimization, and machine learning. This review aims to be accessible to both communities and intends to foster further algorithmic developments at the intersection of quantum computing and Monte Carlo methods. Most of the works discussed in this Perspective have emerged within the last two years, indicating a rapidly growing interest in this promising area of research.
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
The Monte Carlo method is a powerful scheme to solve many mathematical equations and is in fact, made practical only through high speed computers, particularly for those physical problems that are of high dimensionality. Alternative numerical schemes of spanning high dimensional spaces uniformly with a grid, increase in computational time exponentially with the dimensionality and thus became rapidly impractical as the dimensionality increases. The key to success of a Monte Carlo scheme is that it samples the space selectively, not with some uniform random distribution but where it matters most, by a probability density called an importance function. Furthermore, the Monte Carlo scheme is well adapted to computers since it consists of a simple, highly repetitive algorithm that takes advantage of the fast arithmetic capabilities of the machines. Consideration of how to arrange such calculations efficiently on various machines of different architecture is discussed.
Quantum algorithms for Monte Carlo integration (QMCI), which are based on quantum amplitude estimation (QAE), provide quadratic speed-up compared with classical counterparts, and are therefore widely investigated, along with applications to industries such as finance. One typical feature of problems in finance is high dimensionality, or, in other words, the necessity to create numerous random numbers (RNs) to calculate the integrand. In such a situation, the original implementation of QMCI, in which states encoding the probability distributions of the RNs are generated on different quantum registers, requires a large number of qubits. In this poster, we propose an implementation of QMCI, in which pseudo-random numbers (PRNs) are sequentially generated on one register, and therefore the qubit number is tremendously reduced. Moreover, we show that, when the integrand has the form such that contributions from different RNs are separable into different terms, we can also achieve time complexity reduction with respect to the number of dimensions by combining the nested QAE and use of PRNs.
Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [D. Layden et al., Nature (London) 619, 282 (2023).] proposed a quantum-enhanced Markov-chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.