We construct quantum algorithms to compute physical observables of nonlinear PDEs with M initial data. Based on an exact mapping between nonlinear and linear PDEs using the level set method, these new quantum algorithms for nonlinear Hamilton-Jacobi and scalar hyperbolic PDEs can be performed with a computational cost that is independent of M, for arbitrary nonlinearity. Depending on the details of the initial data, it can also display up to exponential advantage in both the dimension of the PDE and the error in computing its observables. For general nonlinear PDEs, quantum advantage with respect to M is possible in the large M limit.
We construct quantum algorithms to compute physical observables of nonlinear PDEs with M initial data. Based on an exact mapping between nonlinear and linear PDEs using the level set method, these new quantum algorithms for nonlinear Hamilton-Jacobi and scalar hyperbolic PDEs can be performed with a computational cost that is independent of M, for arbitrary nonlinearity. Depending on the details of the initial data, it can also display up to exponential advantage in both the dimension of the PDE and the error in computing its observables. For general nonlinear PDEs, quantum advantage with respect to M is possible in the large M limit.
Many nonlinear PDEs have singular or oscillatory solutions or may exhibit physical instabilities or uncertainties. This requires a suitable concept of physically relevant generalized solutions. Dissipative measure-valued solutions have been an effective analytical tool to characterize PDE behavior in such singular regimes. They have also been used to characterize limits of standard numerical schemes on classical computers. The measure-valued formulation of a nonlinear PDE yields an optimization problem with a linear cost functional and linear constraints, which can be formulated as a linear programming problem. However, this linear programming problem can suffer from the curse of dimensionality. In this article, we propose solving it using quantum linear programming (QLP) algorithms and discuss whether this approach can reduce costs compared to classical algorithms. We show that some QLP algorithms, such as the quantum central path algorithm, have up to polynomial advantage over the classical interior point method. For problems where one is interested in the dissipative weak solution, namely the expected values of the Young measure, we show that the QLP algorithms offer no advantage over direct classical solvers. Moreover, for random PDEs, there can be up to polynomial advantage in obtaining the Young measure over direct classical PDE solvers. This is a significant advantage over standard PDE solvers, since the Young measure provides a more detailed description of the solution. We also propose some open questions for future development in this direction.
Structural mechanics is commonly modeled by (systems of) partial differential equations (PDEs). Except for very simple cases where analytical solutions exist, the use of numerical methods is required to find approximate solutions. However, for many problems of practical interest, the computational cost of classical numerical solvers running on classical, that is, silicon-based computer hardware, becomes prohibitive. Quantum computing, though still in its infancy, holds the promise of enabling a new generation of algorithms that can execute the most cost-demanding parts of PDE solvers up to exponentially faster than classical methods, at least theoretically. Also, increasing research and availability of quantum computing hardware spurs the hope of scientists and engineers to start using quantum computers for solving PDE problems much faster than classically possible. This work reviews the contributions that deal with the application of quantum algorithms to solve PDEs in structural mechanics. The aim is not only to discuss the theoretical possibility and extent of advantage for a given PDE, boundary conditions and input/output to the solver, but also to examine the hardware requirements of the methods proposed in literature.
Quantum algorithms for nonlinear partial differential equations remain challenging because nonlinear dynamics are not directly amenable to unitary quantum simulation. Building on the level-set formulation, we construct a quantum algorithm and provide an explicit gate-level implementation for solving scalar conservation laws. The nonlinear equation is first lifted to a linear Liouville equation, discretized by finite differences, and then embedded into a unitary evolution through Schrödingerisation. We further develop quantum procedures for estimating relevant observables from the evolved state. Error bounds and gate-complexity estimates are established for the complete algorithm. The resulting complexity comparison demonstrates a quantum advantage for observable estimation in sufficiently high spatial dimensions, under standard assumptions on state preparation and oracle access. Finally, numerical experiments validate the accuracy, multidimensional applicability, and predicted scaling of the proposed method.
A variational quantum algorithm for numerically solving partial differential equations (PDEs) on a quantum computer was proposed by Lubasch et al. [Phys. Rev. A 101, 010301(R) (2020)]. In this paper we generalize the method introduced by Lubasch et al. to cover a broader class of nonlinear PDEs as well as multidimensional PDEs and study the performance of the variational quantum algorithm on several example equations. Specifically, we show via numerical simulations that the algorithm can solve instances of the single-asset Black-Scholes equation with a nontrivial nonlinear volatility model, the double-asset Black-Scholes equation, the Buckmaster equation, and the deterministic Kardar-Parisi-Zhang equation. Our simulations use up to n=12 Ansatz qubits, computing PDE solutions with 2n grid points. We also perform proof-of-concept demonstrations with a trapped-ion quantum processor from IonQ [Nat. Commun. 10, 5464 (2019)], showing accurate computation of two representative expectation values needed for the calculation of a single time step of the nonlinear Black-Scholes equation. Through our classical simulations and demonstrations on quantum hardware, we identify and discuss several open challenges for using quantum variational methods to solve PDEs in a regime with a large number (much greater than 220) of grid points, but also a practical number of gates per circuit and circuit shots.
Most problems in uncertainty quantification, despite its ubiquitousness in scientific computing, applied mathematics and data science, remain formidable on a classical computer. For uncertainties that arise in partial differential equations (PDEs), large numbers M>>1 of samples are required to obtain accurate ensemble averages. This usually involves solving the PDE M times. In addition, to characterise the stochasticity in a PDE, the dimension L of the random input variables is high in most cases, and classical algorithms suffer from curse-of-dimensionality. We propose new quantum algorithms for PDEs with uncertain coefficients that are more efficient in M and L in various important regimes, compared to their classical counterparts. We introduce transformations that transfer the original d-dimensional equation (with uncertain coefficients) into d+L (for dissipative equations) or d+2L (for wave type equations) dimensional equations (with certain coefficients) in which the uncertainties appear only in the initial data. These transformations also allow one to superimpose the M different initial data, so the computational cost for the quantum algorithm to obtain the ensemble average from M different samples is then independent of M, while also showing potential advantage in d, L and precision in computing ensemble averaged solutions or physical observables.
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity p o l y ( 1 / ϵ ) , where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be p o l y ( d , log ( 1 / ϵ ) ) , where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.