Nathan Wiebe

We provide several quantum algorithms for continuous optimization that do not require gradient estimation. Instead, we encode the optimization problem into the dynamics of a physical system and coherently simulate the time evolution. Our first two algorithms can find local optima of a differentiable function $f: \mathbb{R}^N \rightarrow \mathbb{R}$ by simulating either classical or quantum dynamics with friction via a time-dependent Hamiltonian. We show that for the benchmark problem of optimizing a locally quadratic objective function, these methods require a total of $O(N^2\kappa^2/h_x^2\epsilon)$ queries to a phase oracle to find an $\epsilon$-approximate local optimum, where $\kappa$ is the condition number of the Hessian matrix and $h_x$ is the discretization spacing. In contrast, we show that methods based on gradient descent require $O(N^{3/2}(1/\epsilon)^{\kappa \log(3)/4})$ queries. This corresponds to an exponential separation between the query upper bounds for the benchmark problem. Our third algorithm can find the global optimum of $f$ by preparing a classical low-temperature thermal state via simulation of the classical Liouvillian operator associated with the Nosé Hamiltonian. We use results from the quantum thermodynamics literature to bound the thermalization time for the discrete system. Additionally, we analyze barren plateau effects that commonly plague quantum optimization algorithms and observe that our approach is vastly less sensitive to this problem than standard gradient-based optimization. Our results suggests that these dynamical optimization approaches may be far more scalable for future quantum machine learning, optimization and variational experiments than was widely believed.

Abstract We show how to achieve the highest efficiency yet for simulations with arbitrary basis sets by using a representation of the Coulomb operator known as tensor hypercontraction (THC). We use THC to express the Coulomb operator in a non-orthogonal basis, which we are able to block encode by separately rotating each term with angles that are obtained via QROM. Our algorithm has the best complexity scaling for an arbitrary basis, as well as the best complexity for the specific case of FeMoCo. By optimising the surface code resources, we show that FeMoCo can be simulated using about 4 million physical qubits and 3.5 days of runtime, assuming 1 s cycle times and physical gate error rates no worse than 0.1%.

Abstract We compile explicit circuits and evaluate the computational cost for heuristic-based quantum algorithms for combinatorial optimization. We consider several variants of quantum-accelerated simulated annealing as well as adiabatic algorithms, quantum-enhanced population transfer, the quantum approximate optimization algorithm, and other approaches. We provide novel methods for executing the bottleneck subroutines for these heuristics, and our methods can easily be applied to other algorithms where numerical performance matters. We estimate how quickly the subroutines could be executed on a modestly sized superconducting-qubit-based quantum computer with surface code error correction. We conclude that quadratic speedups for heuristic-based quantum optimization algorithms are insufficient for early quantum computers to beat present day classical computers.

In this work we introduce the quantum springs and sticks (QSS) model, a quantum machine learning model that performs supervised learning with an exponential amount of degrees of freedom. The model is based on the springs and sticks model, a classical mechanical system that uses coupled oscillators and dissipation to perform non-linear regression. We map the dynamics to a time-dependent Hamiltonian, which uses the Caldirola–Kanai parametrization to simulate dissipation through unitary evolution. Then, the solution to the supervised learning problem can be extracted via a spectral decomposition. Finally, we simulate our algorithm on simple regression tasks using time-dependent Trotterization, and compare it to the classical Langevin-dynamics version of such algorithm.

Accurately computing the free energies of biological processes is a cornerstone of computer-aided drug design, but it is a daunting task. The need to sample vast conformational spaces and account for entropic contributions makes the estimation of binding free energies very expensive. While classical methods, such as thermodynamic integration and alchemical free energy calculations, have significantly contributed to reducing computational costs, they still face limitations in terms of efficiency and scalability. We tackle this through a quantum algorithm for the estimation of free energy differences by adapting the existing Liouvillian approach and introducing several key algorithmic improvements. We directly implement the Liouvillian operator and provide an efficient description of electronic forces acting on both nuclear and electronic particles on the quantum ground state potential energy surface. This leads to super-polynomial runtime scaling improvements in the precision of our Liouvillian simulation approach and quadratic improvements in the scaling with the number of particles relative to prior quantum algorithms. Second, our algorithm calculates free energy differences via a fully quantum implementation of thermodynamic integration and alchemy, thereby foregoing expensive entropy estimation subroutines used in prior works. Our results open new avenues towards the application of quantum computers in drug discovery.

We present quantum algorithms for simulating the dynamics of a broad class of classical oscillator systems containing 2^n coupled oscillators (Eg: 2^n masses coupled by springs), including those with time-dependent forces, time- varying stiffness matrices, and weak nonlinear interactions. This generaliza- tion of the Harmonic oscillator simulation algorithm is achieved through an approach that we call “Nonlinear Schrödingerization”, which involves reduction of the dynamical system to a nonlinear Schrödinger equation and then reduced to a time-independent Schrodinger Equation through perturbative techniques. The linearization of the equation is performed using an approach that allows the dynamics of a nonlinear Schrödinger equation to be approximated as a linear Schrödinger equation in a higher dimensional space. This allows Hamiltonian Simulation algorithms to be applied to simulate the dynamics of resulting sys- tem. When the properties of the classical dynamical systems can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in n, and almost linear in evolution time for most dynamical systems. Our work extends the applicability of quan- tum algorithms to simulate the dynamics of non-conservative and nonlinear classical systems, addressing key limitations in previous approaches