Simple algorithms to test and learn local Hamiltonians
<|reference_start|>Simple algorithms to test and learn local Hamiltonians: 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 $\epsilon_1$-close to $k$-local or $\epsilon_2$-far from $k$-local, we show that $O(1/(\epsilon_2-\epsilon_1)^{8})$ queries suffice. This solves two questions posed in a recent work by Bluhm, Caro and Oufkir. For learning up to error $\epsilon$, we show that $\exp(O(k^2+k\log(1/\epsilon)))$ queries suffice. Our proofs are simple, concise and based on Pauli-analytic techniques.<|reference_end|>
@article{gutiérrez2024simple,
    title={Simple algorithms to test and learn local Hamiltonians},
    author={Francisco Escudero Guti'errez},
    journal={arXiv preprint arXiv:2404.06282},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.06282},
    primaryClass={quant-ph cs.CC cs.DS cs.IT cs.LG math.IT}
}