  Quantum algorithms for Hamiltonian simulation and linear differential
equations more generally have provided promising exponential speed-ups over
classical computers on a set of problems with high real-world interest.
However, extending this to a nonlinear problem has proven challenging, with
exponential lower bounds having been demonstrated for the time scaling. We
provide a quantum algorithm matching these bounds. Specifically, we find that
for a non-linear differential equation of the form $\frac{d|u\rangle}{dt} =
A|u\rangle + B|u\rangle^{\otimes2}$ for evolution of time $T$, error tolerance
$\epsilon$ and $c$ dependent on the strength of the nonlinearity, the number of
queries to the differential operators that approaches the scaling of the
quantum lower bound of $e^{o(T\|B\|)}$ queries in the limit of strong
non-linearity. Finally, we introduce a classical algorithm based on the Euler
method allowing comparably scaling to the quantum algorithm in a restricted
case, as well as a randomized classical algorithm based on path integration
that acts as a true analogue to the quantum algorithm in that it scales
comparably to the quantum algorithm in cases where sign problems are absent.
