Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2410.21635 · ACM Symposium on Theory of Computing (STOC)

Learning the Structure of Any Hamiltonian from Minimal Assumptions

Andrew Zhao

Published Jun 15, 2025• 3 citations
arXivHTMLPDF

Abstract

We study the problem of learning an unknown quantum many-body Hamiltonian $H$ from black-box queries to its time evolution $e^{-\mathrm{i} H t}$. Prior proposals for solving this task either impose some assumptions on $H$, such as its interaction structure or locality, or otherwise use an exponential amount of computational postprocessing. In this paper, we present algorithms to learn any $n$-qubit Hamiltonian, which do not need to know the Hamiltonian terms in advance, nor are they restricted to local interactions. Our algorithms are efficient as long as the number of terms $m$ is polynomially bounded in the system size $n$. We consider two models of control over the time evolution:~the first has access to time reversal ($t < 0$), enabling an algorithm that outputs an $ε$-accurate classical description of $H$ after querying its dynamics for a total of $\widetilde{\mathcal{O}}(m/ε)$ evolution time. The second access model is more conventional, allowing only forward-time evolutions;~our algorithm requires $\widetilde{\mathcal{O}}(\|H\|^3/ε^4)$ evolution time in this setting. Central to our results is the recently introduced concept of a pseudo-Choi state of $H$. We extend the utility of this learning resource by showing how to use it to learn the Fourier spectrum of $H$, how to achieve nearly Heisenberg-limited scaling with it, and how to prepare it even under our more restricted access models.

DOI
10.1145/3717823.3718115

Related papers

Ansatz-Free Hamiltonian Learning with Heisenberg-Limited Scaling

Hong-Ye Hu, Muzhou Ma, Weiyuan Gong +4 more

Learning the unknown interactions that govern a quantum system is crucial for quantum information processing, device benchmarking, and quantum sensing. The problem, known as Hamiltonian learning, is well understood under the assumption that interactions are local, but this assumption may not hold for arbitrary Hamiltonians. Previous methods all require high-order inverse polynomial dependency with precision, unable to surpass the standard quantum limit and reach the gold-standard Heisenberg-limited scaling. Whether Heisenberg-limited Hamiltonian learning is possible without prior assumptions about the interaction structures, a challenge we term , remains an open question. In this work, we present a quantum algorithm to learn arbitrary sparse Hamiltonians without any structure constraints using only black-box queries of the system’s real-time evolution and minimal digital controls to attain Heisenberg-limited scaling in estimation error. Our method is also resilient to state-preparation-and-measurement errors, enhancing its practical feasibility. We numerically demonstrate our ansatz-free protocol for learning physical Hamiltonians and validating analog quantum simulations, benchmarking our performance against the state-of-the-art Heisenberg-limited learning approach. Moreover, we establish a fundamental trade-off between total evolution time and quantum control on learning arbitrary interactions, revealing the intrinsic interplay between controllability and total evolution-time complexity for any learning algorithm. These results pave the way for further exploration into Heisenberg-limited Hamiltonian learning in complex quantum systems under minimal assumptions, potentially enabling new benchmarking and verification protocols.

arXiv:2502.11900•PRX Quantum•Aug 1, 2025•7 citations

Heisenberg-limited Hamiltonian learning without short-time control

Myeongjin Shin, Junseo Lee, Changhun Oh

Characterizing quantum systems by learning their underlying Hamiltonians is a central task in quantum information science. While recent algorithmic advances have achieved near-optimal efficiency in this task, they critically rely on accessing arbitrarily short-time dynamics. This reliance poses severe experimental challenges due to finite control bandwidth and transient pulse errors. In this work, we demonstrate that Heisenberg-limited Hamiltonian learning can be achieved without short-time control. We introduce a framework in which every query to the unknown dynamics has duration at least a prescribed minimum time $T$, and show that this restriction does not preclude Heisenberg-limited scaling. The key ingredient is a method for emulating the continuous quantum control required by iterative learning algorithms using only such lower-bounded evolution times. This reduces the learning task to sparse pure-state tomography. Notably, for logarithmically sparse Hamiltonians, our algorithm achieves the information-theoretically optimal $1/\varepsilon$ scaling in total evolution time for any arbitrary constant minimum evolution time $T$. For many-body (polynomially sparse) systems, we uncover a rigorous quantitative tradeoff, showing that the minimum required evolution time can be significantly relaxed from the standard limit at a polynomial cost in total evolution time. Our results affirmatively resolve a prominent open problem in the field and reveal that high-bandwidth, ultra-short pulses are not fundamentally necessary for optimal quantum learning.

