Efficient quantum algorithms for simulating sparse hamiltonians

Dominic W. Berry*, Graeme Ahokas, Richard Cleve, Barry C. Sanders

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    437 Citations (Scopus)


    We present an efficient quantum algorithm for simulating the evolution of a quantum state for a sparse Hamiltonian H over a given time t in terms of a procedure for computing the matrix entries of H. In particular, when H acts on n qubits, has at most a constant number of nonzero entries in each row/column, and ||H|| is bounded by a constant, we may select any positive integer k such that the simulation requires O((log* n)t 1+1/2k ) accesses to matrix entries of H. We also show that the temporal scaling cannot be significantly improved beyond this, because sublinear time scaling is not possible.

    Original languageEnglish
    Pages (from-to)359-371
    Number of pages13
    JournalCommunications in Mathematical Physics
    Issue number2
    Publication statusPublished - Mar 2007


    Dive into the research topics of 'Efficient quantum algorithms for simulating sparse hamiltonians'. Together they form a unique fingerprint.

    Cite this