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:1712.03843 · Journal of Complexity

Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods

Robert J. Kunsch

Published Apr 25, 2018• 8 citations
arXivHTMLPDF
DOI
10.1016/j.jco.2018.04.002

Related papers

Quasi–Monte Carlo integration, discrepancy and reproducing kernel Hilbert spaces

Josef Dick, Friedrich Pillichshammer

Cambridge University Press eBooks•Sep 9, 2010•0 citations

Monte Carlo sampling of energy-constrained quantum superpositions in high-dimensional Hilbert spaces

Frank Hantschel, Boris V. Fine

arXiv:1102.0531•The European Physical Journal D•Apr 14, 2011•4 citations

High-Dimensional Function Approximation: Breaking the Curse with Monte Carlo Methods

Robert J. Kunsch

In this dissertation we study the tractability of the information-based complexity $n(\varepsilon,d)$ for $d$-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $d$. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the $L_{\infty}$-approximation of certain classes of $C^{\infty}$-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the $L_{\infty}$-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the $L_1$-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $\sqrt{d}$ only.

arXiv:1704.08213•Apr 26, 2017•17 citations

On the quantum and randomized approximation of linear functionals on function spaces

Boleslaw Z. Kacewicz

Quantum Information Processing•Aug 26, 2010•0 citations

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

Gowri Suryanarayana

The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.

•May 27, 2016•0 citations

Accelerating Convergence in Fock Space Quantum Monte Carlo Methods

Verena A. Neufeld, Alex J. W. Thom

The convergence of full configuration interaction quantum Monte Carlo (FCIQMC) is accelerated using a quasi-Newton propagation (QN) which can also be applied to coupled cluster Monte Carlo (CCMC). The computational scaling of this optimized propagation is, keeping the additional computational cost to a bare minimum. Its effects are investigated deterministically and stochastically on a model system, the uniform electron gas, with Hilbert space size up to 10 40, and shown to accelerate convergence of the instantaneous projected energy by over an order of magnitude in the FCIQMC test case. Its capabilities are then demonstrated with FCIQMC on an archetypical quantum chemistry problem, the chromium dimer, in an all-electron basis set with Hilbert space size of about 10 22 yielding highly accurate FCI energies.

arXiv:1910.05210•Journal of Chemical Theory and Computation•Jan 16, 2020•10 citations
In this dissertation we study the tractability of the information-based complexity n(ε,d)n(\varepsilon,d)n(ε,d) for ddd-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance ε>0\varepsilon>0ε>0 the complexity n(ε,d)n(\varepsilon,d)n(ε,d) grows exponentially in ddd. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the L∞L_{\infty}L∞​-approximation of certain classes of C∞C^{\infty}C∞-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the L∞L_{\infty}L∞​-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the L1L_1L1​-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance ε>0\varepsilon>0ε>0 the complexity n(ε,d)n(\varepsilon,d)n(ε,d) grows exponentially in d\sqrt{d}d​ only.
The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.
The convergence of full configuration interaction quantum Monte Carlo (FCIQMC) is accelerated using a quasi-Newton propagation (QN) which can also be applied to coupled cluster Monte Carlo (CCMC). The computational scaling of this optimized propagation is, keeping the additional computational cost to a bare minimum. Its effects are investigated deterministically and stochastically on a model system, the uniform electron gas, with Hilbert space size up to 10 40, and shown to accelerate convergence of the instantaneous projected energy by over an order of magnitude in the FCIQMC test case. Its capabilities are then demonstrated with FCIQMC on an archetypical quantum chemistry problem, the chromium dimer, in an all-electron basis set with Hilbert space size of about 10 22 yielding highly accurate FCI energies.