Session Q40: Quantum Algorithms for Hamiltonian Simulation

Simulating thermal quantum quenches with a variational quantum algorithm

Noisy intermediate-scale quantum (NISQ) devices hold great promise in the modeling of quantum physical systems in and out of equilibrium. Thermal quantum quenches are a particularly important example that are both relevant for the discovery of fundamental physics phenomena and the simulation of complex materials. In a thermal quantum quench, a system initially at thermal equilibrium with a finite temperature is abruptly brought out of equilibrium by a sudden change in the parameters of its Hamiltonian. To enable simulations of the complex post-quench dynamics on NISQ devices, which are limited to shallow and narrow circuits, we develop a variational quantum algorithm that combines the recent adaptive variational quantum dynamics simulation (AVQDS) method with a density matrix quantum Monte-Carlo technique for thermal state preparation. We benchmark this new method using simulations of sudden thermal quenches in the mixed-field Ising chain, focusing on thermodynamic observables and the Loschmidt echo. We compare noiseless quantum simulation results with exact diagonalization and comment on the impact of finite temperature on the post-quench dynamics.   

Quantum Simulation of Open Lattice Field Theories

Open lattice field theories are useful in describing many physical systems. Yet their implementation in traditional quantum computing is hindered by the requirement of Hermiticity. We will discuss two ways of simulating a 1D quantum Ising model with an imaginary longitudinal field on quantum computer's. The first is using QITE, and the second is using quantum state tomography to enhance other algorithms based on quantum operations. As tomography involves reconstructing the state vector many times throughout the simulation, it is very volatile to incorrect measurements. Thus in the NISQ era,  we are heavily restricted with both the size of the system, complexity, and length of evolution, so we will further discuss construction of robust noise models to aid in simulation.   

Efficient Fully-Coherent Hamiltonian Simulation

Hamiltonian simulation is a fundamental problem at the heart of quantum computation, and the associated simulation algorithms are useful building blocks for designing larger quantum algorithms. In order to be successfully concatenated into a larger quantum algorithm, a Hamiltonian simulation algorithm must succeed with arbitrarily high success probability 1-δ while only requiring a single copy of the initial state, a property which we call fully-coherent. Although optimal Hamiltonian simulation has been achieved by quantum signal processing (QSP), with query complexity linear in time t and logarithmic in inverse error ln(1/ε), the corresponding algorithm is not fully-coherent as it only succeeds with probability close to 1/4. While this simulation algorithm can be made fully-coherent by employing amplitude amplification at the expense of appending a ln(1/δ) multiplicative factor to the query complexity, here we develop a new fully-coherent Hamiltonian simulation algorithm that achieves a query complexity additive in ln(1/δ): Θ(|H| |t| + ln(1/ε) + ln(1/δ)). We accomplish this by compressing the spectrum of the Hamiltonian with an affine transformation, and applying to it a QSP polynomial that approximates the complex exponential only over the range of the compressed spectrum. We further numerically analyze the complexity of this algorithm and demonstrate its application to the simulation of the Heisenberg model in constant and time-dependent external magnetic fields. We believe that this efficient fully-coherent Hamiltonian simulation algorithm can serve as a useful subroutine in quantum algorithms where maintaining coherence is paramount.   

Multiproduct formulas for time-dependent Hamiltonian simulation

Product formulas, such as Suzuki-Trotter decompositions, are a useful technique for simulating time-dependent (TD) Hamiltonians, such as those with oscillating fields or when working in an interaction picture. In these schemes, the ordering of the operators is chosen to cancel terms in an error series up to a certain order in simulation time $t$. As a generalization of product formulas, multiproduct formulas (MPFs) accomplish this same cancellation of error terms by taking sums of unitaries, which can be implemented on a quantum computer using, for example, the Linear Combination of Unitaries (LCU) technique. While multiproduct formulas have been analyzed in the context of time-independent Hamiltonians, they have not yet been applied to the more general TD case. In this talk, I will present a new algorithm for TD Hamiltonian simulation using MPFs. Like LCU-based methods, our approach has a favorable logarithmic dependence on the inverse error, while also taking advantage of vanishing commutators of $H(t)$ at different times. This work helps address a relative scarcity of algorithms for TD Hamiltonians compared to the time-independent case.   

