Quantum algorithms for viscosity solutions to nonlinear Hamilton–Jacobi equations based on an entropy penalization method

Abstract

We present a framework for efficient extraction of the viscosity solutions of nonlinear Hamilton–Jacobi equations with convex Hamiltonians. These viscosity solutions play a central role in areas such as front propagation, mean-field games, optimal control, machine learning, and a direct application to the forced Burgers’ equation. Our method is based on an entropy penalization method which generalizes the Cole–Hopf transform from quadratic to general convex Hamiltonians, allowing an approximation of viscous Hamilton–Jacobi dynamics by a discrete-time linear dynamics which approximates a linear heat-like parabolic equation, and thus can also extend to continuous-time dynamics. This makes the method suitable for quantum simulation. The validity of these results hold for arbitrary nonlinearity that correspond to convex Hamiltonians, and for arbitrarily long times, thus obviating a chief obstacle in most quantum algorithms for nonlinear partial differential equations. We provide quantum algorithms—both analog and digital—for extracting pointwise values, gradients, minima, and function evaluations at the minimizer of the viscosity solution, without requiring nonlinear updates or full state reconstruction.