Corrected quantum walk for optimal Hamiltonian simulation

Dominic Berry, Leonardo Novo

    Research output: Contribution to journalArticlepeer-review


    We describe a method to simulate Hamiltonian evolution on a quantum computer by repeatedly using a superposition of steps of a quantum walk, then applying a correction to the weightings for the numbers of steps of the quantum walk. This correction enables us to obtain complexity which is the same as the lower bound up to double-logarithmic factors for all parameter regimes. The scaling of the query complexity is O (τ (log logτ/log log logτ) + log(1/ε)) where τ := t||H||maxd, for ε the allowable error, t the time, ||H||max the max-norm of the Hamiltonian, and d the sparseness. This technique should also be useful for improving the scaling of the Taylor series approach to simulation, which is relevant to applications such as quantum chemistry.

    Original languageEnglish
    Pages (from-to)1295–1317
    Number of pages23
    JournalQuantum Information and Computation
    Issue number15&16
    Publication statusPublished - Nov 2016


    • quantum algorithms
    • quantum query complexity
    • Hamiltonian simulation
    • quantum walk


    Dive into the research topics of 'Corrected quantum walk for optimal Hamiltonian simulation'. Together they form a unique fingerprint.

    Cite this