Hamiltonian Simulation by Qubitization

Guang Hao Low; Isaac L. Chuang

doi:10.22331/q-2019-07-12-163

paper

Hamiltonian Simulation by Qubitization

arXiv:1610.06546 · doi:10.22331/q-2019-07-12-163

Abstract

We present the problem of approximating the time-evolution operator $e^{- i H^t}$ to error $ε$ , where the Hamiltonian $H^= (⟨ G ∣ \otimes I^) U^(∣ G ⟩ \otimes I^)$ is the projection of a unitary oracle $U^$ onto the state $∣ G ⟩$ created by another unitary oracle. Our algorithm solves this with a query complexity $O (t + lo g (1/ ε))$ to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are $d$ -sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where $H^$ is a density matrix. A key technical result is `qubitization', which uses the controlled version of these oracles to embed any $H^$ in an invariant $SU (2)$ subspace. A large class of operator functions of $H^$ can then be computed with optimal query complexity, of which $e^{- i H^t}$ is a special case.

23 pages, 1 figure; v2: updated notation; v3: accepted version

Hamiltonian Simulation by Qubitization

Abstract

References in corpus (15)

Cited by in corpus (504)