  Quantum computers have the potential to efficiently solve nonlinear ordinary
differential equations (ODEs), which play a crucial role in various industries
and scientific fields. However, it remains unclear which nonlinear ODEs, and
under what assumptions, can achieve exponential speedup using a quantum
computer. In this work, we introduce a class of nonlinear ODEs, called quantum
solvable ODEs, that can be efficiently solved on quantum computers, where the
efficiency is defined as solving the ODE with computational complexity of
polylog(N) for a number N of variables in ODEs. Specifically, we employ
Koopman-von-Neumann linearization to map nonliner ODEs to Hamiltonian dynamics
and find conditions where the norm of the mapped Hamiltonian is preserved and
the mapped Hamiltonian is sparse. This allows us to use the optimal Hamiltonian
simulation technique for solving the quantum solvable ODEs with polylog(N)
overhead. We further show that quantum solvable ODEs include a wide range of
nonlinear ODEs, such as the extended short-range Kuramoto model. Since this is
the first concrete example of solving nonlinear differential equations with
exponential quantum speedup, these findings contribute significantly to the
application of quantum computers in solving nonlinear problems.

Quantum Physics