Learning k-body Hamiltonians via compressed sensing

arXiv:2410.18928 · quant-ph, cs.DS, cs.LG · Submitted 2024-12-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Learning k-body Hamiltonians via compressed sensing".

Jane: The paper was written by Muzhou Ma, Steven T. Flammia, John Preskill and Yu Tong from California Institute of Technology and Virginia Tech and Phasecraft Inc. and Duke University and Tsinghua University and AWS Center for Quantum Computing.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title and Authors: Tom: Welcome back to the show, everyone! Today we’re diving into a brand new paper that just hit arXiv, and it’s called “Learning k-body Hamiltonians via compressed sensing.” Jane, I’ve got to say, the title alone gets me excited—it’s like two of my favorite things in quantum physics finally got together.

Jane: I know exactly what you mean, Tom. Compressed sensing is this brilliant idea from classical signal processing, and seeing it applied to Hamiltonian learning feels like a natural match. The authors are Muzhou Ma, Steven Flammia, John Preskill, and Yu Tong—that’s a serious lineup. Preskill’s group at Caltech has been pushing quantum learning forward for years.

Tom: And Flammia, of course, has done tons of work on quantum characterization. So when I saw those names together, I knew this wasn’t going to be some incremental paper. They’re tackling a problem that’s been bugging people for a while: how do you learn a Hamiltonian when the interactions aren’t local?

Jane: Right, and that’s the key thing. Most previous methods relied on geometric locality—you know, qubits that are close together interact, and you can use that structure to break the problem into pieces. But this paper says, what if the interactions are completely nonlocal? What if any qubit can talk to any other qubit?

Tom: And that’s where compressed sensing comes in. It lets you exploit sparsity instead of locality. The Hamiltonian has only M unknown terms, even though there are exponentially many possible terms. So you don’t need to measure everything—you just need enough smartly chosen measurements.

Jane: Exactly. And the beauty is, they show you can do it with total evolution time that scales like M to the one-half plus one over p, over epsilon. That’s nearly Heisenberg-limited, which is the best you can hope for in quantum metrology.

Tom: Nearly Heisenberg-limited, non-adaptive, robust to noise—this is a big deal. I mean, for people trying to characterize quantum devices, this could be a game changer.

Jane: Absolutely. And I love that they’re not just giving you a protocol; they’re also proving a lower bound, so you know the scaling is essentially optimal. We’ll get into the details, but for now, let’s just say this paper is packed with results.

Tom: And we’re going to unpack all of it. Stick around, because next we’re going to talk about what they actually do in the paper—the summary, the method, and why it’s so clever.

Summary and Implications: Jane: Welcome back. We’re still on “Learning k-body Hamiltonians via compressed sensing,” and Tom, I want to get into the meat of it. The abstract promises a protocol that learns a k-body Hamiltonian with M unknown Pauli terms, and it doesn’t need geometric locality. How do they pull that off?

Tom: Great question. The first trick is something called Hamiltonian reshaping. You randomly apply Pauli operators during the evolution, and that effectively transforms the Hamiltonian into one that’s completely commuting—meaning all the terms commute with each other. That makes the eigenvalues easy to compute.

Jane: So instead of dealing with a messy, non-commuting Hamiltonian, you reshape it into something diagonal in a basis you choose. And then the eigenvalues depend linearly on the coefficients you want to learn.

Tom: Exactly. And once you have that linear relationship, you can use compressed sensing. You sample a bunch of eigenvalue differences, set up an l1-minimization problem, and recover the sparse coefficient vector. The paper shows that with enough samples—roughly M times polylog factors—you get accurate estimates.

Jane: And the total evolution time is M to the one/p plus one/two over epsilon. For p equals one that’s M to the one point five over epsilon. For p equals two it’s M over epsilon. That’s really good scaling.

Tom: It is. And here’s the kicker—they only use single-qubit control operations. No multi-qubit gates during the evolution, no adaptive feedback. That’s huge for experimentalists. You can implement this on current hardware without needing complex control.

Jane: And they’re robust to SPAM errors, which is another practical win. State preparation and measurement errors are always a pain, but they handle a constant amount of that noise.

Tom: So the implications are pretty clear: this could be the go-to method for learning Hamiltonians in systems where interactions are long-range or even all-to-all, like in some trapped ion setups or the Sachdev-Ye model they mention.

Jane: Right, the sparse SY model is a perfect example. It’s a model where every qubit can interact with every other qubit, but only a fraction of the interactions are nonzero. Previous methods either blew up exponentially or had unknown complexity. This paper gives you a clean polynomial bound.

Tom: And that’s why I’m so excited. It’s not just a theoretical curiosity—it’s a practical tool that could help us characterize real quantum systems. Next, we’re going to look at the actual improvements they make over prior work, so stay tuned.

