Approximating the operator norm of local Hamiltonians via few quantum states

Consider a Hermitian operator $A$ acting on a complex Hilbert space of dimension $2^n$. We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian, its operator norm can be approximated independently of $n$ by maximizing $\mathrm{\mid }⟨\psi \mathrm{\mid }A\mathrm{\mid }\psi ⟩\mathrm{\mid }$ over a small collection ${\mathbf{X}}_n$ of product states $\mathrm{\mid }\psi ⟩\in ({\mathbf{C}}^2{)}^{\otimes n}$. More precisely, we show that whenever $A$ is $d$-local, $\mathit{\text{i.e.,}}$ $\mathrm{°}(A)\le d$, we have the following discretization-type inequality: $$\mathrm{\parallel }A\mathrm{\parallel }\le C(d)\underset{\psi \in {\mathbf{X}}_n}{\max }\mathrm{\mid }⟨\psi \mathrm{\mid }A\mathrm{\mid }\psi ⟩\mathrm{\mid }\mathrm{.}$$ The constant $C(d)$ depends only on $d$. This collection ${\mathbf{X}}_n$ of $\psi$’s, termed a \emph{quantum norm design}, is independent of $A$, and consists of product states, and can have cardinality as small as $(1+\text{eps}{)}^n$, which is essentially tight. Previously, norm designs were known only for homogeneous $d$-localHamiltonians $A$ \cite{L,BGKT,ACKK}, and for non-homogeneous $2$-local traceless $A$ \cite{BGKT}. Several other results, such as boundedness of Rademacher projections for all levels and estimates of operator norms of random Hamiltonians, are also given.