Understanding the Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization

The viability of non-stoquastic catalyst Hamiltonians to deliver consistent quantum speedups in quantum adiabatic optimization remains an open question. Several studies (Crosson et al. (2014), Hormozi et al. (2017)) on random Ising problems have shown that stoquastic catalysts typically outperform non-stoquastic ones. A stark counterexample to this is the exponential speedup of non-stoquastic catalysts over stoquastic ones for infinite-range ferromagnetic p-spin models with p > 3 (Seki & Nishimori (2012)). We provide details on how the non-stoquastic catalyst provides an advantage in these models. We use this insight to then construct a geometrically local 2-body example that exhibits a similar exponential advantage for a non-stoquastic catalyst over a stoquastic one, up to the maximum system size we are able to study.