Simulating sparse Hamiltonians with star decompositions

Details Simulating sparse Hamiltonians with star decompositions Simulating sparse Hamiltonians with star decompositions

2010-03-18

arxiv.org/abs/1003.3683v2

Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), Lecture Notes in Computer Science 6519, pp. 94-103

Physics

Quantum Physics

11 pages. v2: minor corrections

Scientific paper

10.1007/978-3-642-18073-6_8

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.

Affiliated with

Also associated with

No associations

Rating

Simulating sparse Hamiltonians with star decompositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simulating sparse Hamiltonians with star decompositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simulating sparse Hamiltonians with star decompositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-353619