Improvements over Prior Work: Jane: Welcome back. We’re deep into “Learning k-body Hamiltonians via compressed sensing,” and Tom, I want to talk about how this improves on what came before. Because there’s been a lot of work on Hamiltonian learning, but this paper seems to close some important gaps.

Tom: Definitely. The big one is locality. Previous methods, like the one from Huang, Tong, Fang, and Su, required something called low-intersection—each qubit only interacts with a constant number of terms. That’s a relaxation of geometric locality, but it still fails for all-to-all models.

Jane: And this paper just throws that requirement out the window. You can have every qubit interacting with every other qubit, and the method still works with polynomial overhead.

Tom: Right. And there’s also the question of adaptivity. Some recent work, like the bootstrapping approach from Bakshi and others, needed adaptive experiments—you use the results from one experiment to design the next. That’s hard to implement in practice because it requires fast feedback and multi-qubit operations.

Jane: But this protocol is completely non-adaptive. You pick all the experiments in advance, run them, and then do the classical post-processing. That’s a huge practical advantage.

Tom: And the total evolution time is better too. For the sparse SY model, they get M to the one/p plus one/two over epsilon, whereas the bootstrapping method gets M to the one plus one/p over epsilon. So for p equals one that’s M to the one point five versus M squared—a real improvement.

Jane: Plus, they handle the case where you don’t know M exactly or the Hamiltonian isn’t exactly k-body. They show the method degrades gracefully, which is important for real-world applications.

Tom: And let’s not forget the lower bound. They prove that any algorithm needs at least M over epsilon log of one over gamma total evolution time. So the scaling in M and epsilon is essentially tight, up to that square root gap.

Jane: So they’re not just giving you a protocol—they’re telling you how close it is to optimal. That’s the kind of rigor you want when you’re building quantum devices.

Tom: Exactly. And the fact that they can do all this with single-qubit operations and GHZ states makes it even more compelling. Next, we’re going to dig into the first page of the paper itself and look at some of the specific numbers and examples they present.

First Page Details: Jane: Welcome back. We’re still on “Learning k-body Hamiltonians via compressed sensing,” and Tom, I want to look at the first page more carefully. There are some concrete examples that really bring the results home.

Tom: Yeah, the sparse Sachdev-Ye model is a great one. It’s a random Heisenberg model where each interaction is present with probability p. For small p, you have a sparse Hamiltonian with M roughly n squared p terms. And they show their method learns it with total evolution time scaling like n squared p to the one/p plus one/two over epsilon.

Jane: And that’s a huge improvement over prior work. Some methods had exponential scaling in n, and others had unknown complexity because there’s no Lieb-Robinson bound for all-to-all interactions.

Tom: Right. And they also look at power-law interactions on a lattice. For alpha less than or equal to D, where the interactions are long-range, previous methods struggled. But this paper gets n to the two/p plus one over epsilon, which is polynomial and Heisenberg-limited.

Jane: For alpha greater than D, where interactions decay faster, they still get the same scaling. So regardless of the range of the interactions, this method works.

Tom: And the table they include—Table one—is really helpful. It compares their method to all the prior work across these different models, and you can see they’re either better or match the best known scaling.

Jane: One thing I appreciate is that they’re careful about the error metric. They talk about l1 and l2 errors and give operational interpretations. l1 error gives you worst-case guarantees on predicting observables, while l2 error gives you average-case guarantees for random initial states.

Tom: That’s important because it tells you what the error actually means for your application. If you care about worst-case performance, use l1. If you care about typical performance, use l2.

Jane: And they even show that the l2 error connects to the Frobenius norm of the Hamiltonian difference, which is a nice clean result.

Tom: So the first page alone is packed with results and examples. And we’ve only scratched the surface. Let’s wrap up with our final thoughts on the paper.

Conclusion: Tom: Alright, we’ve spent a lot of time on “Learning k-body Hamiltonians via compressed sensing,” and I think it’s fair to say this is one of the most impactful Hamiltonian learning papers we’ve seen in a while.

Jane: I completely agree. They’ve shown that you can learn a sparse, nonlocal Hamiltonian with nearly Heisenberg-limited scaling, using only single-qubit operations and non-adaptive experiments. That’s a combination of features that no prior method achieved.

Tom: And they backed it up with a lower bound, so we know the scaling is essentially optimal. Plus, they handled SPAM noise and modeling errors, which makes it practical for real experiments.

Jane: The examples—sparse SY model and power-law interactions—show that this isn’t just a theoretical toy. It applies to systems that are actually being studied in the lab.

Tom: And the fact that it’s robust to not knowing M exactly or the Hamiltonian not being exactly k-body means you can use it in messy, real-world scenarios.

