Learning k-body Hamiltonians via compressed sensing

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!