The continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuously in time. We show that any quantum algorithm in this model whose total query time is T can be simulated by a quantum algorithm in the discrete-time query model that makes O(T log T / loglog T) subset O~(T) queries. This is the first such upper bound that is independent of the driving operations (i.e., it holds even if the norm of the driving Hamiltonian is very large). A corollary is that any lower bound of T queries for a problem in the discrete-time query model immediately carries over to a lower bound of Omega(T loglog T / log T) subset Omega~(T) in the continuous-time query model.
The continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuously in time. We show that any quantum algorithm in this model whose total query time is T can be simulated by a quantum algorithm in the discrete-time query model that makes O(T log T / loglog T) subset O~(T) queries. This is the first such upper bound that is independent of the driving operations (i.e., it holds even if the norm of the driving Hamiltonian is very large). A corollary is that any lower bound of T queries for a problem in the discrete-time query model immediately carries over to a lower bound of Omega(T loglog T / log T) subset Omega~(T) in the continuous-time query model.
Quantum query complexity is known to be characterized by the so-called quantum adversary bound. While this result has been proved in the standard discrete-time model of quantum computation, it also holds for continuous-time (or Hamiltonian-based) quantum computation, due to a known equivalence between these two query complexity models. In this work, we revisit this result by providing a direct proof in the continuous-time model. One originality of our proof is that it draws new connections between the adversary bound, a modern theoretical computer science technique, and early theorems of quantum mechanics. Indeed, the proof of the lower bound is based on Ehrenfest's theorem, while the upper bound relies on the Adiabatic theorem, as we construct an optimal adiabatic quantum query algorithm.
Quantum query complexity is known to be characterized by the so-called quantum adversary bound. While this result has been proved in the standard discrete-time model of quantum computation, it also holds for continuous-time (or Hamiltonian-based) quantum computation, due to a known equivalence between these two query complexity models. In this work, we revisit this result by providing a direct proof in the continuous-time model. One originality of our proof is that it draws new connections between the adversary bound, a modern technique of theoretical computer science, and early theorems of quantum mechanics. Indeed, the proof of the lower bound is based on Ehrenfest's theorem, while the upper bound relies on the adiabatic theorem, as it goes by constructing a universal adiabatic quantum query algorithm. Another originality is that we use for the first time in the context of quantum computation a version of the adiabatic theorem that does not require a spectral gap.
We give a query-optimal algorithm for simulating a general n-qubit time-dependent Hamiltonian H(t) on [0,T], assuming that H is Lipschitz continuous and ∥H(t)∥≤α. In the standard $\mathrm{HAM\mbox{-}T}$ access model, the algorithm approximates the time-ordered propagator UH(T) to error ε using O(αT+log(e+log(1/ε)/(αT))log(1/ε)) $\mathrm{HAM\mbox{-}T}$ queries. This matches the known query lower bound for time-independent Hamiltonians, showing that time dependence incurs no asymptotic query overhead.
Our method first constructs a one-query transducer that, given an auxiliary state, implements an approximation to UH(T) and returns the state unchanged. A weighted combination of circuits that apply the transducer different numbers of times makes the error caused by omitting this state decay factorially, yielding the stated optimal precision dependence. For time-independent Hamiltonians, the same method also gives a query-optimal alternative to qubitization.
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.
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.
Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating nand trees that runs in time O ( √ N log N) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N 1/2+ǫ) queries in the conventional quantum query model, for any fixed ǫ> 0. A nand tree of depth n is a balanced binary tree whose internal vertices represent nand gates. Placing bits x1,...,x2 n at the leaves, the root of the nand tree evaluates to the function fn(x1,...,x2 n), where fn: {0, 1} 2n → {0, 1} is defined recursively as follows. For n = 0, f0(x) = x, and for n> 0, fn(x1,..., x2 n) = ¬ ( fn−1(x1,..., x 2 n−1) ∧ fn−1(x 2 n−1 +1,...,x2 n)). (1) The goal of the nand tree problem is to evaluate fn(x1,..., x2 n), making as few queries to the bits x1,..., x2 n as possible. The optimal classical randomized algorithm for this problem makes Θ(N 0.753) queries, where N = 2 n [7, 8, 9]. Until now, no better quantum algorithm was known, whereas the best known quantum lower bound is only Ω ( √ N) [1]. Here we show that for any fixed ǫ> 0, the quantum query complexity of evaluating nand trees is O(N 1/2+ǫ).