Jane: So what’s the takeaway for our listeners? If you’re trying to characterize a quantum system with sparse, long-range interactions, this is the method to use.

Tom: And the open questions—like closing the gap between the upper and lower bounds, or extending to bosonic and fermionic systems—are exciting directions for future work.

Jane: We’ll be watching for those follow-ups. For now, thanks for joining us on this deep dive into “Learning k-body Hamiltonians via compressed sensing.” We’ll see you next time with another paper.

Tom: Take care, everyone, and keep learning!

Muzhou Ma, Steven T. Flammia, John Preskill, Yu Tong

California Institute of Technology · Virginia Tech · Phasecraft Inc. · Duke University · Tsinghua University · AWS Center for Quantum Computing

quant-ph, cs.DS, cs.LG

Submitted: 2024-12-12

Comments: 49 pages, 1 figure

DOI: 10.1109/TIT.2026.3720996

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 78/100

The gist: The paper studies the problem of learning a k-body Hamiltonian with M unknown Pauli terms that are not necessarily geometrically local.

Terminology

Summary

The paper studies the problem of learning a k-body Hamiltonian with M unknown Pauli terms that are not necessarily geometrically local. The authors propose a protocol that learns the Hamiltonian to precision ϵ with total evolution time O(M(1/2+1/p)/ϵ) up to logarithmic factors, where the error is quantified by the l p-distance between Pauli coefficients.

The main theorem (informal version) states: "There exists a learning protocol that uses N = Õ(M) independent non-adaptive experiments to learn, with probability at least 1 − δ, an estimate µ̂ of all coefficients with weight ≤ k that has l p error (1 ≤ p ≤ 2) at most ϵ, and uses a total evolution time T = Õ(M(1/p+1/2)/ϵ)."

Key features of the protocol:

  • Uses only single-qubit control operations and a GHZ state initial state

  • Is non-adaptive

  • Is robust against SPAM errors

  • Performs well even if M and k are not precisely known in advance or if the Hamiltonian is not exactly M-sparse

  • Requires neither geometric locality nor any other relaxed locality conditions

The paper also provides a lower bound: T = Ω(M/(ϵ log(1/γ))) for the total evolution time needed in this learning task, where γ is the amount of measurement error.

The authors use several key techniques:

  1. Hamiltonian reshaping: "Hamiltonian reshaping, proposed in [HTFS23] is an approach to reshape the Hamiltonian during time evolution into a new Hamiltonian Heff that is easy to learn and also contains useful information about the original Hamiltonian." The reshaping is done by applying random Pauli operators from the set Kβ (an abelian subgroup of the Pauli group) with interval τ, resulting in an effective Hamiltonian Heff = (1/2 n)Σ Q∈Kβ QHQ that consists of commuting Pauli terms.

  2. Compressed sensing: Compressed sensing provides a powerful tool to reconstruct a sparse high-dimensional vector from few measurements. The authors use a weight-k Hadamard matrix (Definition 1) as the measurement matrix, which has the restricted isometry property (RIP). The reconstruction is done via l1-minimization: minimize ∥x∥1 subject to ∥Ax − y∥2 ≤ α.

  3. Robust frequency estimation: The authors use a modified version of the robust phase estimation protocol [KLY15] to estimate eigenvalue differences with Heisenberg-limited scaling and SPAM robustness.

  4. Randomized basis selection: "uniformly randomly choosing β is a good strategy. Since each Pauli term P in the Hamiltonian is k-body, for a uniformly randomly generated β, P ∈ Kβ with probability at least 3(−k). It therefore takes L = 3 k log(M/δ basis) samples of β to ensure that all the M terms are included in at least one of the L instances with probability at least 1 − δ basis."

The learning protocol works as follows:

  1. Phase estimation experiments (Definition 3): Prepare the initial state (1/√2)(0⟩ β + b⟩ β), let the system evolve for time t while applying random Pauli operators from Kβ with interval τ, then measure observables X β b or Y β b to obtain ±1 outcomes.

  2. Learning a completely commuting Hamiltonian: For the effective Hamiltonian Heff, the relation between eigenvalues and coefficients is λ = H(k)µ β(k), where H(k) is the weight-k Hadamard matrix. The authors generate Γ independent samples of rows of H(k), form matrix A, and solve the l1-minimization problem.

  3. Randomized basis selection: Generate L = 3 k log(M/δ basis) independent samples of β to ensure all M terms are covered.

The main theorem (Theorem 8) states: "We assume that the quantum system is evolving under a k-body Hamiltonian with M terms (Definition 2). With N exp independent non-adaptive (β, b j, t j, τ)-phase estimation experiments (Definition 3), j = 1, 2, · · ·, N exp, with the SPAM error (Definition 4) satisfying ϵ SPAM ≤ 1/(3√2), we can obtain estimates µ̂ P for every P ∈ P n(k) such that, with probability at least 1 − δ, (Σ P∈P n(k)I µ̂ P − µ P p)(1/p) ≤ ϵ for 1 ≤ p ≤ 2."

