Not checkedNot checked for notices yet.
Hamiltonian Simulation by Qubitization
Guang Hao Low, Isaac L. Chuang
Quantum · 2019
doi:10.22331/q-2019-07-12-163 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
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.
Abstract licence: CC BY
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.