quant-pharXiv:2604.27838•May 1, 2026•0 citations

Structure Learning of Hamiltonians from Real-Time Evolution

Ainesh Bakshi, Allen Liu, Ankur Moitra +1 more

We study the problem of Hamiltonian structure learning from real-time evolution: given the ability to apply$e^{-\mathrm{i}Ht}$for an unknown local Hamiltonian$H=\Sigma_{a=1}^{m}\lambda_{a}E_{a}$on$n$qubits, the goal is to recover$H$. This problem is already well-understood under the assumption that the interaction terms,$E_{a}$, are given, and only the interaction strengths,$\lambda_{a}$, are unknown. But how efficiently can we learn a local Hamiltonian without prior knowledge of its interaction structure? We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area, all while achieving the gold standard of Heisenberg-limited scaling. In particular, our algorithm recovers the Hamiltonian to$\varepsilon$error with total evolution time$\mathcal{O}(\log(n)/\varepsilon)$, and has the following appealing properties: 1)It does not need to know the Hamiltonian terms; 2)It works beyond the short-range setting, extending to any Hamiltonian$H$where the sum of terms interacting with a qubit has bounded norm; 3)It evolves according to$H$in constant time$t$increments, thus achieving constant time resolution. As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracy$\varepsilon$with total evolution time beating the standard limit of$1/\varepsilon^{2}$.

arXiv:2405.00082•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•8 citations

Out-of-control Hamiltonian Learning

Weiyuan Gong, Muzhou Ma, Sitan Chen +2 more

Learning the Hamiltonian of a many-body system from its dynamics is a central task in quantum science, yet the algorithms with the strongest provable guarantees assume some level of quantum control--fast, arbitrary single-qubit gates interleaved with time evolution, and measurements in arbitrary bases--that is beyond the capabilities of near-term analog quantum simulators. Motivated by analog atom- and ion-based platforms, we study Hamiltonian learning under minimal access models. Uniform state preparation and measurements: We first consider the setting where in every experiment, one can rotate each qubit to the same state, perform short-time evolution, and measure every qubit in the same basis. Surprisingly, we show that for generic 2-local Hamiltonians on any interaction graph, all of the parameters can be reconstructed from such experiments. Computational basis state preparation and measurements: We then consider a similarly constrained setting, but where state preparation and measurement are restricted to the computational basis. For nearest-neighbor Hamiltonians with only Pauli $X/Z$ interactions, a class which captures contemporary Rydberg atom platforms, we show that over 1D and 2D rectangular lattices, all of the parameters can be reconstructed from such experiments up to unavoidable gauges. Our protocols introduce new techniques for solving structured polynomial systems over an extensive number of parameters. Taken together, our results suggest that one can learn a great deal from the dynamics of quantum many-body systems even under the most stringent experimental constraints.

quant-pharXiv:2610.06709•Oct 6, 2026•0 citations

Near-Optimal Learning of Local Lindbladians

Itai Arad, Zhili Chen, Naixu Guo +2 more