The resource requirements are: N exp = Õ(3 k M), T = Õ(9 k M(1/p+1/2)/ϵ), and τ = Ω(3(−k)ϵ/(M(1/p+3/2) log(M/δ))).

The protocol is robust to two types of modeling errors:

  1. If the Hamiltonian contains more than M terms (but all terms are k-body), an extra error term σ M(µ)1 is included in the estimation error.

  2. If the terms are not exactly k-body, the error bound includes an additional term involving ϵ(k), an upper bound of ∥µ̄ β(k)∥1.

The classical post-processing involves solving l1-minimization problems. The authors show this can be done in polynomial time via a bisection procedure (Algorithm 1) that solves convex quadratic programs. Theorem 10 states: The approximate solution x̃ is obtained through Algorithm 5.6.2 which runs in time poly(n, Γ, log(1/ν)).

Theorem 11 states: "Given integers n and M, real numbers ϵ, δ ∈ (0, 1), and a set P1, P2,..., P M ∈ P n I representing the M n-qubit Pauli terms in the Hamiltonian, we consider any learning algorithm with a total evolution time T and a constant measurement noise γ ∈ (0, 0.5)... Suppose that such a learning algorithm satisfies that for an n-qubit Hamiltonian H = Σ a=1 M µ a P a with any unknown parameters µ a ≤ 1, after multiple rounds of noisy experiments, the algorithm can estimate any µ = (µ1,..., µ M) to ϵ1-error in the l1-norm in expectation value averaged over experimental outcomes. Then, T ≥ M/(ϵ1 e log(1/γ))."

The proof uses Assouad's lemma and a bound on the total variation distance between output distributions of adaptive experiments with different Hamiltonians.

  • l1-norm: the l1-error bound provides us with a worst case guarantee on how well we can predict expectation values of observables. Specifically, ⟨O⟩ ρ(t) − ⟨O⟩ ρ′(t) ≤ 2t∥O∥∞ ∥µ − µ′∥1.

  • l2-norm: an l2-error bound guarantees the average accuracy of predicting the expectation value of a low-rank observable for initial states drawn from a 2-design. Specifically, E[Tr[Oρ(t)] − Tr[Oρ′(t)]2] ≤ 2t2∥O∥22 ∥µ − µ′∥22.

The paper discusses two applications:

  1. Sparse Sachdev-Ye model: For the Hamiltonian H SY = Σ 1≤i<j≤n µ ij(σ i x σ j x + σ i y σ j y + σ i z σ j z), the total evolution time is T = Õ((n2p)(1/p+1/2)/ϵ).

  2. Power law interaction Hamiltonians: For H = Σ i≤j H ij where ∥H ij∥ ≤ 1/(1 + d(i,j) α), the total evolution time is T = Õ(n(2/p+1)/ϵ), regardless of whether α ≤ D or α > D.

Improvements for AI systems

Based on the paper, here are specific improvements for AI systems:

Improvement: Implement a compressed sensing-based algorithm that learns unknown k-body Hamiltonians with M Pauli terms from time evolution experiments, without requiring geometric locality assumptions.

What the improved AI system can do:

  • Learn Hamiltonians with non-local interactions (e.g., sparse Sachdev-Ye models, power-law interactions) that previous methods cannot handle efficiently

  • Achieve total evolution time scaling of O(M(1/p+1/2)/ε) for l p error, nearly reaching the Heisenberg limit

  • Operate non-adaptively with only single-qubit control operations and GHZ state preparation

  • Remain robust to constant SPAM errors and modeling errors (non-exactly sparse or non-exactly k-local Hamiltonians)

Abstract

We study the problem of learning a k-body Hamiltonian with M unknown Pauli terms that are not necessarily geometrically local. We propose a protocol that learns the Hamiltonian to precision epsilon with total evolution time O (M 1/2+1/p/epsilon) up to logarithmic factors, where the error is quantified by the p-distance between Pauli coefficients. Our learning protocol uses only single-qubit control operations and a GHZ state initial state, is non-adaptive, is robust against SPAM errors, and performs well even if M and k are not precisely known in advance or if the Hamiltonian is not exactly M-sparse. Methods from the classical theory of compressed sensing are used for efficiently identifying the M terms in the Hamiltonian from among all possible k-body Pauli operators. We also provide a lower bound on the total evolution time needed in this learning task, and we discuss the operational interpretations of the 1 and squared error metrics. In contrast to most previous works, our learning protocol requires neither geometric locality nor any other relaxed locality conditions.

Sources

Related papers