Diagonal catalysts in quantum adiabatic optimization

We propose a protocol for quantum adiabatic optimization whereby an intermediary Hamiltonian that is diagonal in the computational basis is turned on and off during the interpolation. This "diagonal catalyst" serves to bias the energy landscape towards a given spin configuration, and we show how this can remove the first-order phase transition present in the standard protocol for the ferromagnetic p spin and the weak-strong cluster problems. The success of the protocol also makes clear how it can fail: biasing the energy landscape towards a state only helps in finding the ground state if the Hamming distance from the ground state and the energy of the biased state are correlated. We present examples where biasing towards low-energy states that are nonetheless very far in Hamming distance from the ground state can severely worsen the efficiency of the algorithm compared to the standard protocol. Our results for the diagonal catalyst protocol are analogous to results exhibited by adiabatic reverse annealing, so our conclusions should apply to that protocol as well.