### 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

*Quantum Information and Computation*,

*12*(1-2), 29-62.

}

*Quantum Information and Computation*, vol. 12, no. 1-2, pp. 29-62.

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

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 -