# Hamiltonian Simulation by Qubitization. (arXiv:1610.06546v3 [quant-ph] UPDATED)

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.