Search

In this paper, we present an efficient quantum algorithm to simulate nonlinear differential equations with polynomial vector fields of arbitrary (finite) degree on quantum platforms. Ordinary differential equations (ODEs) and partial differential equations (PDEs) arise extensively in science and engineering applications. Examples of ODE models include mechanics of rigid bodies, molecular dynamics, chemical kinetics, and epidemiology. Nonlinear PDEs arise in fluid dynamics, combustion, weather forecasting, structural mechanics, plasma dynamics, and finance to name a few. In practice, it is challenging to simulate such equations on classical computers due to high dimensionality, stiffness arising from multiple spatial/temporal scales, nonlinearities, and chaotic dynamics. Typically, high performance computing is used to mitigate computational challenges and involves approximations for tractability. For sparse n-dimensional linear ODEs, quantum algorithms have been developed which can produce a quantum state proportional to the solution in poly (log (n)) ) time using the quantum linear systems algorithm (QLSA). Recently, this framework was extended to systems of nonlinear ODEs with quadratic polynomial vector fields by applying Carleman linearization that enables the embedding of the quadratic system into an approximate linear form. A detailed complexity analysis was conducted which showed significant computational advantage under certain conditions. We present an extension of this algorithm to deal with systems of nonlinear ODEs with k-th degree polynomial vector fields for arbitrary (finite) values of k. The steps involve: (1) mapping the k-th degree polynomial ODE to a higher-dimensional quadratic polynomial ODE; (2) applying Carleman linearization to transform the quadratic ODE to an infinite-dimensional system of linear ODEs; (3) truncating and discretizing the linear ODE and solving using the forward Euler method and QLSA. Alternatively, one could apply Carleman linearization directly to the k-th degree polynomial ODE, resulting in a system of infinite-dimensional linear ODEs, and then apply step 3. This solution route can be computationally more efficient. We present detailed complexity analysis of the proposed algorithms and prove polynomial scaling of runtime on k. We demonstrate the computational framework on a numerical example. [ABSTRACT FROM AUTHOR]

In this paper, we propose algorithms for the graph isomorphism (GI) problem that are based on the eigendecompositions of the adjacency matrices. The eigenvalues of isomorphic graphs are identical. However, two graphs G A and G B can be isospectral but non-isomorphic. We first construct a GI testing algorithm for friendly graphs and then extend it to unambiguous graphs. We show that isomorphisms can be detected by solving a linear assignment problem (LAP). If the graphs possess repeated eigenvalues, which typically correspond to graph symmetries, finding isomorphisms is much harder. By repeatedly perturbing the adjacency matrices and by using properties of eigenpolytopes, it is possible to break symmetries of the graphs and iteratively assign vertices of G A to vertices of G B , provided that an admissible assignment exists. This heuristic approach can be used to construct a permutation which transforms G A into G B if the graphs are isomorphic. The methods will be illustrated with several guiding examples. [ABSTRACT FROM AUTHOR]

• We develop a systematic framework for computing rare event probabilities in stochastic differential equations. • Stochastic Koopman eigenfunctions are used to develop importance sampling estimators. • Stochastic Koopman eigenfunctions are computed using dynamic mode decomposition. • Non-rare trajectories are used to inform how rare events occur. • Even crude approximations of eigenfunctions can yield efficient estimators. We exploit the relationship between the stochastic Koopman operator and the Kolmogorov backward equation to construct importance sampling schemes for stochastic differential equations. Specifically, we propose using eigenfunctions of the stochastic Koopman operator to approximate the Doob transform for an observable of interest (e.g., associated with a rare event) which in turn yields an approximation of the corresponding zero-variance importance sampling estimator. Our approach is broadly applicable and systematic, treating non-normal systems, non-gradient systems, and systems with oscillatory dynamics or rank-deficient noise in a common framework. In nonlinear settings where the stochastic Koopman eigenfunctions cannot be derived analytically, we use dynamic mode decomposition (DMD) methods to approximate them numerically, but the framework is agnostic to the particular numerical method employed. Numerical experiments demonstrate that even coarse approximations of a few eigenfunctions, where the latter are built from non-rare trajectories, can produce effective importance sampling schemes for rare events. [ABSTRACT FROM AUTHOR]

