An official website of the United States government
Nonlinearity presents a significant challenge in developing quantum algorithms involving differential equations, prompting the exploration of various linearization techniques, including the well-known Carleman Linearization. Instead, this paper introduces the Koopman Spectral Linearization method tailored for nonlinear autonomous ordinary differential equations. This innovative linearization approach harnesses the interpolation methods and the Koopman Operator Theory to yield a lifted linear system. It promises to serve as an alternative approach that can be employed in scenarios where Carleman Linearization is traditionally applied. Numerical experiments demonstrate the effectiveness of this linearization approach for several commonly used nonlinear ordinary differential equations.
more »
« less
A General Method for Solving Systems of Nonlinear Differential Equations on a Quantum Annealer with Application to Molecular Dynamics
One of the most fundamental problems that has no efficient solutions on classical computers is simulation of quantum systems. It has been long hypothesized that quantum computing devices are naturally more suitable for this task, but many aspects of practical implementations of such simulations remain unknown. One particularly important kind of these simulations is the simulation of molecular dynamics, i.e. prediction of time evolution for a system of interacting particles. In this work we show how a quantum annealer can be used to carry out such simulations by solving differential equations of motion, on the example of the hydrogen molecule. Although the considered system is simple, our method is well scalable and can be readily applied to more complicated systems as annealers with larger number of qubits become available. Importantly, the method is general and can be used to solve arbitrary systems of ordinary non-linear differential equations, which can be helpful not only in the field of computational chemistry, but in many other fields as well.
more »
« less
- Award ID(s):
- 2102465
- PAR ID:
- 10503299
- Publisher / Repository:
- APS
- Date Published:
- Journal Name:
- APS March Meeting 2022, abstract id.G38.001
- ISSN:
- 2022APS..MARG38001G
- Format(s):
- Medium: X
- Location:
- Chicago, IL, USA
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic n-dimensional ordinary differential equations. Assuming R < 1 , where R is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity T 2 q poly ( log T , log n , log 1 / ϵ ) / ϵ , where T is the evolution time, ϵ is the allowed error, and q measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for R ≥ 2 . Finally, we discuss potential applications, showing that the R < 1 condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of R.more » « less
-
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.more » « less
-
Abstract Numerical solutions of Maxwell’s equations are indispensable for nanophotonics and electromagnetics but are constrained when it comes to large systems, especially multi-channel ones such as disordered media, aperiodic metasurfaces and densely packed photonic circuits where the many inputs require many large-scale simulations. Conventionally, before extracting the quantities of interest, Maxwell’s equations are first solved on every element of a discretization basis set that contains much more information than is typically needed. Furthermore, such simulations are often performed one input at a time, which can be slow and repetitive. Here we propose to bypass the full-basis solutions and directly compute the quantities of interest while also eliminating the repetition over inputs. We do so by augmenting the Maxwell operator with all the input source profiles and all the output projection profiles, followed by a single partial factorization that yields the entire generalized scattering matrix via the Schur complement, with no approximation beyond discretization. This method applies to any linear partial differential equation. Benchmarks show that this approach is 1,000–30,000,000 times faster than existing methods for two-dimensional systems with about 10,000,000 variables. As examples, we demonstrate simulations of entangled photon backscattering from disorder and high-numerical-aperture metalenses that are thousands of wavelengths wide.more » « less
-
Abstract The technologies used in the manipulation of light can be used to do analogue simulations of physical systems with wave-like equations of motion. This analogy is maximized by the use of all the degrees of freedom of light. The Helmholtz equation in physical optics and the Schodinger equation in quantum mechanics share the same mathematical form. We use this connection to prepare non-diffracting optical beams representing the spatial and temporal dynamics of a nonlinear physical system: the quantum pendulum. By using the propagation coordinate to represent time in the quantum problem, we are able to analogue-simulate quantum wavepacket dynamics. These manifest themselves in novel optical beams with rich three-dimensional structures, such as rotation and sloshing of the light's intensity as it propagates. Our experimental results agree very well with the predictions from quantum theory, thus demonstrating that our system can be used as a platform to simulate the quantum pendulum dynamics. This three-dimensional light-sculpting capability has the potential to impact fields such as manipulation with light and imaging.more » « less