We study the problem of learning local Lindbladians from black-box access to the physical evolution, where the goal is to estimate all Hamiltonian and dissipative coefficients. For local Lindbladians with low-intersection dissipators and local dynamical strength at most $Λ$, we design an algorithm that learns the coefficients to target accuracy $\varepsilon$, whose number of channel uses and total evolution time scale as $\widetilde{O}(Λ^2/\varepsilon^2)$ and $\widetilde{O}(Λ/\varepsilon^2)$, respectively, with only logarithmic dependence on the number of qubits. The algorithm is built directly from finite-time channel probes. It runs the unknown evolution for short times, estimates the corresponding Pauli transfer matrices from classical shadows, and converts these estimates into Lindbladian coefficients by stable local Fourier inversions. The algorithm is non-adaptive, uses no ancillas, and requires only random product states as inputs followed by random Pauli measurements. The method does not require knowing the structure of the Lindbladian in advance. We prove matching lower bounds that establish the near-optimality of the algorithm in both resources. By constructing a family of single-qubit dephasing Lindbladians, we show that any algorithm, even an adaptive one with arbitrary ancillas and measurements, requires $Ω(Λ^2/\varepsilon^2)$ channel uses and $Ω(Λ/\varepsilon^2)$ total evolution time. In particular, the lower bounds imply that the Heisenberg-limited scaling achievable for Hamiltonian learning is information-theoretically impossible once dissipative coefficients must be estimated.

quant-pharXiv:2606.20535•Jun 19, 2026•0 citations

Heisenberg-Limited Hamiltonian Learning Without Short-Time Control

Anonymous, Junseo Lee, Changhun Oh

Characterizing quantum systems by learning their underlying Hamiltonians is a central task in quantum information science. While recent algorithmic advances have achieved near-optimal efficiency in this task, they critically rely on accessing arbitrarily short-time dynamics. This reliance poses severe experimental challenges due to finite control bandwidth and transient pulse errors. In this work, we demonstrate that Heisenberg-limited Hamiltonian learning can be achieved without short-time control. We introduce a framework in which every query to the unknown dynamics has duration at least a prescribed minimum time T , and show that this restriction does not preclude Heisenberg-limited scaling. The key ingredient is a method for emulating the continuous quantum control required by iterative learning algorithms using only such lower-bounded evolution times. This reduces the learning task to sparse pure-state tomography. Notably, for logarithmically sparse Hamiltonians, our algorithm achieves the information-theoretically optimal 1 / ε scaling in total evolution time for arbitrary constant minimum evolution time T . For many-body (polynomially sparse) systems, we uncover a rigorous quantitative tradeoff, showing that the minimum required evolution time can be significantly relaxed from the standard limit at a polynomial cost in total evolution time. Our results affirmatively resolve a prominent open problem in the field and reveal that high-bandwidth, ultra-short pulses are not fundamentally necessary for optimal quantum learning.

