Invited Talks

Jin-Peng Liu, Center for Theoretical Physics, MIT, USA.

Title: Towards Provably Efficient Quantum Algorithms for Nonlinear Dynamics and Large-scale Machine Learning Models.

Nonlinear dynamics play a prominent role in many domains and are notoriously difficult to solve. Whereas previous quantum algorithms for general nonlinear equations have been severely limited due to the linearity of quantum mechanics, we gave the first efficient quantum algorithm for nonlinear differential equations with sufficiently strong dissipation. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in the evolution time. We also established a lower bound showing that nonlinear differential equations with sufficiently weak dissipation have worst-case complexity exponential in time, giving an almost tight classification of the quantum complexity of simulating nonlinear dynamics. Furthermore, we design the first quantum algorithm for training classical sparse neural networks with end-to-end settings. We benchmark instances of training ResNet from 7 to 103 million parameters with sparse pruning applied to the Cifar-100 dataset, and we find that a quantum enhancement is possible at the early stage of learning. Our work shows that fault-tolerant quantum computing can contribute to the scalability and sustainability of most state-of-the-art, large-scale machine learning models.  

Dominic Berry, Macquarie University, Australia.

Title: Exponential quantum speedup in simulating coupled classical oscillators

We present a quantum algorithm for simulating the classical dynamics of 2^n coupled oscillators (e.g., masses coupled by springs). Our approach leverages a mapping between the Schrödinger equation and Newton's equation for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators. When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in n almost linear in the evolution time, and sublinear in the sparsity. As an example application, we apply our quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time. We show that any classical algorithm solving this same problem is inefficient and must make 2^{\Omega(n)} queries to the oracle and, when the oracles are instantiated by efficient quantum circuits, the problem is BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers. Finally, we show that under similar conditions our approach can efficiently simulate more general classical harmonic systems with 2^n modes.

Contributed Talks

Potential quantum advantage for simulation of fluid dynamics, Li, Yin, Wiebe, Chun, Schenter, Cheung, Muelmenstaedt

Numerical simulation of turbulent fluid dynamics needs to either parameterize turbulence—which introduces large uncertainties—or explicitly resolve the smallest scales—which is prohibitively expensive. Here we provide evidence through analytic bounds and numerical studies that a potential quantum exponential speedup can be achieved to simulate the Navier–Stokes equations governing turbulence using quantum computing. Specifically, we provide a formulation of the lattice Boltzmann equation for which we give evidence that low-order Carleman linearization is much more accurate than previously believed for these systems and that for computationally interesting examples. This is achieved via a combination of reformulating the nonlinearity and accurately linearizing the dynamical equations, effectively trading nonlinearity for additional degrees of freedom that add negligible expense in the quantum solver. Based on this we apply a quantum algorithm for simulating the Carleman-linearized lattice Boltzmann equation and provide evidence that its cost scales logarithmically with system size, compared to polynomial scaling in the best known classical algorithms. This work suggests that an exponential quantum advantage may exist for simulating fluid dynamics, paving the way for simulating nonlinear multiscale transport phenomena in a wide range of disciplines using quantum computing.

Continuous Variables Quantum Algorithm for solving Ordinary Differential Equations. Barthe, Grossi, Tura, Dunjko

Solving Ordinary Differential Equations (ODE) is important for a broad range of domains, such as engineering, weather forecast, and finance. Most quantum algorithms proposed to solve them revolve around transforming ODEs into a system of linear equations, in order to benefit from the exponential advantage promised by the HHL algorithm. However, there are known limitations to this subroutine such as the linear scaling with condition number. In particular, for HHL-based ODE solvers, this dependency yields a complexity that generally grows exponentially with the integration time. In this paper, we present a scheme that does not rely on the HHL subroutine. We use the Koopman Von Neumann (KvN) formalism that maps arbitrary nonlinear dynamics to a Hilbert space where the dynamics are unitary. This effectively reduces the ODE problem to a Hamiltonian time evolution, which is a well-known problem in quantum computing. However, this comes at a cost as the KvN formalism is expressed in an infinite-dimensional Hilbert space, and involves nonphysical states with infinite energies. Previous works have tackled this by truncating the Hilbert space, and by approximating all the relevant states and operations on qubit-based systems. Instead of mapping to qubit-based computations, in this paper, we investigate the direct use of continuous-variable quantum computers for this problem. We provide an algorithm to compile a sequence of Gaussian and non-Gaussian continuous variables gates to solve an arbitrary one-dimensional polynomial ODE. We analyze the algorithm and propose that it is intrinsically better suited for solving so-called initial distribution problems, rather than initial condition problems. We also propose the first steps towards a comprehensive complexity and specify which steps need to be developed for a complete analysis.

Efficient Quantum Algorithms for Nonlinear Stochastic Dynamical Systems. Gnanasekaran, Surana, Sahai

In this paper, we propose efficient quantum algorithms for solving nonlinear stochastic differential equations (SDE) via the associated Fokker-Planck equation (FPE). We discretize the FPE in space and time using two well-known numerical schemes, namely Chang-Cooper and implicit finite difference. We then compute the solution of the resulting system of linear equations using the quantum linear systems algorithm. We present detailed error and complexity analyses for both these schemes and demonstrate that our proposed algorithms, under certain conditions, provably compute the solution to the FPE within prescribed error bounds with polynomial dependence on state dimension. Classical numerical methods scale exponentially with dimension, thus, our approach, under the aforementioned conditions, provides an exponential speed-up over traditional approaches.

Quantum algorithm for the linear Vlasov equation with collisions. Ameri, Ye, Cappellaro, Krovi, Loureiro

The Vlasov equation is a nonlinear partial differential equation that provides a first-principles description of the dynamics of plasmas. Its linear limit is routinely used in plasma physics to investigate plasma oscillations and stability. In this paper, we present a quantum algorithm that simulates the linearized Vlasov equation with and without collisions, in the one-dimensional electrostatic limit. Rather than solving this equation in its native spatial and velocity phase space, we adopt an efficient representation in the dual space yielded by a Fourier-Hermite expansion. For a given simulation time, the Fourier-Hermite representation is exponentially more compact, thus yielding a classical algorithm that can match the performance of a previously proposed quantum algorithm for this problem. This representation results in a system of linear ordinary differential equations (ODEs) which can be solved with well-developed quantum algorithms: a Hamiltonian simulation in the collisionless case, and quantum ODE solvers in the collisional case. In particular, we demonstrate that a quadratic speedup in system size is attainable.