Optimal certification of constant-local Hamiltonians

2025/12/10 by Lee, Junseo, Shin, Myeongjin
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2512.09778

Abstract

We study the problem of certifying local Hamiltonians from real-time access to their dynamics. Given oracle access to e^-itH for an unknown k-local Hamiltonian H and a fully specified target Hamiltonian H₀, the goal is to decide whether H is exactly equal to H₀ or differs from H₀ by at least ε in normalized Frobenius norm, while minimizing the total evolution time. We introduce the first intolerant Hamiltonian certification protocol that achieves optimal performance for all constant-locality Hamiltonians. For general n-qubit, k-local, traceless Hamiltonians, our procedure uses O(c^k/ε) total evolution time for a universal constant c, and succeeds with high probability. In particular, for O(1)-local Hamiltonians, the total evolution time becomes Θ(1/ε), matching the known Ω(1/ε) lower bounds and achieving the gold-standard Heisenberg-limit scaling. Prior certification methods either relied on implementing inverse evolution of H, required controlled access to e^-itH, or achieved near-optimal guarantees only in restricted settings such as the Ising case (k=2). In contrast, our algorithm requires neither inverse evolution nor controlled operations: it uses only forward real-time dynamics and achieves optimal intolerant certification for all constant-locality Hamiltonians.

Citations

• Certifying and learning quantum Ising Hamiltonians
• Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
• Improved Hamiltonian learning and sparsity testing through Bell sampling
• Hamiltonian Locality Testing via Trotterized Postselection
• Ansatz-free Hamiltonian learning with Heisenberg-limited scaling
• Efficient Hamiltonian, structure and trace distance learning of Gaussian states
• Testing and learning structured quantum Hamiltonians
• Learning k-body Hamiltonians via compressed sensing
• Learning the structure of any Hamiltonian from minimal assumptions
• Simple algorithms to test and learn local Hamiltonians
• Quantum Hamiltonian Learning for the Fermi-Hubbard Model
• Learning quantum Hamiltonians at any temperature in polynomial time
• Heisenberg-limited Hamiltonian learning for interacting bosons
• Efficient and robust estimation of many-qubit Hamiltonians
• Learning stabilizer states by Bell sampling
• Simulating physics with computers

Related

• Quantum Hamiltonian Certification
• Simple algorithms to test and learn local Hamiltonians
• Hamiltonian Locality Testing via Trotterized Postselection
• Certifying and learning quantum Ising Hamiltonians
• Testing and learning structured quantum Hamiltonians