Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 67 / 3 / c / Solution

The local Hamiltonian problem is a promise problem specified by a sum $H={\sum }_{j=1}^M{h}_j$ on $n$ qubits, where $M$ is polynomial in $n$, each Hermitian term acts on at most a fixed number $k$ of qubits, and the terms and two thresholds $a<b$ are described with polynomially many bits. The promise gap satisfies $b-a\ge 1/\mathrm{poly}(n)$. In a convenient normalization, $0\le h_j\le I$. The task is to distinguishThere is no required answer when the minimum energy lies between the thresholds. A formulation with Hermitian terms of polynomially bounded norm is equivalent: shift each term by a known scalar lower bound and rescale all terms by a polynomial bound to obtain positive semidefinite terms of norm at most one, while shifting and rescaling $a,b$ in parallel. The promise gap remains inverse-polynomial.