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

Journal of Complexity

Multi-level Monte Carlo algorithms for infinite-dimensional integration on R N

Fred J. Hickernell, Thomas Müller-Gronbach, Ben Niu, Klaus Ritter

Published Mar 9, 2010• 52 citations
Publisher
DOI
10.1016/j.jco.2010.02.002

Related papers

Efficiency of Quasi-Monte Carlo Algorithms for High Dimensional Integrals

Henryk Woźniakowski

Springer eBooks•Jan 1, 2000•36 citations

Advanced Quasi-Monte Carlo Algorithms for High-dimensional Integration and Approximation

Gowri Suryanarayana

•May 27, 2016•0 citations

Photonic quantum algorithm for Monte Carlo integration

Patrick Rebentrost, Brajesh Gupt, Thomas R. Bromley

We present a continuous-variable photonic quantum algorithm for the Monte Carlo evaluation of multi-dimensional integrals. Our algorithm encodes n-dimensional integration into n+3 modes and can provide a quadratic speedup in runtime compared to the classical Monte Carlo approach. The speedup is achieved by developing a continuous-variable adaptation of amplitude estimation. We provide an error analysis for each element of the algorithm and account for the effects of finite squeezing. Our findings show that Monte Carlo integration is a natural use case for algorithms using the continuous-variable setting.

arXiv:1809.02579•Sep 7, 2018•3 citations

The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension

Fred J. Hickernell, Xiaoqun Wang

Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation. Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor ε \varepsilon is bounded by C ε − p C \varepsilon ^{-p} for some exponent p p and some positive constant C C . The ε \varepsilon -exponent of tractability is defined as the smallest power of ε − 1 \varepsilon ^{-1} in these bounds. It is shown by using Monte Carlo quadrature that the ε \varepsilon -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the ε \varepsilon -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.

Mathematics of Computation•Aug 2, 2001•61 citations

QUANTUM MONTE CARLO IN THE INFINITE DIMENSIONAL LIMIT

Mark Jarrell, H. Akhlaghpour, Thomas Pruschke

WORLD SCIENTIFIC eBooks•Dec 1, 1993•2 citations

Exploring the Potential of Quantum Monte Carlo Method for Computational Fluid Dynamics Simulations

Ferdin Sagai Don Bosco, Rochisha Agarwal, Aakif Akhtar +4 more

Quantum computing is a very active and diverse area, with immense research and development occurring in quantum hardware design and algorithm creation for applications in various scientific fields. The key motivation behind such efforts is the potential for significant speed-up relative to simulations on classical computers. Quantum Monte Carlo Integration (QMCI) is a quantum algorithm that promises a quadratic advantage in terms of the required number of samples for a required accuracy over classical Monte Carlo Integration (MCI), which is a key statistical resource for integrating multi-dimensional space. In this study, we explore the reality of this potential, specifically for applications in Computational Fluid Dynamics (CFD). We perform an eigenvalue stability analysis for a 1D convection-diffusion equation, in which the coefficients depend on a random number. The quantum algorithm utilized uses quantum amplitude estimation (QAE) to accelerate the integral estimation process. Numerical values obtained from QMCI results are compared against numerical integration techniques, and acceptably low errors are observed. The performance of QMCI is compared against MCI by equating the number of oracle calls in QMCI with the number of samples required in MCI. No significant difference in this metric is observed, with QMCI requiring more oracle calls. This suggests that the expected quantum supremacy is not attainable for the considered numerical integration problem and its quantum-circuit implementation. Extension to available Noisy-Intermediate-Scale-Quantum (NISQ) hardware is expected to reveal more about the algorithm implementation and the simulator emulation. Potential future directions that can be explored in algorithmic development based on this preliminary research are outlined.

AIAA SciTech Forum•Jan 3, 2025•0 citations
We present a continuous-variable photonic quantum algorithm for the Monte Carlo evaluation of multi-dimensional integrals. Our algorithm encodes n-dimensional integration into n+3 modes and can provide a quadratic speedup in runtime compared to the classical Monte Carlo approach. The speedup is achieved by developing a continuous-variable adaptation of amplitude estimation. We provide an error analysis for each element of the algorithm and account for the effects of finite squeezing. Our findings show that Monte Carlo integration is a natural use case for algorithms using the continuous-variable setting.
Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation. Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor ε \varepsilon is bounded by C ε − p C \varepsilon ^{-p} for some exponent p p and some positive constant C C . The ε \varepsilon -exponent of tractability is defined as the smallest power of ε − 1 \varepsilon ^{-1} in these bounds. It is shown by using Monte Carlo quadrature that the ε \varepsilon -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the ε \varepsilon -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.
Quantum computing is a very active and diverse area, with immense research and development occurring in quantum hardware design and algorithm creation for applications in various scientific fields. The key motivation behind such efforts is the potential for significant speed-up relative to simulations on classical computers. Quantum Monte Carlo Integration (QMCI) is a quantum algorithm that promises a quadratic advantage in terms of the required number of samples for a required accuracy over classical Monte Carlo Integration (MCI), which is a key statistical resource for integrating multi-dimensional space. In this study, we explore the reality of this potential, specifically for applications in Computational Fluid Dynamics (CFD). We perform an eigenvalue stability analysis for a 1D convection-diffusion equation, in which the coefficients depend on a random number. The quantum algorithm utilized uses quantum amplitude estimation (QAE) to accelerate the integral estimation process. Numerical values obtained from QMCI results are compared against numerical integration techniques, and acceptably low errors are observed. The performance of QMCI is compared against MCI by equating the number of oracle calls in QMCI with the number of samples required in MCI. No significant difference in this metric is observed, with QMCI requiring more oracle calls. This suggests that the expected quantum supremacy is not attainable for the considered numerical integration problem and its quantum-circuit implementation. Extension to available Noisy-Intermediate-Scale-Quantum (NISQ) hardware is expected to reveal more about the algorithm implementation and the simulator emulation. Potential future directions that can be explored in algorithmic development based on this preliminary research are outlined.