Fault-tolerant quantum computers are expected to excel in simulating unitary dynamics, such as the dynam-ics of a quantum state under a Hamiltonian. Most applications in scientific and engineering computations involve non-unitary and/or nonlinear dynamics. Therefore, efficient quantum algorithms are the key for un-locking the full potential of quantum computers to achieve comparable speedup in these general tasks. First, we propose a simple method for simulating a general class of non-unitary dynamics as a linear com-bination of Hamiltonian simulation (LCHS) problems. The LCHS method can achieve optimal cost in terms of state preparation. Second, we give the first efficient (polynomial time) quantum algorithm for nonlinear differential equations with sufficiently strong dissipation. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in the evolution time. Our work shows that fault-tolerant quantum computing can potentially address complex non-unitary and nonlinear phenomena in natural and data sciences with provable efficiency.

1_jliu-poster.pdf