arXiv:quant-ph/0510045AbstractReferencesReviewsResources
Almost Optimal Solution of Initial-Value Problems by Randomized and Quantum Algorithms
Published 2005-10-06, updated 2006-10-09Version 2
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.
Comments: 16 pages, minor presentation changes
Journal: Journal of Complexity 22 (2006), 676-690
Categories: quant-ph
Tags: journal article
Related articles: Most relevant | Search more
Acceleration of quantum algorithms using three-qubit gates
Five Quantum Algorithms Using Quipper
Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning