  Adiabatic quantum computation starts from embedding a computational problem
into a Hamiltonian whose ground state encodes the solution to the problem. This
problem Hamiltonian, $H_{\rm p}$, is normally chosen to be diagonal in the
computational basis, that is a product basis for qubits. We point out that
$H_{\rm p}$ can be chosen to be non-diagonal in the computational basis. To be
more precise, we show how to construct $H_{\rm p}$ in such a way that all its
excited states are entangled with respect to the qubit tensor product
structure, while the ground state is still of the product form and encodes the
solution to the problem. We discuss how such entangling problem Hamiltonians
can improve the performance of the adiabatic quantum computation.
