Gate-efficient discrete simulations of continuous-time quantum query algorithms

Dominic W. Berry, Richard Cleve, Sevag Gharibian

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)


We show how to efficiently simulate continuous-time quantum query algorithms that run in time T in a manner that preserves the query complexity (within a polylogarithmic factor) while also incurring a small overhead cost in the total number of gates between queries. By small overhead, we mean T within a factor that is polylogarithmic in terms of T and a cost measure that reflects the cost of computing the driving Hamiltonian. This permits any continuous-time quantum algorithm based on an efficiently computable driving Hamiltonian to be converted into a gate-efficient algorithm with similar running time.

Original languageEnglish
Pages (from-to)1-30
Number of pages30
JournalQuantum Information and Computation
Issue number1-2
Publication statusPublished - 1 Jan 2014


  • Quantum computation
  • Quantum query complexity


Dive into the research topics of 'Gate-efficient discrete simulations of continuous-time quantum query algorithms'. Together they form a unique fingerprint.

Cite this