01436nas a2200121 4500008004100000245006400041210006300105260001500168520104800183100002301231700002301254856003701277 2009 eng d00aBlack-box Hamiltonian simulation and unitary implementation0 aBlackbox Hamiltonian simulation and unitary implementation c2009/10/223 a 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 log N)^{4/3}) queries to its matrix
elements. In fact, except for pathological cases, it appears that most
unitaries can be performed with only O(sqrt{N}) queries, which is optimal.
1 aBerry, Dominic, W.1 aChilds, Andrew, M. uhttp://arxiv.org/abs/0910.4157v4