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

Cambridge University Press eBooks

When are integration and discrepancy tractable?

Erich Novak, H. Woźniakowski

Published May 17, 2001• 68 citations
Publisher

Abstract

Introduction There has been an increasing interest in studying computational aspects of high dimensional problems. Such problems are defined on spaces of functions of d variables and occur in many applications, with d that can be hundreds or even thousands. Examples include: • High dimensional integrals or path integrals with respect to the Wiener measure . These are important for many applications, in particular, in physics and in finance. High dimensional integrals also occur when we want to compute certain parameters of stochastic processes. Moreover, path integrals arise as solutions of partial differential equations given, for example, by the Feynman–Kac formula . See [25, 40, 66, 82, 85, 91]. • Global optimization where we need to compute the (global) minimum of a function of d variables. This occurs in many applications, for example, in pattern recognition and in image processing , see [97], or in the modelling and prediction of the geometry of proteins, see [45]. Simulated annealing strategies and genetic algorithms are often used, as well as smoothing techniques and other stochastic algorithms, see [10] and [74]. Some error bounds for deterministic and stochastic algorithms can be found in [42, 43, 44, 48, 53]. • The Schrödinger equation for m > 1 particles in ℝ 3 is a d = 3m -dimensional problem.

DOI
10.1017/cbo9781107360198.009

Related papers

04401 Summary – Algorithms and Complexity for Continuous Problems

Thomas Müller-Gronbach, Erich Novak, Knut Petras +1 more

The goal of this workshop was to bring together researchers from different communities working on computational aspects of continuous problems. Continuous computational problems arise in many areas of science and engineering. Examples include path and multivariate integration, function approximation, optimization, as well as differential, integral, and operator equations. Understanding the complexity of such problems and constructing efficient algorithms is both important and challenging. The workshop was of a very interdisciplinary nature with invitees from, e.g., computer science, numerical analysis, discrete, applied, and pure mathematics, physics, statistics, and scientific computation. Many of the lectures were presented by Ph.D. students. Compared to earlier meetings, several very active research areas received more emphasis. These include Quantum Computing, Complexity and Tractability of high-dimensional problems, Stochastic Computation, and Quantization, which was an entirely new field for this workshop. Due to strong connections between the topics treated at this workshop many of the participants initiated new cooperations and research projects. For more details, see the pdf-file with the same title.

Dagstuhl Seminar Proceedings•Jan 1, 2005•0 citations

Mathematics of the Feynman path integral

Vassili Nikitich Kolokoltsov

(and its generalisations that include magnetic fields) can be roughly divided into two classes. In the aproaches of the first class that we shall not discuss here in detail the Feynman integral is not supposed to be a genuine integral, but is specified as some generalised functional on an appropriate space of functions, which can be defined, for example, as the limit of certain discrete approximations (see e.g. [16], [44] and more recent papers [24], [25], [34]), by means of analytical continuation (see e.g. [26], [23] and references therein), by extensions of Parceval’s identity and by related axiomatic definitions (see [2], [5], [30], [11], [42] and references therein) or by means of the white noise analysis (see [22]), see also [46] for the discussion of path integral applied to the Dirac equation. These approaches still cover only a very restrictive class of potentials, for example, singular potentials were considered only by white noise analysis approach but only in one-dimensional case (see e.g. [6] and references therein). In the approaches of the second class, one tries to define the infinite-dimensional Feynmann integral as a genuine integral over a bona fide σ-additive measure on an appropriate space of trajectories. The first attempt made in [19] to construct such a measure was erronious and led to understanding that there is no direct generalisation of Wiener measure that can give an analog of FeynmanKac formula for the case of Schrodinger operators. A correct construction of the Feynman integral in terms of the Wiener measure was proposed in [15] and was based on the idea of the rotation of the classical trajectories in complex

•Jan 1, 2001•2 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 Algorithms and Complexity for Certain Continuous and Related Discrete Problems

Kwas, Marek

The thesis contains an analysis of two computational problems. The first problem is discrete quantum Boolean summation. This problem is a building block of quantum algorithms for many continuous problems, such as integration, approximation, differential equations and path integration. The second problem is continuous multivariate Feynman-Kac path integration, which is a special case of path integration. The quantum Boolean summation problem can be solved by the quantum summation (QS) algorithm of Brassard, Hí yer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function. We improve the error bound of Brassard et al. for the worst-probabilistic setting. Our error bound is sharp. We also present new sharp error bounds in the average-probabilistic and worst-average settings. Our average-probabilistic error bounds prove the optimality of the QS algorithm for a certain choice of its parameters. The study of the worst-average error shows that the QS algorithm is not optimal in this setting; we need to use a certain number of repetitions to regain its optimality. The multivariate Feynman-Kac path integration problem for smooth multivariate functions suffers from the provable curse of dimensionality in the worst-case deterministic setting, i.e., the minimal number of function evaluations needed to compute an approximation depends exponentially on the number of variables. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the minimal number of function evaluations and/or quantum queries required to compute an approximation depends only polynomially on the reciprocal of the desired accuracy and has a bound independent of the number of variables. The exponents of these polynomials are 2 in the randomized setting and 1 in the quantum setting. These exponents can be lowered at the expense of the dependence on the number of variables. Hence, the quantum setting yields exponential speedup over the worst-case deterministic setting, and quadratic speedup over the randomized setting.

