Young Measure Based Quantum Linear Programming Algorithms for Nonlinear/Stochastic Multiscale Partial Differential Equations and Homogenization

We study quantum algorithms for nonlinear and stochastic homogenization via a Young-measure based linear programming (LP) formulation, which lifts the nonlinear problem to a linear one in higher dimensions by treating the microscale, the gradient, and possible random variables as independent variables, thereby capturing effective macroscopic quantities without directly resolving fine-scale oscillations. The resulting LP is large but structured, and its high-dimensional nature creates regimes in which quantum LP solvers outperform direct classical solvers: in the deterministic setting, polynomial quantum speedup arises when moderate homogenized accuracy suffices; in the stochastic setting, encoding all random realizations simultaneously in a single LP yields a quantum square-root reduction in stochastic sampling cost that grows with the number of random variables. Regularity or sparsity of the Young measure may further extend these advantages to fine-scale accuracy. Numerical experiments on one- and two-dimensional benchmarks confirm the correctness of the Young-measure LP formulation.