Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances

Technical Summary: Nearly Optimal Algorithms to Learn Sparse Quantum Hamiltonians in Physically Motivated Distances

1. Problem Statement

The paper addresses the problem of learning an unknown $n$-qubit Hamiltonian $H$ that is $s$-sparse in the Pauli basis (i.e., it has at most $s$ non-zero Pauli coefficients). The learning algorithm has access to the Hamiltonian via its time-evolution operator $U(t) = e^{-iHt}$.

The authors identify two critical gaps in existing literature:

1. Lack of Optimality: Many existing algorithms lack matching lower bounds to establish if they are optimal.
2. Physically Opaque Metrics: Previous works often measure estimation quality using mathematically convenient distances (e.g., $\ell_\infty$ or $\ell_2$ norms of Pauli coefficients) that lack direct physical interpretation regarding the distinguishability of the underlying quantum systems.

The core question posed is: What is the optimal complexity of Hamiltonian learning in physically meaningful worst-case distances?

2. Methodology and Techniques

A. Physically Motivated Distances
The authors introduce two new distance metrics that quantify the distinguishability of Hamiltonians based on operational scenarios:

1. Time-Constrained Distance ($d_T$): Defined as the maximum diamond distance between the time-evolution channels of two Hamiltonians over a bounded time interval $[0, T]$. It quantifies the best probability of distinguishing Hamiltonians by preparing a state, evolving it for time $t \le T$, and measuring.
2. Temperature-Constrained Distance ($d_B$): Defined as the maximum trace distance between the Gibbs states (thermal states) of two Hamiltonians over a bounded inverse temperature range $[0, B]$. It quantifies distinguishability via thermal states.

The authors prove that learning in the time-constrained distance is equivalent to learning in the operator norm ($\|H_1 - H_2\|_{op}$), and that upper bounds in the operator norm imply upper bounds in the temperature-constrained distance.

B. The Isolation Technique (Valiant-Vazirani Inspired)
A central technical contribution is a novel isolation technique inspired by the Valiant-Vazirani theorem. This technique allows the algorithm to "isolate" a single Pauli coefficient of a sparse Hamiltonian even when the full Pauli support is unknown.

• Mechanism: By randomly selecting a set of Pauli operators $Q_1, \dots, Q_r$ and constructing a modified Hamiltonian $H_{Q_1, \dots, Q_r}$ via conjugation, the algorithm ensures that with probability $\Omega(1/s)$, only a specific target Pauli term $P$ commutes with all $Q_i$.
• Result: This effectively filters the Hamiltonian evolution to isolate the dynamics of a single Pauli term $e^{-ith_P P}$, allowing for efficient sampling and estimation.

C. Algorithmic Structure
The learning algorithm proceeds in two stages:

1. Effective Support Learning: Using the isolation technique and Pauli sampling, the algorithm identifies a set $\mathcal{P}$ of size $\tilde{O}(s)$ that contains the $\epsilon$-effective support of $H$ (all Pauli terms with coefficients $|h_P| \ge \epsilon$).
2. Parameter Estimation: Once the support is identified, the algorithm uses the isolation technique again to estimate each Pauli coefficient $h_P$ individually to within error $\epsilon$.

3. Key Results

Upper Bounds (Algorithm Performance)
The authors present an algorithm that learns an $s$-sparse Hamiltonian with bounded operator norm:

• Experiments: $\tilde{O}(s \log(1/\epsilon))$ experiments.
• Total Evolution Time: $\tilde{O}(s^2/\epsilon)$.
• Distances: The algorithm achieves $\epsilon$-learning in both the time-constrained and temperature-constrained distances.
• Robustness: The algorithm is robust to constant amounts of state preparation and measurement (SPAM) errors and requires no ancilla qubits (a modification of the main algorithm removes the need for ancillas used in standard Pauli sampling).
• Heisenberg Scaling: The total evolution time scales as $1/\epsilon$, achieving the Heisenberg limit, which is optimal for the dependence on $\epsilon$.

Lower Bounds (Optimality)
The authors establish fundamental limits for any learning algorithm with $O(n)$ ancilla qubits:

• Experiment Lower Bound: $\Omega((s/n) \log(1/\epsilon) + s)$. This demonstrates that the algorithm's dependence on $s$ and $\log(1/\epsilon)$ is nearly optimal.
• Time Lower Bound: $\Omega(\sqrt{s}/\epsilon)$ for operator norm learning. This establishes a gap between the algorithm's upper bound of $\tilde{O}(s^2/\epsilon)$ and the theoretical lower bound, indicating that while the number of experiments is nearly optimal, the total evolution time scaling is not yet optimal.

Intermediate Improvements
As a byproduct, the paper provides an algorithm to learn every Pauli coefficient of an $s$-sparse Hamiltonian in $\tilde{O}(s \log(1/\epsilon))$ experiments and $\tilde{O}(s/\epsilon)$ total time. This improves upon several recent concurrent works (e.g., [Zha25], [ADE25], [HMG+25], [ST25]) which had higher polynomial dependencies on $s$ and $1/\epsilon$.

4. Significance and Claims

The paper claims to provide the first nearly-optimal Hamiltonian learning result with respect to the number of experiments in a physically meaningful distance.

• Physical Relevance: By shifting the metric from abstract coefficient norms to time-constrained diamond distance and temperature-constrained trace distance, the results directly relate to experimental capabilities (finite evolution time and finite temperature).
• Optimality: The work establishes that the number of experiments required is essentially optimal, matching the derived lower bounds up to logarithmic factors.
• Generality: Unlike many prior works, this algorithm does not assume prior knowledge of the Pauli support, nor does it require the Hamiltonian to be local or geometrically structured; it only assumes sparsity.
• Theoretical Bridge: The paper rigorously connects the operator norm (a standard mathematical tool) to physical distinguishability metrics, showing that for bounded time and temperature budgets, learning in the operator norm is sufficient for learning in these physical distances.

The authors acknowledge that while the experiment count is nearly optimal, the total evolution time scaling ($\tilde{O}(s^2/\epsilon)$) leaves room for improvement, as the lower bound is $\Omega(\sqrt{s}/\epsilon)$. They identify finding the optimal evolution time as a primary direction for future work.