PRX Quantum•Sep 17, 2026•0 citations
We study the problem of learning an unknown quantum many-body Hamiltonian HHH from black-box queries to its time evolution e−iHte^{-\mathrm{i} H t}e−iHt. Prior proposals for solving this task either impose some assumptions on HHH, such as its interaction structure or locality, or otherwise use an exponential amount of computational postprocessing. In this paper, we present algorithms to learn any nnn-qubit Hamiltonian, which do not need to know the Hamiltonian terms in advance, nor are they restricted to local interactions. Our algorithms are efficient as long as the number of terms mmm is polynomially bounded in the system size nnn. We consider two models of control over the time evolution:~the first has access to time reversal (t<0t < 0t<0), enabling an algorithm that outputs an εεε-accurate classical description of HHH after querying its dynamics for a total of O~(m/ε)\widetilde{\mathcal{O}}(m/ε)O(m/ε) evolution time. The second access model is more conventional, allowing only forward-time evolutions;~our algorithm requires O~(∥H∥3/ε4)\widetilde{\mathcal{O}}(\|H\|^3/ε^4)O(∥H∥3/ε4) evolution time in this setting. Central to our results is the recently introduced concept of a pseudo-Choi state of HHH. We extend the utility of this learning resource by showing how to use it to learn the Fourier spectrum of HHH, how to achieve nearly Heisenberg-limited scaling with it, and how to prepare it even under our more restricted access models.
Learning the unknown interactions that govern a quantum system is crucial for quantum information processing, device benchmarking, and quantum sensing. The problem, known as Hamiltonian learning, is well understood under the assumption that interactions are local, but this assumption may not hold for arbitrary Hamiltonians. Previous methods all require high-order inverse polynomial dependency with precision, unable to surpass the standard quantum limit and reach the gold-standard Heisenberg-limited scaling. Whether Heisenberg-limited Hamiltonian learning is possible without prior assumptions about the interaction structures, a challenge we term , remains an open question. In this work, we present a quantum algorithm to learn arbitrary sparse Hamiltonians without any structure constraints using only black-box queries of the system’s real-time evolution and minimal digital controls to attain Heisenberg-limited scaling in estimation error. Our method is also resilient to state-preparation-and-measurement errors, enhancing its practical feasibility. We numerically demonstrate our ansatz-free protocol for learning physical Hamiltonians and validating analog quantum simulations, benchmarking our performance against the state-of-the-art Heisenberg-limited learning approach. Moreover, we establish a fundamental trade-off between total evolution time and quantum control on learning arbitrary interactions, revealing the intrinsic interplay between controllability and total evolution-time complexity for any learning algorithm. These results pave the way for further exploration into Heisenberg-limited Hamiltonian learning in complex quantum systems under minimal assumptions, potentially enabling new benchmarking and verification protocols.
Characterizing quantum systems by learning their underlying Hamiltonians is a central task in quantum information science. While recent algorithmic advances have achieved near-optimal efficiency in this task, they critically rely on accessing arbitrarily short-time dynamics. This reliance poses severe experimental challenges due to finite control bandwidth and transient pulse errors. In this work, we demonstrate that Heisenberg-limited Hamiltonian learning can be achieved without short-time control. We introduce a framework in which every query to the unknown dynamics has duration at least a prescribed minimum time TTT, and show that this restriction does not preclude Heisenberg-limited scaling. The key ingredient is a method for emulating the continuous quantum control required by iterative learning algorithms using only such lower-bounded evolution times. This reduces the learning task to sparse pure-state tomography. Notably, for logarithmically sparse Hamiltonians, our algorithm achieves the information-theoretically optimal 1/ε1/\varepsilon1/ε scaling in total evolution time for any arbitrary constant minimum evolution time TTT. For many-body (polynomially sparse) systems, we uncover a rigorous quantitative tradeoff, showing that the minimum required evolution time can be significantly relaxed from the standard limit at a polynomial cost in total evolution time. Our results affirmatively resolve a prominent open problem in the field and reveal that high-bandwidth, ultra-short pulses are not fundamentally necessary for optimal quantum learning.
We study the problem of Hamiltonian structure learning from real-time evolution: given the ability to applye−iHte^{-\mathrm{i}Ht}e−iHtfor an unknown local HamiltonianH=Σa=1mλaEaH=\Sigma_{a=1}^{m}\lambda_{a}E_{a}H=Σa=1m​λa​Ea​onnnnqubits, the goal is to recoverHHH. This problem is already well-understood under the assumption that the interaction terms,EaE_{a}Ea​, are given, and only the interaction strengths,λa\lambda_{a}λa​, are unknown. But how efficiently can we learn a local Hamiltonian without prior knowledge of its interaction structure? We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area, all while achieving the gold standard of Heisenberg-limited scaling. In particular, our algorithm recovers the Hamiltonian toε\varepsilonεerror with total evolution timeO(log⁡(n)/ε)\mathcal{O}(\log(n)/\varepsilon)O(log(n)/ε), and has the following appealing properties: 1)It does not need to know the Hamiltonian terms; 2)It works beyond the short-range setting, extending to any HamiltonianHHHwhere the sum of terms interacting with a qubit has bounded norm; 3)It evolves according toHHHin constant timetttincrements, thus achieving constant time resolution. As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracyε\varepsilonεwith total evolution time beating the standard limit of1/ε21/\varepsilon^{2}1/ε2.
Learning the Hamiltonian of a many-body system from its dynamics is a central task in quantum science, yet the algorithms with the strongest provable guarantees assume some level of quantum control--fast, arbitrary single-qubit gates interleaved with time evolution, and measurements in arbitrary bases--that is beyond the capabilities of near-term analog quantum simulators. Motivated by analog atom- and ion-based platforms, we study Hamiltonian learning under minimal access models. Uniform state preparation and measurements: We first consider the setting where in every experiment, one can rotate each qubit to the same state, perform short-time evolution, and measure every qubit in the same basis. Surprisingly, we show that for generic 2-local Hamiltonians on any interaction graph, all of the parameters can be reconstructed from such experiments. Computational basis state preparation and measurements: We then consider a similarly constrained setting, but where state preparation and measurement are restricted to the computational basis. For nearest-neighbor Hamiltonians with only Pauli X/ZX/ZX/Z interactions, a class which captures contemporary Rydberg atom platforms, we show that over 1D and 2D rectangular lattices, all of the parameters can be reconstructed from such experiments up to unavoidable gauges. Our protocols introduce new techniques for solving structured polynomial systems over an extensive number of parameters. Taken together, our results suggest that one can learn a great deal from the dynamics of quantum many-body systems even under the most stringent experimental constraints.
We study the problem of learning local Lindbladians from black-box access to the physical evolution, where the goal is to estimate all Hamiltonian and dissipative coefficients. For local Lindbladians with low-intersection dissipators and local dynamical strength at most ΛΛΛ, we design an algorithm that learns the coefficients to target accuracy ε\varepsilonε, whose number of channel uses and total evolution time scale as O~(Λ2/ε2)\widetilde{O}(Λ^2/\varepsilon^2)O(Λ2/ε2) and O~(Λ/ε2)\widetilde{O}(Λ/\varepsilon^2)O(Λ/ε2), respectively, with only logarithmic dependence on the number of qubits. The algorithm is built directly from finite-time channel probes. It runs the unknown evolution for short times, estimates the corresponding Pauli transfer matrices from classical shadows, and converts these estimates into Lindbladian coefficients by stable local Fourier inversions. The algorithm is non-adaptive, uses no ancillas, and requires only random product states as inputs followed by random Pauli measurements. The method does not require knowing the structure of the Lindbladian in advance. We prove matching lower bounds that establish the near-optimality of the algorithm in both resources. By constructing a family of single-qubit dephasing Lindbladians, we show that any algorithm, even an adaptive one with arbitrary ancillas and measurements, requires Ω(Λ2/ε2)Ω(Λ^2/\varepsilon^2)Ω(Λ2/ε2) channel uses and Ω(Λ/ε2)Ω(Λ/\varepsilon^2)Ω(Λ/ε2) total evolution time. In particular, the lower bounds imply that the Heisenberg-limited scaling achievable for Hamiltonian learning is information-theoretically impossible once dissipative coefficients must be estimated.
Characterizing quantum systems by learning their underlying Hamiltonians is a central task in quantum information science. While recent algorithmic advances have achieved near-optimal efficiency in this task, they critically rely on accessing arbitrarily short-time dynamics. This reliance poses severe experimental challenges due to finite control bandwidth and transient pulse errors. In this work, we demonstrate that Heisenberg-limited Hamiltonian learning can be achieved without short-time control. We introduce a framework in which every query to the unknown dynamics has duration at least a prescribed minimum time T , and show that this restriction does not preclude Heisenberg-limited scaling. The key ingredient is a method for emulating the continuous quantum control required by iterative learning algorithms using only such lower-bounded evolution times. This reduces the learning task to sparse pure-state tomography. Notably, for logarithmically sparse Hamiltonians, our algorithm achieves the information-theoretically optimal 1 / ε scaling in total evolution time for arbitrary constant minimum evolution time T . For many-body (polynomially sparse) systems, we uncover a rigorous quantitative tradeoff, showing that the minimum required evolution time can be significantly relaxed from the standard limit at a polynomial cost in total evolution time. Our results affirmatively resolve a prominent open problem in the field and reveal that high-bandwidth, ultra-short pulses are not fundamentally necessary for optimal quantum learning.