2010/11/30 by Nathan Wiebe, Dominic W Berry, Dominic W. Berry +4 · 6 citations
Computer Science · Mathematics · Physics and Astronomy · #Constant (computer programming) #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum computer #Quantum many-body systems #Quantum phase estimation algorithm #Representation (politics) #Smoothness #Unitary state #Upper and lower bounds #math-ph #math.MP #quant-ph
paper · pdf · doi:10.1088/1751-8113/44/44/445308
published as J. Phys. A: Math. Theor. 44, 445308 (2011) · Paper modified from previous version to enhance clarity. Comments are welcome
arxiv created 2011/05/27 · openalex publication_date 2011/10/18 · arxiv updated 2011/11/03 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
We explicitly show how to simulate time-dependent sparse Hamiltonian evolution on a quantum computer, with complexity that is close to linear in the evolution time. The complexity also depends on the magnitude of the derivatives of the Hamiltonian. We propose a range of techniques to simulate Hamiltonians with badly behaved derivatives. These include using adaptive time steps, adapting the order of the integrators, and omitting regions about discontinuities. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian, and accounts for all computational resources. We explicitly determine the number of bits of output that this oracle needs to provide, and show how to efficiently perform the required 1-sparse unitary operations using these bits. We also account for discretization error in the time, as well as accounting for Hamiltonians that are a sum of terms that are sparse in different bases.