Quantum algorithm for nonlinear differential equations

The nonlinear Schr¨odinger equation

• For anti-Hermitian f without driving, the approach implements this dynamics using n >> m identical copies and linear Schrödinger evolution [11].Source: The nonlinear Schr¨odinger equation · p. 3
• Tracing out other copies gives each copy effective nonlinear Schrödinger dynamics at short times, with second- and higher-order deviations suppressed by 1/n.Source: The nonlinear Schr¨odinger equation · pp. 3–4
• The required discretized Trotter-step count grows quadratically with integration time t, since E^2 t^2/T must be small.Source: The nonlinear Schr¨odinger equation · p. 4
• For approximation error ǫ, n must significantly exceed T and satisfy E^2 t∆t m^2/n < ǫ; the required copy count also scales quadratically in t.Source: The nonlinear Schr¨odinger equation · p. 4
• Numerical integration breaks down when exponential amplification of wave-function deviations raises E^2 t∆t above O(ǫ).Source: The nonlinear Schr¨odinger equation · p. 4
• The equation is a mean-field model of weakly interacting systems in the same state; the Gross-Pitaevskii equation for bosons in a Bose-Einstein condensate is one example.Source: The nonlinear Schr¨odinger equation · pp. 4–5

Quantum solution to general nonlinear differential equations

• When f(x) is not anti-Hermitian, the solution cannot be embedded in a nonlinear Schrödinger equation, unlike the special anti-Hermitian case.The general setting encompasses equations such as Boltzmann and Navier–Stokes, as well as plasma hydrodynamics.Source: Quantum solution to general nonlinear… · p. 5
• The approach combines mean-field techniques for the nonlinear Schrödinger equation with methods from quantum linear differential-equation solvers [1] [2] to obtain a quantum solution to equation (1).Source: Quantum solution to general nonlinear… · p. 5
• The resulting quantum algorithm for nonlinear differential equations inherits the exponential quantum advantage of linear differential-equation solvers [1] [2].The paper presents it as a quantum solution to equation (1).Source: Quantum solution to general nonlinear… · p. 5

• The original method [1] maps a general linear differential equation to matrix inversion, which can be solved with a quantum linear systems algorithm [12-13].Source: Review of quantum linear differential… · p. 6
• The solution is discretized in time using Euler forward updates, with implicit methods such as Euler backward, Crank-Nicholson, or Runge-Kutta available when greater stability is needed [3].Source: Review of quantum linear differential… · p. 6
• A time-step register encodes the solution vectors and driving terms as unnormalized quantum history states, with each |xk⟩ representing the solution at step k.Source: Review of quantum linear differential… · p. 7
• The quantum linear systems algorithm takes A, the initial state, and driving terms as inputs and returns the history state; measurement and quantum post-processing [3] reveal solution features.Source: Review of quantum linear differential… · p. 7

Non-Hermitian nonlinear Schr¨odinger equation

• The quantum linear differential-equation solver constructs the desired history state without requiring its matrix A to be Hermitian, enabling a non-Hermitian Hamiltonian formulation of the nonlinear dynamics.The method uses the quantum linear systems algorithm to construct the history state corresponding to the solution.Source: Non-Hermitian nonlinear Schr¨odinger… · pp. 7–8
• Up to O(1/n), the non-Hermitian construction preserves a tensor-product history state that superposes tensor products of the nonlinear-equation solutions at different times.The stated approximation is to lowest order in 1/n.Source: Non-Hermitian nonlinear Schr¨odinger… · pp. 8–9
• The nonlinear Schrödinger approximation error is |E|^2 t Δt m^2/n, a factor of n below the numerical-integration error, which dominates overall.The approximation error arises from the nonlinear Schrödinger equation approximation; overall error is dominated by numerical-integration discretization.Source: Non-Hermitian nonlinear Schr¨odinger… · pp. 8–9

Errors, stability, and range of applicability

