A big thanks to my coauthors for the great collaboration! Hopefully you enjoy reading the paper as much as we did writing it, despite the approaching QIP deadline :)

Again, this result generalizes to k-local Hamiltonians for k>2. While the algorithm is sample- and time-efficient, we don't know if it is optimal, because we lack matching lower bounds so far. So we ask: What is the optimal sample-complexity of
certifying Ising Gibbs states?

In our final result, we give an algorithm for certifying Ising Gibbs
states in trace norm that is both sample and time-efficient, thereby solving a question posed by Anshu hdsr.mitpress.mit.edu/pub/3x2sd8nq...

This one actually generalizes to k-local and does not need any additional assumptions (e.g. on the degree of the interaction graph). Whether one can find a better algorithm that is also time efficient is an interesting open problem.

Secondly, we design an algorithm for learning Ising Gibbs states in trace norm that is sample-efficient in all parameters. Previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state) but suffered from exponential sample complexity in the inverse temperature.

To our knowledge, this is the first nearly-optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Lemma from Fourier analysis. Curiously, this Lemma is the reason that our results do not seem to easily generalize to k-local Hamiltonians for k>2.

First, we show that certifying an Ising Hamiltonian (checking whether it is identical to some H_0 or far from it) in
normalized Frobenius norm via access to its time-evolution operator requires only O(1/ε) evolution time. This matches the known lower bounds up to a logarithmic factor.

Thanks to Tim Möbus, Tuvia Gefen, Yu Tong, Albert H. Werner and Cambyse Rouzé for the great collaboration!

Our main technical tool is a new adiabatic approximation for general Lindbladian evolutions with unbounded generators which should also be helpful elsewhere. For example, we can quantify with it how photon-driven dissipation leads to an effective evolution on the code space for bosonic cat codes.

Before, we could either do Heisenberg-limited learning for Bose-Hubbard type models scirate.com/arxiv/2307.0..., or learn arbitrary Hamiltonians with engineered dissipation, but not with Heisenberg scaling scirate.com/arxiv/2307.1.... Our new paper shows that you can have the best of both worlds.

Thanks to my PhD student Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel and @henryyuen.bsky.social for the great collaboration! And congratulations to Simon for his first paper.

In the longer term, our aim is to be able to put NLQC tasks into classes of equally hard problems, like complexity classes. This would allow us to identify the hard NLQC problems that we would like to use for quantum position verification, because they are hard for attackers to solve.

In particular, we have shown that two protocols for quantum position verification, the f-route and the f-measure protocol, are equally secure, i.e., if you can attack one, you can attack the other. This gives the first subexponential upper bound on the entanglement needed to attack f-measure.

Thanks to my coauthors for the great collaboration!

To unite these different phenomena, we consider multimeters, i.e., collections of measurements. Many of them, e.g., compatible measurements, classical simulations of measurements, or the compression of measurements can be viewed as factorizations of these multimeters through different state spaces.