Abstract: Uncertainty quantification (UQ) techniques are frequently used to ascertain output variability in systems with parametric uncertainty. Traditional algorithms for UQ are either system-agnostic and slow (such as Monte Carlo) or fast with stringent assumptions on smoothness (such as polynomial chaos and Quasi-Monte Carlo). In this work, we develop a fast UQ approach for hybrid dynamical systems by extending the polynomial chaos methodology to these systems. To capture discontinuities, we use a wavelet-based Wiener–Haar expansion. We develop a boundary layer approach to propagate uncertainty through separable reset conditions. We also introduce a transport theory based approach for propagating uncertainty through hybrid dynamical systems. Here the expansion yields a set of hyperbolic equations that are solved by integrating along characteristics. The solution of the partial differential equation along the characteristics allows one to quantify uncertainty in hybrid or switching dynamical systems. The above methods are demonstrated on example problems. [Copyright &y& Elsevier]

Abstract: We propose a novel distributed algorithm to cluster graphs. The algorithm recovers the solution obtained from spectral clustering without the need for expensive eigenvalue/eigenvector computations. We prove that, by propagating waves through the graph, a local fast Fourier transform yields the local component of every eigenvector of the Laplacian matrix, thus providing clustering information. For large graphs, the proposed algorithm is orders of magnitude faster than random walk based approaches. We prove the equivalence of the proposed algorithm to spectral clustering and derive convergence rates. We demonstrate the benefit of using this decentralized clustering algorithm for community detection in social graphs, accelerating distributed estimation in sensor networks and efficient computation of distributed multi-agent search strategies. [Copyright &y& Elsevier]

Abstract: The study of high-dimensional differential equations is challenging and difficult due to the analytical and computational intractability. Here, we improve the speed of waveform relaxation (WR), a method to simulate high-dimensional differential-algebraic equations. This new method termed adaptive waveform relaxation (AWR) is tested on a communication network example. Further, we propose different heuristics for computing graph partitions tailored to adaptive waveform relaxation. We find that AWR coupled with appropriate graph partitioning methods provides a speedup by a factor between 3 and 16. [Copyright &y& Elsevier]

In this paper we develop new methods for computing k-dimensional invariant manifolds of delayed systems for k ≥ 2. Our current implementation is built for k = 2 only, but the numerical and algorithmic challenges encountered in this case will be also present for any k > 1. For small delays, we consider methods for approximating delay differential equations (DDEs) with ordinary differential equations (ODEs). Once these approximations are made, any existing method for computing invariant manifolds of ODEs can then be used directly. We derive bounds on errors incurred by the most natural of these approximations. For large delays, we extend to DDEs the method originally introduced by Krauskopf and Osinga [Chaos, 9 (1999), pp. 768-774] for invariant manifolds of ODEs. We test the convergence of the resulting algorithms numerically and further illustrate our approach by computing two-dimensional unstable manifolds of equilibria in the context of phase-conjugate feedback lasers. [ABSTRACT FROM AUTHOR]

Synchronized micromechanical oscillators have potential for applications in signal processing, neural computing, sensing, and other fields. This paper explores the conditions under which coupled nonlinear limit cycle microoscillators can synchronize. As an example of the modeling approach and to be able to obtain results for a system that has been experimentally realized, thermally excited dome oscillators, which are fabricated by buckling of a thin circular film of polysilicon, are modeled. Starting with the von Kármán plate equations and an assumed mode shape, a Galerkin projection is performed to obtain an ordinary differential equation for the postbuckled dynamics of the mode. Because the structure is thermally excited, a thermal model is built by solving the heat equation on a disk with appropriate boundary conditions. Bifurcation analysis of the single oscillator model is performed to look for basic underlying phenomena. Conditions under which two slightly detuned coupled limit cycle dome oscillators will synchronize are explored. [ABSTRACT FROM AUTHOR]

