Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm

Abstract:We give a quantum algorithm for simulating a $d$-sparse Hermitian Hamiltonian $H$, assuming a known upper bound $\Lambda$ on its maximum column Euclidean norm $\|H\|_{1\to2}$. For $t\Lambda\ge1/2$, simulation with operator-norm error $\epsilon$ uses \[ O\!\left(t\Lambda\sqrt d+\sqrt d\log(2/\epsilon)\right) \] sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For $d>1$ and $t\Lambda\ge\log(2/\epsilon)$, the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of $\Lambda$. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters. As applications, we obtain $O(\kappa\sqrt d\,\mathrm{polylog}(\kappa/\epsilon))$ queries for solving $d$-sparse quantum linear systems with $\|A\|\le1$ and $\|A^{-1}\|\le\kappa$, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most $d$ nonzero entries per row and column using $O(\sqrt d\log(2/\epsilon))$ queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields $\Theta(\sqrt N)$ queries for arbitrary $N\times N$ unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].

arXiv:2610.02030 [quant-ph]

(or arXiv:2610.02030v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.02030 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.