Almost optimal solution of initial-value problems by randomized and quantum algorithms
From MaRDI portal
Publication:855897
DOI10.1016/J.JCO.2006.03.001zbMATH Open1111.65063arXivquant-ph/0510045OpenAlexW2952282722MaRDI QIDQ855897FDOQ855897
Publication date: 7 December 2006
Published in: Journal of Complexity (Search for Journal in Brave)
Abstract: We establish essentially optimal bounds on the complexity of initial-value problems in the randomized and quantum settings. For this purpose we define a sequence of new algorithms whose error/cost properties improve from step to step. These algorithms yield new upper complexity bounds, which differ from known lower bounds by only an arbitrarily small positive parameter in the exponent, and a logarithmic factor. In both the randomized and quantum settings, initial-value problems turn out to be essentially as difficult as scalar integration.
Full work available at URL: https://arxiv.org/abs/quant-ph/0510045
Recommendations
- Improved bounds on the randomized and quantum complexity of initial-value problems
- Randomized and quantum algorithms yield a speed-up for initial-value problems
- The randomized complexity of initial value problems
- Randomized and quantum algorithms for solving initial-value problems in ordinary differential equations of order \(k\)
- Complexity of initial-value problems for ordinary differential equations of order \(k\)-different models of computation
Complexity and performance of numerical algorithms (65Y20) Quantum computation (81P68) Nonlinear ordinary differential equations and systems (34A34) Numerical methods for initial value problems involving ordinary differential equations (65L05) Quantum stochastic calculus (81S25)
Cites Work
- Quantum summation with an application to integration.
- Randomized and quantum algorithms yield a speed-up for initial-value problems
- Title not available (Why is that?)
- Optimal solution of ordinary differential equations
- Title not available (Why is that?)
- Improved bounds on the randomized and quantum complexity of initial-value problems
Cited In (35)
- Turbulence theories and statistical closure approaches
- Solving Burgers' equation with quantum computing
- On the optimal robust solution of IVPs with noisy information
- Complexity of initial-value problems for ordinary differential equations of order \(k\)-different models of computation
- Complexity of the derivative-free solution of systems of IVPs with unknown singularity hypersurface
- Optimal adaptive solution of initial-value problems with unknown singularities
- On the randomized solution of initial value problems
- On the quantum and randomized approximation of linear functionals on function spaces
- Mathematical analysis of a randomized method for fractional Carathéodory type equation with time-irregular coefficients
- Randomized and quantum complexity of nonlinear two-point BVPs
- On a randomized backward Euler method for nonlinear evolution equations with time-irregular coefficients
- Optimality proofs of quantum weight decision algorithms
- The quantum query complexity of elliptic PDE
- Optimal solution of a class of non-autonomous initial-value problems with unknown singularities
- Randomized and quantum algorithms yield a speed-up for initial-value problems
- Existence, uniqueness and approximation of solutions to Carathéodory delay differential equations
- Optimal adaptive solution of piecewise regular systems of IVPs with unknown switching hypersurface
- Randomized and quantum algorithms for solving initial-value problems in ordinary differential equations of order \(k\)
- Complexity of parametric initial value problems in Banach spaces
- Quantum lower bounds by entropy numbers
- The randomized complexity of initial value problems
- Optimal global approximation of SDEs with time-irregular coefficients in asymptotic setting
- A quantum algorithm for the lattice-Boltzmann method advection-diffusion equation
- On the Complexity of Parametric ODEs and Related Problems
- Improved bounds on the randomized and quantum complexity of initial-value problems
- Complexity of certain nonlinear two-point BVPs with Neumann boundary conditions
- Solving systems of IVPs with discontinuous derivatives-numerical experiments
- Simulating nonlinear radiation diffusion through quantum computing
- Error analysis of randomized Runge-Kutta methods for differential equations with time-irregular coefficients
- A note on the probabilistic stability of randomized Taylor schemes
- On the complexity of a two-point boundary value problem in different settings
- On the properties of the exceptional set for the randomized Euler and Runge-Kutta schemes
- Randomized Runge-Kutta method -- stability and convergence under inexact information
- On the randomized Euler schemes for ODEs under inexact information
- Strong approximation of solutions of stochastic differential equations with time-irregular coefficients via randomized Euler algorithm
This page was built for publication: Almost optimal solution of initial-value problems by randomized and quantum algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q855897)
