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

Dagstuhl Seminar Proceedings

04401 Summary – Algorithms and Complexity for Continuous Problems

Thomas Müller-Gronbach, Erich Novak, Knut Petras, Joseph F. Traub

Published Jan 1, 2005• 0 citations
Publisher

Abstract

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.

DOI
10.4230/dagsemproc.04401.2

Related papers

Quantum Algorithms and Complexity for Continuous Problems

Anargyros Papageorgiou, Joseph F. Traub

Most continuous mathematical formulations arising in science and engineering can only be solved numerically and therefore approximately. We shall always assume that we're dealing with a numerical approximation to the solution. There are two major motivations for studying quantum algorithms and complexity for continuous problems. 1. Are quantum computers more powerful than classical computers for important scientific problems? How much more powerful? 2. Many important scientific and engineering problems have continuous formulations. To answer the first question we must know the classical computational complexity of the problem. Knowing the classical complexity of a continuous problem we obtain the quantum computation speedup if we know the quantum complexity. If we know an upper bound on the quantum complexity through the cost of a particular quantum algorithm then we can obtain a lower bound on the quantum speedup. Regarding the second motivation, in this article we'll report on high-dimensional integration, path integration, Feynman path integration, the smallest eigenvalue of a differential equation, approximation, partial differential equations, ordinary differential equations and gradient estimation. We'll also briefly report on the simulation of quantum systems on a quantum computer.

arXiv:0712.1211•Dec 7, 2007•0 citations

When are integration and discrepancy tractable?

Erich Novak, H. Woźniakowski

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.

Cambridge University Press eBooks•May 17, 2001•68 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

Many-Body Quantum Systems and Effective Theories

Christian Hainzl, Benjamin Schlein, Robert Seiringer

In the last years, substantial progress has been made in many areas of mathematical physics. The goal of this workshop was to bring together researchers working on analytic and probabilistic aspects of many-body quantum systems and quantum statistical mechanics, to discuss recent developments, exchange ideas and propose new challenges and research directions. Among the questions addressed during the workshop were the derivation of effective equations, the analysis of physically interesting nonlinear partial differential equations emerging from microscopic theories, the study of open quantum systems in and out of equilibrium, and the investigation of the ground state properties and of the dynamics of quantum spin systems.

Oberwolfach Reports•Apr 22, 2017•0 citations

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

Mathematical Methods in Quantum Chemistry

Quantum chemistry focuses on modelling and simulating the behaviour of molecular systems using the fundamental principles of quantum mechanics. However, the underlying equations, such as the Schrödinger equation for computing the ground state of $N$ electrons, which is a partial differential equation defined on $\mathbb{R}^{3N}$, suffer from the curse of dimensionality. As a result, simulating even moderately sized molecules demands advanced techniques in analysis, approximation and reduced-order modelling for overcoming the naive computational complexity. In this workshop, the rapidly growing mathematical community working in the field together with several quantum chemists and physicists were gathered to discuss recent advances in areas such as (1) the mathematical and numerical analysis of standard models used in the field, including Density Functional Theory, Coupled Cluster, and the Density Matrix Renormalization Group (2) the development of efficient numerical methods, relying e.g. on the development of error bounds and (3) the opportunities of recent data-driven methods towards the approximation of wavefunctions or density matrices.

•Jan 1, 2025•0 citations
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.
Most continuous mathematical formulations arising in science and engineering can only be solved numerically and therefore approximately. We shall always assume that we're dealing with a numerical approximation to the solution. There are two major motivations for studying quantum algorithms and complexity for continuous problems. 1. Are quantum computers more powerful than classical computers for important scientific problems? How much more powerful? 2. Many important scientific and engineering problems have continuous formulations. To answer the first question we must know the classical computational complexity of the problem. Knowing the classical complexity of a continuous problem we obtain the quantum computation speedup if we know the quantum complexity. If we know an upper bound on the quantum complexity through the cost of a particular quantum algorithm then we can obtain a lower bound on the quantum speedup. Regarding the second motivation, in this article we'll report on high-dimensional integration, path integration, Feynman path integration, the smallest eigenvalue of a differential equation, approximation, partial differential equations, ordinary differential equations and gradient estimation. We'll also briefly report on the simulation of quantum systems on a quantum computer.
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 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.
In the last years, substantial progress has been made in many areas of mathematical physics. The goal of this workshop was to bring together researchers working on analytic and probabilistic aspects of many-body quantum systems and quantum statistical mechanics, to discuss recent developments, exchange ideas and propose new challenges and research directions. Among the questions addressed during the workshop were the derivation of effective equations, the analysis of physically interesting nonlinear partial differential equations emerging from microscopic theories, the study of open quantum systems in and out of equilibrium, and the investigation of the ground state properties and of the dynamics of quantum spin systems.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Quantum chemistry focuses on modelling and simulating the behaviour of molecular systems using the fundamental principles of quantum mechanics. However, the underlying equations, such as the Schrödinger equation for computing the ground state of NNN electrons, which is a partial differential equation defined on R3N\mathbb{R}^{3N}R3N, suffer from the curse of dimensionality. As a result, simulating even moderately sized molecules demands advanced techniques in analysis, approximation and reduced-order modelling for overcoming the naive computational complexity. In this workshop, the rapidly growing mathematical community working in the field together with several quantum chemists and physicists were gathered to discuss recent advances in areas such as (1) the mathematical and numerical analysis of standard models used in the field, including Density Functional Theory, Coupled Cluster, and the Density Matrix Renormalization Group (2) the development of efficient numerical methods, relying e.g. on the development of error bounds and (3) the opportunities of recent data-driven methods towards the approximation of wavefunctions or density matrices.