Non-diagonal problem Hamiltonian for adiabatic quantum computation

Abstract

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, which is a product basis for qubits. We point out that \(H_{\rm p}\) can be chosen to be non-diagonal. 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 non-diagonal problem Hamiltonians might improve the performance of the adiabatic quantum computation.