Quantum algorithm for simulating real time evolution of lattice Hamiltonians

DOI10.1137/18M1231511MaRDI QIDQ5149753zbMATH OpenWikidataFDO

Authors Jeongwan Haah, Robin Kothari, Guang Hao Low, M. B. Hastings

Publication date 8 February 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.03922

zbMATH Keywords

local Hamiltonianquantum algorithmsimulation

Mathematics Subject Classification ID

Polylogarithms and relations with (K)-theory (11G55) Simulation of dynamical systems (37M05) Applications to the sciences (65Z05) Quantum algorithms and complexity in the theory of computing (68Q12) Approximation algorithms (68W25) Computational methods for problems pertaining to quantum theory (81-08) Quantum gates (81P65) Quantum computation (81P68) Selfadjoint operator theory in quantum theory, including spectral analysis (81Q10) Statistical mechanics of crystals (82D25)

Abstract: We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on $n$ qubits for time $T$ up to error $epsilon$ using $mathcalO(nTmathrmpolylog(nT/epsilon))$ gates with depth $mathcalO(Tmathrmpolylog(nT/epsilon))$. Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in $nT$ and polylogarithmic in $1/epsilon$. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. 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 $ildeOmega(nT)$ gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.

Recommendations

• Efficient quantum algorithms for simulating sparse Hamiltonians
• Algorithm for quantum simulation
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Bounding the costs of quantum simulation of many-body physics in real space

Cites work

• Adiabatic quantum state generation and statistical zero knowledge
• Approximation theory and approximation practice
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Fast universal quantum computation with railroad-switch local Hamiltonians
• General theory of fractal path integrals with applications to many-body theories and statistical physics
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 5788515 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• Lieb-Robinson bounds and the exponential clustering theorem
• Mapping local Hamiltonians of fermions to local Hamiltonians of spins
• On the Product of Semi-Groups of Operators
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits
• Spectral gap and exponential decay of correlations
• The theory of quantum information
• Toward the first quantum simulation with quantum speedup
• Universal Quantum Simulators

Cited in

(20)

• Correlation length in random MPS and PEPS
• Trotter product formulae for \(\ast\)-automorphisms of quantum lattice systems
• Probabilistic nonunitary gate in imaginary time evolution
• Quantum algorithm for preparing thermal Gibbs states -- detailed analysis
• Approximating fractional time quantum evolution
• On the efficiency of quantum algorithms for Hamiltonian simulation
• Bounding the costs of quantum simulation of many-body physics in real space
• An algebraic quantum circuit compression algorithm for Hamiltonian simulation
• Efficient Quantum Algorithms for Simulating Lindblad Evolution
• Optimization of quantum Hamiltonian evolution: from two projection operators to local Hamiltonians
• ON THE COMPUTATIONAL POWER OF PHYSICAL INTERACTIONS: BOUNDS ON THE NUMBER OF TIME STEPS FOR SIMULATING ARBITRARY INTERACTION GRAPHS
• Conserved charges in the quantum simulation of integrable spin chains
• Invertible subalgebras
• Average-case speedup for product formulas
• Riemannian quantum circuit optimization for Hamiltonian simulation
• Enhanced Lieb-Robinson bounds for commuting long-range interactions
• Preparing Hamiltonians for quantum simulation: A computational framework for Cartan decomposition via Lax dynamics
• On the refinement of Cartan decomposition: an implicit commutative substructure in \(\mathfrak{su}(2^n)\)
• Efficient quantum Gibbs samplers with Kubo-Martin-Schwinger detailed balance condition
• Exponential tail estimates for quantum lattice dynamics

This page was built for publication: Quantum algorithm for simulating real time evolution of lattice Hamiltonians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5149753)