REVIEW
Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm
Quantum Physics · Submitted 1 Oct 2026 · 32 references
Pith's verdict: Theorem 1's query bound is real and well-supported; the gate bound rests on the least-checked estimates, but the risk is contained and the paper deserves a serious referee.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Simulating a $d$-sparse Hamiltonian with $O(t\Lambda\sqrt{d} + \sqrt{d}\log(1/\varepsilon))$ queries, matching the lower bound in the large-time regime.
The reading
What carries the argument
Three components carry the argument. The sparse-entry lifting is an isometry $V\lvert i\rangle = d^{-1/2}\sum_{\ell}\lvert i,\ell\rangle$ together with an operator $M$ built from $2\times2$ transpose-pair blocks of entries, satisfying $H = 2\sqrt{d\Lambda}\,V^\dagger M V$ with the compressed second-moment bound $V^\dagger M^2 V \preceq \frac14 I$; the second inequality is where the $1\to2$ norm promise enters, because it bounds the compressed moment even though $\lVert M\rVert$ can be of order $\sqrt{d}$. The transfer response is the function $\Phi_t(z) = \exp[-t\sqrt{d\Lambda}\,V^\dagger(I+zU_M)(I-zU_M)^{-1}V]$ formed by feeding the private output of a unitary coupling $W_t$ back through the Cayley query $U_M = (M+iI/2)(M-iI/2)^{-1}$, whose boundary value at $z=1$ equals $e^{-itH}$, so simulation reduces to evaluating the boundary family $\theta \mapsto e^{-itH_\theta}$ at $\theta=0$. The phase-twisted clock realizes that evaluation with a real even signed kernel $\kappa_{m,p}(\theta)$ that is localized near zero and exactly reproduces Fourier modes up to order $p$, factored as the cross-spectrum of two clock states so that one routed circuit and one round of oblivious amplitude amplification suffice; the gate realization replaces the analytic coupling by a Fourier-diagonal circuit on a grid with logarithmic address size.
Extended reading notes
Core claim
The paper's central claim, stated in its own terms, is that sparse Hamiltonian simulation admits a query-optimal algorithm using the $1\to2$ norm: for a Hermitian $d$-sparse $H$ with known $\Lambda \ge \lVert H\rVert_{1\to2}$, the unitary $e^{-itH}$ can be implemented to operator-norm error $\varepsilon \le 1/2$ in $O(\tau + \sqrt{d}\log(2/\varepsilon))$ queries with $\tau = t\Lambda\sqrt{d}$, and in $O(\tau)$ queries when $t\Lambda \ge \log(2/\varepsilon)$. The second estimate is worst-case optimal for $d > 1$ against the dimension-independent lower bound, so the subpolynomial factors in the prior state of the art are replaced by an additive logarithmic precision term. The same construction yields Corollary 4, implementing a $d$-row-sparse unitary and its adjoint with $O(\sqrt{d}\log(2/\varepsilon))$ queries; at constant error this is $\Theta(\sqrt{N})$ for dense unitaries, settling the Berry\,--\,Childs open problem. Theorem 3 realizes the simulator with $O(Q_{\mathrm{sim}})$ 1- and 2-qubit gates where the query scale dominates, up to oracle gate costs and polynomial overhead in the input bit lengths and logarithmic precision parameters.
Load-bearing premise
The gate-efficient realization (Theorem 3) rests on the claim that replacing the continuous coupling by a finite Fourier grid accumulates error only linearly across the $R$ routed interactions, justified by bounding the derivative of every exact forward history inside the polynomial reachable class $F^{sc}_{R-1}(\tau) = \{x \mapsto e^{-x}f(x) : \deg f \le R-1\}$ with factor $L_R(\tau) = 1 + R^2/\min\{\tau,1\}$; the query-complexity theorem (Theorem 1) does not depend on this estimate, but the gate count does.
Editorial extensions
If this is right
- For $d > 1$ and $t\Lambda \ge \log(2/\varepsilon)$, the query bound $O(t\Lambda\sqrt{d})$ matches the dimension-independent worst-case lower bound, so sparsity, time, and norm dependence are simultaneously optimal in that regime.
- Corollary 4 implements a $d$-row-sparse black-box unitary and its adjoint with $O(\sqrt{d}\log(2/\varepsilon))$ queries; at constant error this is $\Theta(\sqrt{N})$ for dense $N\times N$ unitaries, resolving the Berry\,--\,Childs upper-bound question.
- The spectral-norm formulation (Corollary 2) gives $O(t\sqrt{d}\,\Gamma + \sqrt{d}\log(2/\varepsilon))$ queries from a known bound $\Gamma \ge \lVert H\rVert$, covering Hamiltonian simulation normalized by spectral norm.
- The sparse quantum linear systems application yields $O(\kappa\sqrt{d}\,\mathrm{polylog}(\kappa/\varepsilon))$ queries under standard sparse-access and state-preparation oracles, replacing subpolynomial overhead with polylogarithmic factors.
- Theorem 3 realizes the simulator with a gate count linear in the query scale, up to oracle circuit costs and polynomial overhead in input bit lengths and logarithmic precision parameters, with a qubit count adding only logarithmic-size address registers.
Reading between the lines
- Reducing simulation to evaluating a transfer-response boundary value at a single phase suggests a template: any task expressible as $\int \kappa(\theta) e^{-iH_\theta} d\theta$ with a factorable signed kernel may inherit the additive-logarithm precision term, potentially transferring to time-dependent or non-Hermitian settings.
- The phase-twisted clock factorizes a signed kernel as one cross-spectrum, avoiding an LCU over multiple routed circuits, so similar factorizations could reduce distribution-over-circuits overhead in other phase-integral algorithms.
- The linear-in-$\tau$ query growth together with the linear gate overhead makes the algorithm's asymptotic resource profile directly usable, though the absolute constants in the $O(\cdot)$ bounds are not examined.
- The gate bound's dependence on the reachable polynomial class suggests sensitivity to oracle noise: perturbed entry values that push histories outside $F^{sc}_{R-1}(\tau)$ could inflate the required grid, a regime the paper does not analyze.
Original 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].
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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].
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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}$. | contribution 0.99 | 0.95 | 0.19 | asserted 1.00 |
| s1 | 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. | result 0.96 | 0.93 | 0.63 | asserted 1.00 |
| s2 | This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. | interpretation 0.66 | 0.82 | 0.23 | asserted 1.00 |
| s3 | For $d>1$ and $t\Lambda\ge\log(2/\epsilon)$, the bound matches the worst-case lower bound. | result 0.61 | 0.78 | 0.19 | asserted 1.00 |
| s4 | A known spectral-norm upper bound may also be used in place of $\Lambda$. | method 0.33 | 0.37 | 0.03 | hedged possibility 0.95 |
| s5 | 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. | result 0.95 | 0.90 | 0.07 | asserted 1.00 |
| s6 | 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. | result 0.73 | 0.94 | 0.08 | asserted 1.00 |
| s7 | 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. | contribution 0.66 | 0.95 | 0.06 | asserted 1.00 |
| s8 | 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]. | interpretation 0.55 | 0.89 | 0.21 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.