•Jan 1, 2005•3 citations

Tractability Properties of High-Dimensional Integration and Star Discrepancy / submitted by Andreas Thoma

Andreas Thoma

•Jan 1, 2018•0 citations

High dimensional integration: New weapons fighting the curse of dimensionality

Peter Zinterhof

The approximate computation of the definite integral of a function of several variables is one of the basic problems of numerical analysis. The problem is hard because of the so called “curse of dimensionality”. This curse consists of the following: applying an integration rule with N nodes to an univariate function, you will get an integration error, say, ε> 0. Applying

Physics of Particles and Nuclei Letters•May 1, 2008•3 citations
Introduction There has been an increasing interest in studying computational aspects of high dimensional problems. Such problems are defined on spaces of functions of d variables and occur in many applications, with d that can be hundreds or even thousands. Examples include: • High dimensional integrals or path integrals with respect to the Wiener measure . These are important for many applications, in particular, in physics and in finance. High dimensional integrals also occur when we want to compute certain parameters of stochastic processes. Moreover, path integrals arise as solutions of partial differential equations given, for example, by the Feynman–Kac formula . See [25, 40, 66, 82, 85, 91]. • Global optimization where we need to compute the (global) minimum of a function of d variables. This occurs in many applications, for example, in pattern recognition and in image processing , see [97], or in the modelling and prediction of the geometry of proteins, see [45]. Simulated annealing strategies and genetic algorithms are often used, as well as smoothing techniques and other stochastic algorithms, see [10] and [74]. Some error bounds for deterministic and stochastic algorithms can be found in [42, 43, 44, 48, 53]. • The Schrödinger equation for m > 1 particles in ℝ 3 is a d = 3m -dimensional problem.
The goal of this workshop was to bring together researchers from different communities working on computational aspects of continuous problems. Continuous computational problems arise in many areas of science and engineering. Examples include path and multivariate integration, function approximation, optimization, as well as differential, integral, and operator equations. Understanding the complexity of such problems and constructing efficient algorithms is both important and challenging. The workshop was of a very interdisciplinary nature with invitees from, e.g., computer science, numerical analysis, discrete, applied, and pure mathematics, physics, statistics, and scientific computation. Many of the lectures were presented by Ph.D. students. Compared to earlier meetings, several very active research areas received more emphasis. These include Quantum Computing, Complexity and Tractability of high-dimensional problems, Stochastic Computation, and Quantization, which was an entirely new field for this workshop. Due to strong connections between the topics treated at this workshop many of the participants initiated new cooperations and research projects. For more details, see the pdf-file with the same title.
(and its generalisations that include magnetic fields) can be roughly divided into two classes. In the aproaches of the first class that we shall not discuss here in detail the Feynman integral is not supposed to be a genuine integral, but is specified as some generalised functional on an appropriate space of functions, which can be defined, for example, as the limit of certain discrete approximations (see e.g. [16], [44] and more recent papers [24], [25], [34]), by means of analytical continuation (see e.g. [26], [23] and references therein), by extensions of Parceval’s identity and by related axiomatic definitions (see [2], [5], [30], [11], [42] and references therein) or by means of the white noise analysis (see [22]), see also [46] for the discussion of path integral applied to the Dirac equation. These approaches still cover only a very restrictive class of potentials, for example, singular potentials were considered only by white noise analysis approach but only in one-dimensional case (see e.g. [6] and references therein). In the approaches of the second class, one tries to define the infinite-dimensional Feynmann integral as a genuine integral over a bona fide σ-additive measure on an appropriate space of trajectories. The first attempt made in [19] to construct such a measure was erronious and led to understanding that there is no direct generalisation of Wiener measure that can give an analog of FeynmanKac formula for the case of Schrodinger operators. A correct construction of the Feynman integral in terms of the Wiener measure was proposed in [15] and was based on the idea of the rotation of the classical trajectories in complex
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.
The thesis contains an analysis of two computational problems. The first problem is discrete quantum Boolean summation. This problem is a building block of quantum algorithms for many continuous problems, such as integration, approximation, differential equations and path integration. The second problem is continuous multivariate Feynman-Kac path integration, which is a special case of path integration. The quantum Boolean summation problem can be solved by the quantum summation (QS) algorithm of Brassard, Hí yer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function. We improve the error bound of Brassard et al. for the worst-probabilistic setting. Our error bound is sharp. We also present new sharp error bounds in the average-probabilistic and worst-average settings. Our average-probabilistic error bounds prove the optimality of the QS algorithm for a certain choice of its parameters. The study of the worst-average error shows that the QS algorithm is not optimal in this setting; we need to use a certain number of repetitions to regain its optimality. The multivariate Feynman-Kac path integration problem for smooth multivariate functions suffers from the provable curse of dimensionality in the worst-case deterministic setting, i.e., the minimal number of function evaluations needed to compute an approximation depends exponentially on the number of variables. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the minimal number of function evaluations and/or quantum queries required to compute an approximation depends only polynomially on the reciprocal of the desired accuracy and has a bound independent of the number of variables. The exponents of these polynomials are 2 in the randomized setting and 1 in the quantum setting. These exponents can be lowered at the expense of the dependence on the number of variables. Hence, the quantum setting yields exponential speedup over the worst-case deterministic setting, and quadratic speedup over the randomized setting.