



01041nas a2200121   4500008004100000245006000041210006000101260001500161520066400176100002300840700001900863856003700882       2010                        eng d00aSimulating sparse Hamiltonians with star decompositions0 aSimulating sparse Hamiltonians with star decompositions  c2010/03/183 a  We present an efficient algorithm for simulating the time evolution due to a
sparse Hamiltonian. In terms of the maximum degree d and dimension N of the
space on which the Hamiltonian H acts for time t, this algorithm uses
(d^2(d+log* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the
sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders,
which scales like (d^4(log* N)||Ht||)^{1+o(1)}. To achieve this, we decompose a
general sparse Hamiltonian into a small sum of Hamiltonians whose graphs of
non-zero entries have the property that every connected component is a star,
and efficiently simulate each of these pieces.
1 aChilds, Andrew, M.1 aKothari, Robin  uhttp://arxiv.org/abs/1003.3683v2