Ojas Parekh, Sandia National Laboratories
Quantum Max Cut (QMC) is a QMA-hard instance of 2-Local Hamiltonian (2-LH) that is closely related to the well-studied antiferromagnetic Heisenberg model (AFHM). Finding maximal energy states of QMC is equivalent to finding ground states of AFHM; however, the approximability of the former is related to the classical Max Cut problem. We will explore this connection and explain why QMC has emerged as a testbed for approximating 2-LH in much the same vein that Max Cut is a canonical constraint-satisfaction problem that has driven development of classical approximation algorithms based on semidefinite programming hierarchies. We will discuss several recent results including an optimal product-state approximation for QMC and prospects for unique-games hardness.
Add event to calendar
