Simulating quantum dynamics on a quantum computer

Nathan Wiebe, Dominic W. Berry, Peter Høyer, Barry C. Sanders

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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.

LanguageEnglish
Article number445308
Pages1-27
Number of pages27
JournalJournal of Physics A: Mathematical and Theoretical
Volume44
Issue number44
DOIs
Publication statusPublished - 4 Nov 2011
Externally publishedYes

Fingerprint

Hamiltonians
Quantum computers
Quantum Computer
quantum computers
Quantum Dynamics
integrators
Derivatives
Derivative
Discretization Error
resources
discontinuity
Discontinuity
output
Resources
Output
Term
Range of data

Cite this

Wiebe, Nathan ; Berry, Dominic W. ; Høyer, Peter ; Sanders, Barry C. / Simulating quantum dynamics on a quantum computer. In: Journal of Physics A: Mathematical and Theoretical. 2011 ; Vol. 44, No. 44. pp. 1-27.
@article{a5b7ed5df558407383c77c10ef59ff0f,
title = "Simulating quantum dynamics on a quantum computer",
abstract = "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.",
author = "Nathan Wiebe and Berry, {Dominic W.} and Peter H{\o}yer and Sanders, {Barry C.}",
year = "2011",
month = "11",
day = "4",
doi = "10.1088/1751-8113/44/44/445308",
language = "English",
volume = "44",
pages = "1--27",
journal = "Journal of Physics A: Mathematical and Theoretical",
issn = "1751-8113",
publisher = "IOP Publishing",
number = "44",

}

Simulating quantum dynamics on a quantum computer. / Wiebe, Nathan; Berry, Dominic W.; Høyer, Peter; Sanders, Barry C.

In: Journal of Physics A: Mathematical and Theoretical, Vol. 44, No. 44, 445308, 04.11.2011, p. 1-27.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Simulating quantum dynamics on a quantum computer

AU - Wiebe, Nathan

AU - Berry, Dominic W.

AU - Høyer, Peter

AU - Sanders, Barry C.

PY - 2011/11/4

Y1 - 2011/11/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=80054824113&partnerID=8YFLogxK

U2 - 10.1088/1751-8113/44/44/445308

DO - 10.1088/1751-8113/44/44/445308

M3 - Article

VL - 44

SP - 1

EP - 27

JO - Journal of Physics A: Mathematical and Theoretical

T2 - Journal of Physics A: Mathematical and Theoretical

JF - Journal of Physics A: Mathematical and Theoretical

SN - 1751-8113

IS - 44

M1 - 445308

ER -