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.
| Language | English |
|---|---|
| Pages | 1-30 |
| Number of pages | 30 |
| Journal | Quantum Information and Computation |
| Volume | 14 |
| Issue number | 1-2 |
| Publication status | Published - 1 Jan 2014 |
Fingerprint
Cite this
}
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 journal › Article › Research › peer-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 -