Simple algorithms to test and learn local Hamiltonians
This solves specific open questions in quantum Hamiltonian analysis, but is incremental in advancing algorithmic techniques for quantum systems.
The paper tackles the problems of testing and learning local Hamiltonians from queries, showing that O(1/(ε2-ε1)^8) queries suffice for testing and exp(O(k^2 + k log(1/ε))) queries for learning up to error ε.
We consider the problems of testing and learning an $n$-qubit $k$-local Hamiltonian from queries to its evolution operator with respect the 2-norm of the Pauli spectrum, or equivalently, the normalized Frobenius norm. For testing whether a Hamiltonian is $ε_1$-close to $k$-local or $ε_2$-far from $k$-local, we show that $O(1/(ε_2-ε_1)^{8})$ queries suffice. This solves two questions posed in a recent work by Bluhm, Caro and Oufkir. For learning up to error $ε$, we show that $\exp(O(k^2+k\log(1/ε)))$ queries suffice. Our proofs are simple, concise and based on Pauli-analytic techniques.