Continuous-Time Quantum Walks for MAX-CUT Optimization

Explore the performance of continuous-time quantum walks for solving the MAX-CUT problem in this 40-minute lecture by Dan Browne from UCL. Discover how the link between time-independent Hamiltonians and thermalisation is used to make heuristic predictions, with a focus on the impact of triangles in the underlying MAX-CUT graph. Learn about the extension of these results to time-dependent settings, including multi-stage quantum walks and Floquet systems. Gain insights into a novel approach for understanding the role of unitary dynamics in tackling combinatorial optimization problems using continuous-time quantum algorithms. This talk is part of the Simons Institute's series on Near-Term Quantum Computers, covering fault tolerance, benchmarking, quantum advantage, and quantum algorithms.