Hamiltonian simulation with nearly optimal dependence on spectral norm

Abstract

We present a quantum algorithm for approximating the real time evolution \(e^{-iHt}\) of an arbitrary \(d\)-sparse Hamiltonian to error \(\epsilon\), given black-box access to the positions and \(b\)-bit values of its non-zero matrix entries. The complexity of our algorithm is \(\mathcal{O}((t\sqrt{d}\|H\|_{1 \rightarrow 2})^{1+o(1)}/\epsilon^{o(1)})\) queries and a factor \(\mathcal{O}(b)\) more gates, which is shown to be optimal up to subpolynomial factors through a matching query lower bound. This provides a polynomial speedup in sparsity for the common case where the spectral norm \(\|H\|\ge\|H\|_{1 \rightarrow 2}\) is known, and generalizes previous approaches which achieve optimal scaling, but with respect to more restrictive parameters. By exploiting knowledge of the spectral norm, our algorithm solves the black-box unitary implementation problem -- \(\mathcal{O}(d^{1/2+o(1)})\) queries suffice to approximate any \(d\)-sparse unitary in the black-box setting, which matches the quantum search lower bound of \(\Omega(\sqrt{d})\) queries and improves upon prior art [Berry and Childs, QIP 2010] of \(\tilde{\mathcal{O}}(d^{2/3})\) queries. Combined with known techniques, we also solve systems of sparse linear equations with condition number \(\kappa\) using \(\mathcal{O}((\kappa \sqrt{d})^{1+o(1)}/\epsilon^{o(1)})\) queries, which is a quadratic improvement in sparsity.