Quantum Homotopy Algorithm for Nonlinear Flow Problems

Quantum algorithms that solve nonlinear flow problems are challenging to discover but critical to enhancing the practical usefulness of quantum computing. In this work, we introduce a near-optimal and end-to-end quantum algorithm to solve time-dependent, dissipative, and nonlinear PDEs. We embed the PDEs in a truncated, high-dimensional linear space by developing a novel method of quantum homotopy. The linearized system is discretized using finite-difference methods and subsequently solved by a time-marching, compact quantum algorithm based on linear combination of unitaries. The algorithm's complexity offers improvement over earlier methods in its dependence over matrix operators and amplitude norms, condition number, simulation time, and accuracy. We provide a general embedding strategy and prove the bounds on stability criteria, accuracy, gate counts and query complexity. A physically motivated measure of nonlinearity is connected to a parameter that is similar to the flow Reynolds number. We illustrate the embedding scheme with numerical simulations of a one-dimensional Burgers problem. This work reveals the potential of a hybrid quantum algorithm for simulating practical and nonlinear phenomena on near-term, fault-tolerant quantum devices.