Quantum and classical algorithms for nonlinear unitary dynamics

Abstract

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⟩}{dt}=A|u⟩+B|u{⟩}^{\otimes 2}$ 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\Vert B\Vert )}$ 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.

References in corpus (15)

• Quantum algorithm for solving linear systems of equations
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Hamiltonian simulation with nearly optimal dependence on all parameters
• High-order quantum algorithm for solving linear differential equations
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Koopman-von Neumann Approach to Quantum Simulation of Nonlinear Classical Dynamics
• Improved quantum algorithms for linear and nonlinear differential equations
• A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment
• A quantum algorithm to solve nonlinear differential equations
• Optimal state discrimination and unstructured search in nonlinear quantum mechanics
• Quantum algorithm for time-dependent differential equations using Dyson series
• Quantum Algorithms for Nonlinear Dynamics: Revisiting Carleman Linearization with No Dissipative Conditions

Cited by in corpus (2)

• A time-marching quantum algorithm for simulation of the nonlinear Lorenz dynamics
• Solving the Nonlinear Vlasov Equation on a Quantum Computer