Quantum algorithms for general nonlinear dynamics based on the Carleman embedding
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:32QQ4L6Krecord.jsonopen to challenge →
read the original abstract
Important nonlinear dynamics, such as those found in plasma and fluid systems, are typically hard to simulate on classical computers. Thus, if fault-tolerant quantum computers could efficiently solve such nonlinear problems, it would be a transformative change for many industries. In a recent breakthrough [Liu et al., PNAS 2021], the first efficient quantum algorithm for solving nonlinear differential equations was constructed, based on a single condition $R<1$, where $R$ characterizes the ratio of nonlinearity to dissipation. This result, however, is limited to the class of purely dissipative systems with negative log-norm, which excludes application to many important problems. In this work, we correct technical issues with this and other prior analysis, and substantially extend the scope of nonlinear dynamical systems that can be efficiently simulated on a quantum computer in a number of ways. Firstly, we extend the existing results from purely dissipative systems to a much broader class of stable systems, and show that every quadratic Lyapunov function for the linearized system corresponds to an independent $R$-number criterion for the convergence of the Carlemen scheme. Secondly, we extend our stable system results to physically relevant settings where conserved polynomial quantities exist. Finally, we provide extensive results for the class of non-resonant systems. With this, we are able to show that efficient quantum algorithms exist for a much wider class of nonlinear systems than previously known, and prove the BQP-completeness of nonlinear oscillator problems of exponential size. In our analysis, we also obtain several results related to the Poincar\'{e}-Dulac theorem and diagonalization of the Carleman matrix, which could be of independent interest.
This paper has not been read by Pith yet.
Forward citations
Cited by 10 Pith papers
-
Nonlinear semigroups with unbounded generators under Carleman linearization
Carleman embedding turns nonlinear semigroups into linear ones whose convergence follows from dissipativity and Trotter-Kato approximation, even for unbounded generators and as 1-integrated semigroups.
-
Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation
A new LCNU-to-LCU decomposition enables a generalized quantum framework for Carleman-linearized polynomial systems like the lattice Boltzmann equation, with Ns scaling as O(α² Q²) independent of spatial and temporal d...
-
Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation
A new LCNU-to-LCU decomposition yields a quantum framework for Carleman-linearized lattice Boltzmann equations whose term count scales as O(α² Q²) and is independent of spatial or temporal grid points.
-
Fixing Divergence in Carleman Linearization via Analytical Continuation
A Möbius conformal map and regularized incomplete beta function fix the long-time divergence of Carleman linearization for logistic, KPP-Fisher, and phase-field equations.
-
Quantum algorithms for stochastic nonlinear differential equations
Quantum algorithm for N-dimensional stochastic nonlinear differential equations with quadratic drift and dissipation approximates low-order correlation expectations at polylog(N) cost under norm-preserving drift conditions.
-
Structure-Preserving Quantum Method of Lines for Evolutionary PDEs with Mixed Boundary Conditions
Presents structure-preserving quantum method-of-lines algorithms for parabolic and hyperbolic PDEs with mixed BCs, using Coons interpolation, similarity transforms, and explicit quantum circuit constructions with comp...
-
Quantum Algorithms for Nonlinear Differential Equations via Pivot-Shifted Carleman Linearization
Pivot-shifted Carleman linearization with Lyapunov transform enables logarithmic truncation and removes initial-condition lower bounds for quantum simulation of a broader class of nonlinear ODEs.
-
Quantum Koopman Algorithms
Quantum Koopman Algorithms define an observable-space quantum framework for simulating linear quantum and nonlinear classical dynamics with polylog gate costs in some cases.
-
Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation
Presents LCNU-plus-embedding data loading for any polynomial Carleman-linearized autonomous system and applies it to the 3D LBE, yielding Ns ~ O(α²Q²) terms and explicit T-gate resource estimates for two solvers.
-
Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation
A matrix decomposition into linear combinations of non-unitaries produces an LCU for any Carleman-linearized polynomial system and yields an O(α² Q²) term count for the 3D lattice Boltzmann equation independent of spa...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.