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.
| Language | English |
|---|---|
| Pages | 29-62 |
| Number of pages | 34 |
| Journal | Quantum Information and Computation |
| Volume | 12 |
| Issue number | 1-2 |
| Publication status | Published - 1 Jan 2012 |
Fingerprint
Cite this
}
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 journal › Article › Research › peer-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 -