Preparing Angular Momentum Eigenstates on Quantum Computers

Coupled angular momentum eigenstates |j,m, j₁, m₁, j₂, m₂> are widely used in atomic and nuclear physics calculations. In order to accelerate such calculations on a quantum computer, we investigate how to combine two angular momenta J₁ and J₂ to form total angular momentum J=J₁+J₂ eigenstates faster than standard Clebsch–Gordan/Racah methods. Starting from the ground state, simulated magnetic resonance gates U_b prepare states of fixed j. Then, simulated dipole transition gates U_d change the j value and prepare a superposition of |j,m> states. The success probability of preparing a specific |j,m> state can be controlled using parameters of the U_b and U_d gates. Since all eigenstates are needed for the target calculations, we use an ancilla register to record the prepared |j,m> eigenstate. Two entangling gates U_m and U_j transfer the m and j values from the computational basis to the ancilla register, which can be partially readout or retained during subsequent calculations. We experimentally demonstrate our state preparation scheme for the j₁=j₂=1/2 case using four levels in a superconducting transmon qudit. The complexity scaling of this state preparation scheme to higher j values is discussed and compared with classical algorithms.   

Nearly-frustration-free ground state preparation

Solving for quantum ground states is important for understanding the properties of quantum many-body systems, and quantum computers are potentially well-suited for solving for quantum ground states. Recent work has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians, whose query complexity scales as δ^-1, i.e. inversely with their normalized gap. Here we consider instead the ground state preparation problem restricted to a special subset of Hamiltonians, which includes those which we term "nearly-frustration-free": the class of Hamiltonians for which the ground state energy of their block-encoded and hence normalized Hamiltonian α^-1H is within δ^y of -1, where δ is the spectral gap of α^-1H and 0≤y≤1. For this subclass, we describe an algorithm whose dependence on the gap is asymptotically better, scaling as δ^y/2-1, and show that this new dependence is optimal up to factors of log δ. In addition, we give examples of physically motivated Hamiltonians which live in this subclass. Finally, we describe an extension of this method which allows the preparation of excited states both for generic Hamiltonians as well as, at a similar speedup as the ground state case, for those which are nearly frustration-free.   

Hamiltonian Algorithms

We consider two nearly optimal algorithms about local Hamiltonians. The first is to implement the real time evolution unitary generated by a lattice Hamiltonian on a general purpose quantum computer. Our algorithm simulates the time evolution of such a Hamiltonian on n qubits for time T up to error ϵ using O(nTpolylog(nT/ϵ)) gates with depth O(Tpolylog(nT/ϵ)). Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in nT and polylogarithmic in 1/ϵ. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires Ω(nT) gates in the worst case. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. The second is to learn a local Hamiltonian given a short time evolution unitary channel in a blackbox. We show how to learn the coefficients of a lattice Hamiltonian to error ϵ with query complexity O(log n / t ϵ^2 polylog(1/ϵ)) and classical, postprocessing time complexity linear in the product of the query count and the number of qubits. This uses a convergent series expansion of the real time evolution operator in evolution time t, and a quantum device is only required to measure local Pauli operators.   

Implementing NISQ-era algorithms for Open Quantum Systems

Open quantum systems are good models of many interesting physical systems. Non-Hermitian Hamiltonians are known to describe, or at least approximate some of these open quantum systems well. Recently, there has been an increase in interest in quantum algorithms for simulating such Hamiltonians, such as the Quantum Imaginary Time Evolution algorithm, and other ones based on trace preserving quantum operations, using an enlarged Hilbert space. The focus of our work is on testing the near-term applicability of some of these NISQ-era algorithms on real, noisy quantum hardware. We will look at the 1D quantum Ising model and the 3-state Potts model in complex parameter space. These models have a rich phase-structure in the complex plane and studying them would allow us to explore critical regions such as Lee-Yang edges and Fisher zeros. We will also discuss the applicability of these algorithms for ground-state preparation.   

Adaptive Variational Quantum Dynamics Simulations

