Black-box hamiltonian simulation and unitary implementation

Dominic W. Berry, Andrew M. Childs

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D 4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N X N unitary operation use Õ(N 2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N 2/3(log logN) 4/3) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only Õ (√N) queries, which is optimal.

LanguageEnglish
Pages29-62
Number of pages34
JournalQuantum Information and Computation
Volume12
Issue number1-2
Publication statusPublished - 1 Jan 2012

Fingerprint

Hamiltonians
Black Box
boxes
Simulation
simulation
Query
Quantum Walk
Linear Complexity
matrices
Scaling
scaling
Arbitrary

Cite this

@article{1ec33fff23884f7cb622165d690e2069,
title = "Black-box hamiltonian simulation and unitary implementation",
abstract = "We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D 4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N X N unitary operation use {\~O}(N 2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N 2/3(log logN) 4/3) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only {\~O} (√N) queries, which is optimal.",
author = "Berry, {Dominic W.} and Childs, {Andrew M.}",
year = "2012",
month = "1",
day = "1",
language = "English",
volume = "12",
pages = "29--62",
journal = "Quantum Information and Computation",
issn = "1533-7146",
publisher = "Rinton Press Inc.",
number = "1-2",

}

Black-box hamiltonian simulation and unitary implementation. / Berry, Dominic W.; Childs, Andrew M.

In: Quantum Information and Computation, Vol. 12, No. 1-2, 01.01.2012, p. 29-62.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Black-box hamiltonian simulation and unitary implementation

AU - Berry, Dominic W.

AU - Childs, Andrew M.

PY - 2012/1/1

Y1 - 2012/1/1

N2 - We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D 4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N X N unitary operation use Õ(N 2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N 2/3(log logN) 4/3) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only Õ (√N) queries, which is optimal.

AB - We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D 4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N X N unitary operation use Õ(N 2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N 2/3(log logN) 4/3) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only Õ (√N) queries, which is optimal.

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

M3 - Article

VL - 12

SP - 29

EP - 62

JO - Quantum Information and Computation

T2 - Quantum Information and Computation

JF - Quantum Information and Computation

SN - 1533-7146

IS - 1-2

ER -