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}((tsqrt{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.
Download