This article contains some very interesting observations about what generically makes certain optimization problem instances hard for AQC, and what can be done about this. Here is the abstract:
First order quantum phase transition is believed to create a gap in adiabatic quantum computation that is exponentially dependent on system parameters. Here, we investigate first order quantum phase transition by relating it to the properties of the local minima in the problem Hamiltonian. We use perturbation theory to predict the position and the size of the minimum spectral gap and show agreement with numerical calculations for an example of weighted maximum independent set problem. By tuning the parameters of the studied example, we demonstrate a controllable variation of the minimum gap size by several orders of magnitude.