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.
Original language | English |
---|---|
Pages (from-to) | 1-30 |
Number of pages | 30 |
Journal | Quantum Information and Computation |
Volume | 14 |
Issue number | 1-2 |
Publication status | Published - 1 Jan 2014 |
Keywords
- Quantum computation
- Quantum query complexity