arXiv：cs.LG· Francisco Escudero Guti\'errez, Junseo Lee, Sebastian Zur·· 3 小时前AI 评分42
Hamiltonian 局部性测试与认证无法达到海森堡极限
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
AI 导读
研究证明，在只能访问时间演化算符而无法访问其逆算符的模型下，判断 Hamiltonian 是否为 k-local 或与所有 k-local Hamiltonian 相距 ε，需要 Ω(1/ε²) 的总演化时间，与 Kallaugher 和 Liang（TQC'25）的上界吻合。
正文
Abstract:We establish lower bounds for Hamiltonian property testing with access to the time-evolution operator but not its inverse. Each experiment may query the time-evolution operator multiple times, and distances between Hamiltonians are measured in the normalized Frobenius norm.
In this model, we show that testing whether a Hamiltonian is $k$-local or $\varepsilon$-far from every $k$-local Hamiltonian requires $\Omega(1/\varepsilon^2)$ total evolution time, matching the upper bound of Kallaugher and Liang (TQC'25). We also prove that testing whether an unknown Hamiltonian equals a target Hamiltonian or is $\varepsilon$-far from it requires $\Omega(1/\varepsilon^2)$ total evolution time, matching the upper bound of Sinha and Tong (2025). These are the first lower bounds for natural problems in Hamiltonian learning and testing that rule out Heisenberg-limited scaling of $1/\varepsilon$.
As a third result, we show that amplitude estimation to precision $\varepsilon$ requires $\Omega(1/\varepsilon^2)$ total time evolution, recovering the result of Tang and Wright (QIP'26) in the continuous-time query model. All three results follow from the hardness of distinguishing the zero Hamiltonian from a suitably chosen ensemble of random Hamiltonians. We establish this hardness by adapting the continuous-time adversary method to forward Hamiltonian evolution.
| Comments: | 28 pages |
| Subjects: | Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.03205 [quant-ph] |
| (or arXiv:2610.03205v1 [quant-ph] for this version) | |
| https://doi.org/10.48550/arXiv.2610.03205 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Francisco Escudero Gutiérrez [view email]
[v1]
Fri, 2 Oct 2026 12:21:49 UTC (104 KB)
来源：arXiv：cs.LG · arxiv.org