Sparse Hamiltonian learning without short-time control
- Fields
- Topics
Problem
Can every polynomially sparse Hamiltonian be learned with Heisenberg-limited total evolution time when every oracle call has a fixed minimum duration?
Let
where \(c>0\) is fixed, the sum ranges over nonidentity \(n\)-qubit Pauli strings, and the nonzero coefficients and their supports are unknown. An oracle supplies only forward evolution \(e^{-iHt}\) for chosen times \(t\geq T\), where \(T>0\) is fixed independently of \(n,m,\) and \(\varepsilon\). Known controls and ancillas may be used between calls.
Can a learner output \(\widehat a_P\) with \(\max_P|\widehat a_P-a_P|\leq\varepsilon\) and success probability at least \(2/3\), using total evolution time \(\widetilde O(\operatorname{poly}(n,m)/\varepsilon)\) and polynomial query, circuit, and classical-processing costs for every Hamiltonian in Eq. (1)?
Source
Shin, Lee, and Oh explicitly pose the polynomial-sparsity, fixed-minimum-duration question in the discussion following their Theorem 2 [Shin26]. The statement is rewritten here to make its hypotheses and success criterion self-contained.
Progress
Reports do not certify correctness or automatically change the problem's status. Progress policy.
Without the fixed minimum-duration restriction, general sparse Hamiltonian learning can already achieve Heisenberg precision scaling. The ancilla-assisted protocol of Hu and coauthors has
\begin{equation} t_{\mathrm{tot}} =O\!\left(\frac{m^2\log(m/\delta)\log^2(1/\varepsilon)}{\varepsilon}\right), \tag{2} \end{equation}where \(\delta\) is the failure probability. Its access assumptions allow short-time control, so the absence of a known Pauli support alone is no longer the open issue. [Hu25]
The displayed definitions, constraints, and target bounds are recorded in Eqs. (2).
Shin, Lee, and Oh solve the minimum-duration problem for logarithmic sparsity. Their Theorem 1 gives
\begin{equation} t_{\mathrm{tot}} =\widetilde O\!\left( \min\left\{\frac{4^mT^3}{\varepsilon}, \frac{4^mT}{\varepsilon^2}\right\}\right). \tag{3} \end{equation}For \(m=O(\log n)\), this is efficient at any fixed \(T\). [Shin26]
The displayed definitions, constraints, and target bounds are recorded in Eqs. (3).
Their Theorem 2 gives the tradeoff
\begin{equation} t_{\mathrm{tot}} =\widetilde O\!\left( \min\left\{\frac{m^{K+2}T}{\varepsilon}, \frac{m^KT}{\varepsilon^2}\right\}\right), \qquad T=\Theta(m^{-1/K}),\quad K\in\mathbb N. \tag{4} \end{equation}A fixed \(K\) permits polynomial sparsity dependence but a shrinking minimum time. Taking \(K=\Theta(\log m)\) makes \(T=\Theta(1)\), at the cost of \(m^{O(\log m)}\) dependence. [Shin26]
The displayed definitions, constraints, and target bounds are recorded in Eqs. (4).
The paragraph following Theorem 2 explicitly asks for polynomial cost at polynomial sparsity and arbitrary constant \(T\). The later June 2026 work on long-time learning instead establishes recovery up to overall scale for broad ensembles satisfying an approximate-conservation identifiability condition; it does not establish the worst-case, absolute-coefficient, Heisenberg guarantee requested here. [Shin26][Pradenne26]
Comment
The open resource tradeoff concerns polynomial sparsity together with a nonshrinking minimum query duration, not merely whether long-time dynamics contain information. Real-valued programmable durations are allowed, so this is not a question about aliasing from a single fixed sampling interval or finite timing resolution. The available constant-duration generalization is quasipolynomial rather than polynomial in sparsity.
References
- [Hu25]
- H.-Y. Hu, M. Ma, W. Gong, Q. Ye, Y. Tong, S. T. Flammia, and S. F. Yelin, "Ansatz-free Hamiltonian learning with Heisenberg-limited scaling," PRX Quantum 6, 040315 (2025).DOIarXiv
- [Shin26]
- M. Shin, J. Lee, and C. Oh, "Heisenberg-limited Hamiltonian learning without short-time control," arXiv preprint (2026), version 1, 30 April 2026.arXiv
- [Pradenne26]
- C. Cedillo Vayson de Pradenne, J. Cotler, and H.-Y. Huang, "Learning Hamiltonians at Long Times," arXiv preprint (2026), version 1, 4 June 2026.arXiv