Francisco Escudero Gutiérrez

We study the problems of certifying and learning local quantum Hamiltonians and their associated Gibbs states. We first address Hamiltonian certification given real-time access to the dynamics of an unknown k-local Hamiltonian. Given oracle access to its time-evolution operator and a fully specified target Hamiltonian, the task is to decide whether the two Hamiltonians are identical or differ by at least a prescribed accuracy in normalized Frobenius norm, while minimizing the total evolution time. We introduce the first certification protocol that achieves optimal performance for all constant-locality Hamiltonians. For general n-qubit, k-local, traceless Hamiltonians, our algorithm succeeds with high probability using total evolution time that scales inversely with the target accuracy, and for constant locality this matches the fundamental lower bound, achieving Heisenberg-limit scaling. In contrast to prior approaches, our method requires neither inverse evolution nor controlled operations, and relies only on forward real-time dynamics. We then turn to thermal states generated by local Hamiltonians. We develop algorithms for both learning and certifying Gibbs states that are fully sample-efficient in all relevant parameters. For polynomially bounded temperature, our methods achieve exponential improvements over general quantum state tomography. While the learning algorithm is inherently time-inefficient due to covering arguments, the certification algorithm is both sample- and time-efficient, resolving a previously open question on efficient Gibbs state testing. Together, these results establish optimal or near-optimal complexity bounds for characterizing local quantum systems in both dynamical and thermal regimes.

We study the problem of learning Hamiltonians H that are s-sparse in the Pauli basis, given access to their time-evolution operators. Although Hamiltonian learning has been extensively investigated, two issues recur in much of the existing literature: the absence of lower bounds establishing optimality and the use of mathematically convenient but physically opaque error measures. We address both challenges by introducing two physically motivated notions of distance between Hamiltonians and designing a nearly optimal algorithm with respect to one of these metrics. The first, the time-constrained distance, quantifies distinguishability through dynamical evolution up to a bounded time. The second, the temperature-constrained distance, captures distinguishability through thermal states at bounded inverse temperatures. We show that s-sparse Hamiltonians with bounded operator norm can be learned under both distances using only $O(s log(1/ε))$ experiments and $O(s^2/ε)$ total evolution time. For the time-constrained distance, we further establish lower bounds of $Ω((s/n) log(1/ε) + s)$ experiments and $Ω(√s/ε)$ total evolution time, demonstrating near-optimality in the number of experiments. As an intermediate result, we obtain an algorithm that learns every Pauli coefficient of s-sparse Hamiltonians up to error ε in $O(s log(1/ε))$ experiments and $O(s/ε)$ total evolution time, improving upon several recent results. The source of this improvement is a new isolation technique, inspired by the Valiant-Vazirani theorem (STOC’85), which shows that NP is as easy as detecting unique solutions. This isolation technique allows us to query the time evolution of a single Pauli coefficient of a sparse Hamiltonian—even when the Pauli support of the Hamiltonian is unknown—ultimately enabling us to recover the Pauli support itself.

We consider the problem of learning low-degree quantum objects up to ε-error in l_2-distance. We show the following results: (I) unknown n-qubit degree-d (in the Pauli basis) quantum channels and unitaries can be learned using O(1/ε^d) queries (which is independent of n), (II) polynomials p:-1,1^n -> [-1,1] arising from d-query quantum algorithms can be learned from O((1/ε)^d log n) many random examples (x,p(x)) (which implies learnability even for d=O(log n)), and (III) degree-d polynomials p:-1,1^n -> [-1,1] can be learned through O(1/ε^d) queries to a quantum unitary Up that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded polynomials.

We give a new presentation of the main result of Arunachalam, Briët and Palazuelos (SICOMP'19) and show that quantum query algorithms are characterized by a new class of polynomials which we call Fourier completely bounded polynomials. We conjecture that all such polynomials have an influential variable. This conjecture is weaker than the famous Aaronson-Ambainis (AA) conjecture (Theory of Computing'14), but has the same implications for classical simulation of quantum query algorithms.
We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials.
This implies that if the output of d-query quantum algorithm is a homogeneous polynomial p of degree 2d, then it has a variable with influence at least Var[p]^2.
In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.