Continuous-time quantum walks for MAX-CUT are hot

Continuous-time quantum walks are a proposed approach for tackling combinatorial optimisation problems with near-term quantum devices. This approach relies on being able to find good values for the hopping parameter to maximise the performance of the algorithm. In this presentation we focus on tackling MAX-CUT on random graphs with continuous-time quantum walks. By exploiting our understanding of thermalisation, near-optimal values of the hopping parameter can be found, for otherwise intractable problems. We find that the choice of hopping parameter depends on the number of triangles in the underlying MAX-CUT graph. The associated preprint for this presentation can be found at arXiv:2306.10365.