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(k2+klog(1/ε))) queries suffice. Our proofs are simple, concise and based on Pauli-analytic techniques.
We solve an open problem in entanglement theory posed by Yu et al., {\it Nature Communications 12, 1012 (2021)}. The problem is to show, via an entanglement witness, that the
14-qubit state
ΦE8 is entangled. Inspired by a method from quantum codes, we combine symmetric extension with moment matrices to prove that
ΦE8 is entangled. The proof has the form of a rational infeasibility certificate for a semidefinite program, yielding an explicit entanglement witness. Our approach unifies and extends several earlier methods that involve the Lovász theta number of the Pauli anti-commutativity graph, promising scalability and flexibility in further applications.