Schrödingerization based quantum algorithms for regularized Wasserstein proximal operators

Abstract

We develop a quantum algorithm for the regularized Wasserstein proximal operator, which is a fundamental tool in optimal transport and mean-field games. The regularization introduces a small diffusive term into the continuity equation of the Benamou-Brenier formulation, which results in a forward-backward PDE system consisting of a Fokker-Planck equation and a viscous Hamilton-Jacobi equation with a quadratic Hamiltonian. Through the Cole-Hopf transformation, both equations are converted to forward heat equations, whose coupling requires a Hadamard division to prepare the initial data for the second heat equation and a Hadamard product to recover the terminal density. We solve these heat equations via the Schrödingerization method and implement the Hadamard division and product operations using simple matrix-vector multiplication representations. The complete quantum algorithm prepares an $\epsilon$-approximation of the terminal density state with $\mathcal{O}(d{N}_{x}T{\log }^2(1/\epsilon ))$ query complexity, up to constants depending on the potential and initial density, where $d$ is the spatial dimension, $N_x$ is the number of grid points per spatial dimension and $T$ is the evolution time. The complexity depends only {\it linearly} on $d{N}_x$, yielding an {\it exponential} speedup over classical methods, whose cost scales as $N_x^d$ per time step. Numerical experiments validate the effectiveness of the proposed algorithm.

quantum algorithm for Wasserstein proximal operator