We propose a general-purpose, self-adaptive approach to construct variational wavefunction ans\"atze for highly accurate quantum dynamics simulations based on McLachlan's variational principle.  The key idea is to dynamically expand the variational ansatz along the time-evolution path such that the ``McLachlan distance'', which is a measure of the simulation accuracy, remains below a set threshold. We apply this adaptive variational quantum dynamics simulation (AVQDS) approach to the integrable Lieb-Schultz-Mattis spin chain and the nonintegrable mixed-field Ising model, where it captures both finite-rate and sudden post-quench dynamics with high fidelity. The AVQDS quantum circuits that prepare the time-evolved state are much shallower than those obtained from first-order Trotterization and contain up to two orders of magnitude fewer CNOT gate operations. We envision that a wide range of dynamical simulations of quantum many-body systems on near-term quantum computing devices will be made possible through the AVQDS framework.   

Quantum Krylov subspace algorithms for ground and excited state energy estimation

In this talk, I will present unified framework for quantum Krylov subspace methods which aim to solve the ground and excited state energy estimation problem using near-term quantum computing hardware. I will show that a wide class of Hamiltonians relevant to nuclear physics, condensed matter physics, and chemistry contain symmetries that can be exploited to avoid the use of the Hadamard test. The Hadamard test, which is a requisite for a wide variety of quantum Krylov algorithms, uses an ancilla qubit with controlled multi-qubit gates that can be quite costly for near-term hardware. I will introduce a multi-fidelity estimation protocol that replaces the Hadamard test and, when combined with efficient single-fidelity estimation protocols, provides a substantial reduction in circuit depth. I will also introduce several new quantum Krylov algorithms that provide various advantages and disadvantages in terms of the number of calls to the quantum computer, gate depth, and classical complexity. To test the efficacy of the proposed algorithms, I will present numerical experiments of the proposed algorithms for the problem of finding the ground and excited-state energies of various quantum chemistry Hamiltonians, highlighting their fast convergence with a small number of iterations.   

Algebraic Compression of Quantum Circuits for Hamiltonian Evolution

Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware. Synthesizing the corresponding quantum circuit is typically done by breaking the evolution into small time steps, also known as Trotterization, which leads to circuits whose depth scales with the number of steps. When the circuit elements are limited to a subset of $SU(4)$ --- or equivalently, when the Hamiltonian may be mapped onto free fermionic models --- several identities exist that combine and simplify the circuit. Based on this, we present an algorithm that compresses the Trotter steps into a single block of quantum gates. This results in a fixed depth time evolution for certain classes of Hamiltonians. We explicitly show how this algorithm works for several spin models and free fermion models of any dimension, and demonstrate its use for adiabatic state preparation of the 1-D transverse field Ising model and simulation of several 2-D free fermion models.   

Lattice Quantum Chromodynamics and Electrodynamics on a Universal Quantum Computer

Lattice gauge theories form a cornerstone of computational particle physics. Here we present explicit quantum algorithms down to gate-by-gate level circuits for simulating quantum electrodynamics and chromodynamics. The algorithms include every element of the Kogut-Susskind Hamiltonian for U(1), SU(2), and SU(3) theories, and are extensible to SU(N) theories. Furthermore, we provide concrete estimates of the fault-tolerant computational resources required for simulations of lattice gauge theories in any dimension and lattice size. Future improvements based on our results will one day bring about new discoveries in particle and nuclear physics via quantum simulations.   

An efficient quantum algorithm for the time evolution of parameterized circuits

We introduce a novel hybrid algorithm to simulate the real-time evolution of quantum systems using parameterized quantum circuits.

The method, named "projected - Variational Quantum Dynamics" (p-VQD) realizes an iterative, global projection of the exact time evolution onto the parameterized manifold. In the small time step limit, this is equivalent to the McLachlan's variational principle. Our approach is efficient in the sense that it exhibits an optimal linear scaling with the total number of variational parameters. Furthermore, it is global in the sense that it uses the variational principle to optimize all parameters at once. The global nature of our approach then significantly extends the scope of existing efficient variational methods, that instead typically rely on the iterative optimisation of a restricted subset of variational parameters.   

Through numerical experiments, we also show that our approach is particularly advantageous over existing global optimisation algorithms based on the time-dependent variational principle that, due to a demanding quadratic scaling with parameter numbers, are unsuitable for large parameterized quantum circuits.