Entangling Problem Hamiltonian for Adiabatic Quantum Computation

Adiabatic quantum computation starts from embedding a computational problem into a Hamiltonian whose ground state encodes the solution to the problem. This problem Hamiltonian is normally chosen to be diagonal in the computational basis, that is a product basis for qubits. We demonstrate that, in fact, a problem Hamiltonian can always be chosen to be non-diagonal in the computational basis. To be more precise, we show how to construct a problem Hamiltonian 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 conjecture that such entangling problem Hamiltonians might evade the many-body localization bottleneck of the adiabatic quantum computation and thus improve its performance.