We present the problem of approximating the time-evolution operator $e^{ -i\hat{ H}t}$ to error $\epsilon$, where the Hamiltonian $\hat{ H}=(\langle G|\otimes\hat{ \mathcal{ I}})\hat{ U}(|G\rangle\otimes\hat{ \mathcal{ I}})$ is the projection of a unitary oracle $\hat{ U}$ onto the state $|G\rangle$ created by another unitary oracle. Our algorithm solves this with a query complexity $\mathcal{ O}\big(t+\log({ 1/\epsilon})\big)$ 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 $\hat{ H}$ is a density matrix. A key technical result is `qubitization', which uses the controlled version of these oracles to embed any $\hat{ H}$ in an invariant $\text{ SU}(2)$ subspace. A large class of operator functions of $\hat{ H}$ can then be computed with optimal query complexity, of which $e^{ -i\hat{ H}t}$ is a special case.
Categories: quant-ph