Abstract: The small size and low damping of MEMS oscillators give rise to phenomena that are not observed routinely at the macroscopic scale. In this work we document and explain an experimentally observed transition in the response of a doubly clamped micromechanical oscillator with pretension. The transition from softening to hardening is repeatedly observed upon increasing the power of an incident sensing laser beam, a procedure routinely used to improve signal strength during optical detection of resonant motion of microstructures. At intermediate laser power, a novel resonant response that displays characteristics of both softening and hardening in the same sweep, is observed experimentally. Increased laser heating of a structure in tension may be expected to increase softening behavior. Using tools from non-linear dynamics and continuum mechanics, we show that the observed counter-intuitive behavior can be explained by a competition between the opposing responses of linear and non-linear stiffnesses to a change in temperature. [Copyright &y& Elsevier]

The present paper addresses the problem of spin recovery of an aircraft as a nonlinear inverse dynamics problem of determining the control inputs that need to be applied to transfer the aircraft from a spin state to a level trim flight condition. A stable, oscillatory, flat, left spin state is first identified from a standard bifurcation analysis of the aircraft model considered, and this is chosen as the starting point for all recovery attempts. Three different symmetric, level-flight trim states, representative of high, moderate, and low-angle-of-attack trims for the chosen aircraft model, are computed by using an extended-bifurcation-analysis procedure. A standard form of the nonlinear dynamic inversion algorithm is implemented to recover the aircraft from the oscillatory spin state to each of the selected level trims. The required control inputs in each case, obtained by solving the inverse problem, are compared against each other and with the standard recovery procedure for a modern, low-aspect-ratio, fuselage heavy configuration. The spin recovery procedure is seen to be restricted because of limitations in control surface deflections and rates and because of loss of control effectiveness at high angles of attack. In particular, these restrictions adversely affect attempts al recovery directly from high-angle-of-attack oscillatory spins to low-angle-of-attack trims using only aerodynamic controls. Further, two different control strategies are examined in an effort to overcome difficulties in spin recovery because of these restrictions. The first strategy uses an indirect, two-step recovery procedure in which the airplane is first recovered to a high- or moderate-angle-of-attack level-flight trim condition, followed by a second step where the airplane is then transitioned to the desired low-angle-of-attack trim. The second strategy involves the use of thrust-vectoring controls in addition to the standard aerodynamic control surfaces to directly recover the aircraft from high-angle-of-attack oscillatory spin to a low-angle-of-attack level-flight trim state. Our studies reveal that both strategies are successful, highlighting the importance of effective thrust management in conjunction with suitable use of all of the aerodynamic control surfaces for spin recovery strategies. [ABSTRACT FROM AUTHOR]

Abstract: Development of robust dynamical systems and networks such as autonomous aircraft systems capable of accomplishing complex missions faces challenges due to the dynamically evolving uncertainties coming from model uncertainties, necessity to operate in a hostile cluttered urban environment, and the distributed and dynamic nature of the communication and computation resources. Model-based robust design is difficult because of the complexity of the hybrid dynamic models including continuous vehicle dynamics, the discrete models of computations and communications, and the size of the problem. We will overview recent advances in methodology and tools to model, analyze, and design robust autonomous aerospace systems operating in uncertain environment, with stress on efficient uncertainty quantification and robust design using the case studies of the mission including model-based target tracking and search, and trajectory planning in uncertain urban environment. To show that the methodology is generally applicable to uncertain dynamical systems, we will also show examples of application of the new methods to efficient uncertainty quantification of energy usage in buildings, and stability assessment of interconnected power networks. [Copyright &y& Elsevier]