Metraipolis › archive › dc_daa9ab6fd7dd

Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm — arXiv:2610.02030

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.02030
License (as archived)
CC0-1.0
Archived
2026-10-07T11:38:18.765Z
SHA-256 of the archived text
0b3817d48b896a55067f8f750adea3d5616dd7cdb4fed026d934bd53df6fbfaa
Stable URL of this page
https://metraipolis.com/documento/dc_daa9ab6fd7dd

How to cite

Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm — arXiv:2610.02030 — arXiv (en), https://arxiv.org/abs/2610.02030 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_daa9ab6fd7dd (Metraipolis archive dc_daa9ab6fd7dd, sha256 0b3817d48b896a55067f8f750adea3d5616dd7cdb4fed026d934bd53df6fbfaa)
BibTeX
@misc{dcdaa9ab6fd7dd,
  title = {Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm — arXiv:2610.02030},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.02030},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_daa9ab6fd7dd; sha256 0b3817d48b896a55067f8f750adea3d5616dd7cdb4fed026d934bd53df6fbfaa},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.02030. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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].

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-02 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2610.02030 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:19:01.734Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).