• The presented algorithm uses lowest-order Trotterization, while higher-order Trotterization and higher-order implicit numerical methods are expected to improve error scaling.The authors describe this as the simplest version of the algorithm.Source: Errors, stability, and range of… · p. 9
• Approximations must break down when nonlinear growth amplifies errors enough to violate equation (19), limiting exponential speedup to times before that occurs.Otherwise, the solver could amplify exponentially small initial-wavefunction differences to solve NP-complete problems; the analogous issue occurs for linear equations with eigenvalues having positive real parts.Source: Errors, stability, and range of… · p. 9
• Long-time accuracy can be better than for the quantum linear solver with positive-real-part eigenvalues when nonlinear expansion directions change over time and produce no net exponential growth.The paper gives negative-sum Lyapunov exponents, which can yield fractal solutions such as strange attractors, as an example.Source: Errors, stability, and range of… · pp. 9–10
• The solver works best when the mean-field approximation remains valid throughout the investigated evolution and the underlying numerical method is accurate.Performance also varies with the nonlinear equation’s characteristics, notably its stability.Source: Errors, stability, and range of… · p. 10
• Exponential speedup requires a sparse tensor F with computable entries; locality and specified interactions provide this structure for Boltzmann and Navier-Stokes examples.For Boltzmann, the scattering interaction is spatially local and momentum-conserving; for Navier-Stokes, locality combined with momentum conservation yields sparse, computable tensors.Source: Errors, stability, and range of… · p. 10
• Plasma hydrodynamics also yields sparse, computable nonlinear terms because its equations involve local interactions and physical dynamics.These equations include charged-particle and electromagnetic-field dynamics.Source: Errors, stability, and range of… · pp. 10–11

Comparison to related work:

• Retaining all system copies at each step gives this approach quadratic scaling in T, unlike the earlier method [4], which discarded copies and scaled exponentially with T.For pairwise nonlinear interactions, the resources required by [4] scale as 2T.Source: Comparison to related work · p. 11
• Variational techniques do not supply the provable exponential speed-up given by this algorithm; another method uses the Madelung hydrodynamic approach [19].Source: Comparison to related work · p. 11
• A posted method [20] similarly induces single-system nonlinearity through a linear system over multiple copies, but uses classical Carleman rather than quantum nonlinear Schrödinger linearization.Source: Comparison to related work · p. 11

• The algorithm can in principle provide an exponential advantage over classical methods, scaling logarithmically with the dimension of the solution space.Source: Conclusion · p. 11
• Its logarithmic dimension scaling makes the method a candidate for high-dimensional problems such as Navier–Stokes and other nonlinear fluid or plasma systems.Source: Conclusion · pp. 11–12
• The method could be applied to continuous-variable quantum systems using techniques from.Source: Conclusion · p. 12
• Like quantum linear differential-equation solvers, it encodes the solution as a quantum history state, enabling post-processing [3] to extract spectral, component, and multiscale features.Source: Conclusion · p. 12

Supplementary material:

• Setting an added coordinate x0 initially to 1 and defining dx0/dt = 0 keeps it constant over time.This is how the supplement augments the original differential equation.Source: Supplementary material · p. 14
• The constant extra coordinate allows f(x) to include arbitrary polynomials in the x_j and their conjugates.The supplement presents this as a way to write an arbitrary m’th order polynomial in the form of the referenced equation.Source: Supplementary material · p. 14
• For m = 2, the supplement illustrates the construction with the monomial ¯x2.It states that a corresponding term is included in F, but the supplied passage does not show the term itself.Source: Supplementary material · p. 14

Normalization

• Under the action of the non-Hermitian operator, the variables are rescaled so that ˜x†˜x ≤ 1/2 during integration, and an additional dimension is added with real coefficient x_{d+1} obeying a nonlinear equation.Source: Normalization · pp. 14–15
• Expanding (1 − y)^−1/2 about y = 0 converges exponentially, so augmenting m by log(1/ε) maintains accuracy ε throughout integration.Source: Normalization · p. 15

Accuracy of the nonlinear Schr¨odinger equation

• At one time step, first-order terms match the discretized nonlinear dynamics, and second-order terms with disjoint index sets reproduce it exactly.Second-order terms whose index sets overlap represent potentially entangling dynamics that depart from the tensor-product solution.Source: Accuracy of the nonlinear Schr¨odinger… · pp. 15–16
• The approximation holds when n >> mT, with the number of copies larger than the number of time steps.Under this condition, the full dynamics produce an overall state approximately equal to the desired state.Source: Accuracy of the nonlinear Schr¨odinger… · p. 16
• For the m-fold density matrix, the fraction of terms causing departures from tensor-product form is approximately 2m^2/n; the associated ε1 error is O(|E|^2Δt^2m^2/n).Errors induced by entanglement and correlations are additive.Source: Accuracy of the nonlinear Schr¨odinger… · pp. 16–17
• For small m, nonlinear Schrödinger approximation errors are suppressed by a factor of n relative to first-order Trotterization errors.The comparison is to discretization errors for the first-order Trotterization of the Euler forward method.Source: Accuracy of the nonlinear Schr¨odinger… · p. 17