Hamiltonian Simulation by Qubitization

We present the problem of approximating the time-evolution operator e^{-ihat{H}t} to error ε, where the Hamiltonian hat{H}=\(langle G|otimeshat{mathcal{I}}\)hat{U}\(|Grangleotimeshat{mathcal{I}}\) is the projection of a unitary oracle hat{U} onto the state |Grangle created by another unitary oracle. Our algorithm solves this with a query complexity mathcal{O}big\(t+log({1/ε}\)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 SU(2) subspace. A large class of operator functions of hat{H} can then be computed with optimal query complexity, of which e^{-ihat{H}t} is a special case.