  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.
