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

Dominic W. Berry, Richard Cleve, Sevag Gharibian

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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.

LanguageEnglish
Pages1-30
Number of pages30
JournalQuantum Information and Computation
Volume14
Issue number1-2
Publication statusPublished - 1 Jan 2014

Fingerprint

Continuous Time
Hamiltonians
Query
Costs
costs
Query Complexity
Simulation
Quantum Algorithms
simulation
Efficient Algorithms
Computing

Cite this

@article{70f950fb784746739c7a2a0eb260873e,
title = "Gate-efficient discrete simulations of continuous-time quantum query algorithms",
abstract = "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.",
author = "Berry, {Dominic W.} and Richard Cleve and Sevag Gharibian",
year = "2014",
month = "1",
day = "1",
language = "English",
volume = "14",
pages = "1--30",
journal = "Quantum Information and Computation",
issn = "1533-7146",
publisher = "Rinton Press Inc.",
number = "1-2",

}

Gate-efficient discrete simulations of continuous-time quantum query algorithms. / Berry, Dominic W.; Cleve, Richard; Gharibian, Sevag.

In: Quantum Information and Computation, Vol. 14, No. 1-2, 01.01.2014, p. 1-30.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Berry, Dominic W.

AU - Cleve, Richard

AU - Gharibian, Sevag

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84890377309&partnerID=8YFLogxK

M3 - Article

VL - 14

SP - 1

EP - 30

JO - Quantum Information and Computation

T2 - Quantum Information and Computation

JF - Quantum Information and Computation

SN - 1533-7146

IS - 1-2

ER -