Testing and learning structured quantum Hamiltonian

We consider the problems of testing and learning an $n$-qubit structured Hamiltonian $H=\sum_x \lambda_x \sigma_x$ expressed in its Pauli basis, from queries to its evolution operator $U=e^{iHt}$ with respect the normalized Frobenius norm. To this end, we prove the following results for Hamiltonians whose Pauli spectrum involves only $k$-local terms or has sparsity at most $s$: \begin{enumerate} \item \textbf{Local Hamiltonians}: We give a \emph{tolerant} testing protocol to decide if a Hamiltonian is $\eps_1$-close to $k$-local or $\eps_2$-far from $k$-local, with a query complexity of $O(1/(\eps_2-\eps_1)^{4})$, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir. For learning a $k$-local Hamiltonian up to error $\eps$, we give a protocol with query complexity $\exp(O(k^2+k\log(1/\eps)))$. Our algorithm leverages the non-commutative Bohnenblust-Hille inequality by Volberg and Zhang in order to get a complexity independent of $n$. %Our proofs are simple, concise and based on Pauli-analytic techniques. \item \textbf{Sparse Hamiltonians}: We give a protocol for testing whether a Hamiltonian is $\eps_1$-close to $s$-sparse or $\eps_2$-far from $s$-sparse, with query complexity $O(s^4/(\eps_2-\eps_1)^{12})$. For learning up to error $\eps$, we show that $\exp(s^5/\eps^{12})$ queries are sufficient. \item \textbf{Learning without quantum memory}: The results stated above have no dependence on the system size $n$, but requires $n$ qubits of quantum memory (or $n$ auxiliary qubits). %Motivated by the difficulty of accessing quantum memory in current hardware, we propose We give subroutines that require no quantum memory and allows us to reproduce all the above results with only a logarithmic in $n$, increase the query complexity. To this end, our new conceptual contribution is \emph{Pauli hashing}, which allows one to also test $s$-sparse Pauli channels using $O(s/\varepsilon^2)$ queries. \item \textbf{Lower bounds.} We also prove lower bounds for testing and learning Hamiltonians in various models which are polynomially weaker than the upper bounds above. \end{enumerate}