Nathan Wiebe, University of Calgary
We introduce an efficient quantum algorithm for simulating time-dependent Hamiltonian quantum dynamics on a quantum computer and accounts fully for all computational resources, especially the per-qubit oracle query cost, which has been previously regarded as constant cost per query regardless of the number of qubits accessed.
Our algorithm works for any time-dependent Hamiltonian that satisfies specified smoothness conditions. Furthermore, our Hamiltonian need not be sparse but rather can be a sum of Hamiltonians that can be
efficiently converted to sparse Hamiltonians in the computational basis. Our other algorithmic innovations include enhancement of the ordered-exponential decomposition procedure by adaptively choosing the integration step size and by accounting for errors due to discretization of Hamiltonian matrix elements and of time.