← Back to papers
Continuous-time quantum walks for MAX-CUT are hot
Robert J. Banks, Ehsan Haque, Farah Nazef, Fatima Fethallah, Fatima Ruqaya, H. Ahsan, Hetika D. Vora, Hibah Tahir, I. Ahmad, Isaac Hewins, I. Shah, K. Baranwal, Mannan Arora, Mateen Asad, Mubasshirah Khan, Nabian Hasan, Nuh Azad, Salgai Fedaiee, S. Majeed, Shayam Bhuyan, Tasfia Tarannum, Yahya Ali, D. Browne, P. Warburton·June 17, 2023·DOI: 10.22331/q-2024-02-13-1254
PhysicsComputer Science
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
By exploiting the link between time-independent Hamiltonians and thermalisation, heuristic predictions on the performance of continuous-time quantum walks for MAX-CUT are made. The resulting predictions depend on the number of triangles in the underlying MAX-CUT graph. We extend these results to the time-dependent setting with multi-stage quantum walks and Floquet systems. The approach followed here provides a novel way of understanding the role of unitary dynamics in tackling combinatorial optimisation problems with continuous-time quantum algorithms.