On Constructing Driver Hamiltonians for Several Linear Constraints

Recent advances in adiabatic quantum computing and quantum annealers has centered around using more advance and novel Hamiltonians to solve optimization problems. One of these advances has centered around the development of driver Hamiltonians that commute with the constraints of an optimization problem. This approach has been shown to be able to use sparser connectivity to embed several practical problems on quantum devices in comparison to other methods. Designing the driver Hamiltonians that successfully commute with several constraints has largely been based on strong intuition for specific problems and with no general algorithm for arbitrary constraints. In this work, we develop an algebraic framework for reasoning about the commutation of Hamiltonians with linear constraints - one that allows us to classify the complexity of finding a driver Hamiltonian for a set of constraints as NP-Hard through a reduction to the Subset Equal Sums problem as well as design a simple algorithm to solve the problem for Hamiltonians with bounded number of higher body interaction terms.