Codes and Expansions (CodEx) Seminar

Alexandra Kolla (UC Santa Cruz):
Quantum Max Cuts and Local Hamiltonians

In this talk, we will discuss the quantum Heisenberg model and its generalizations. The quantum Heisenberg model is a family of spin glass Hamiltonians defined by nearest-neighbor interactions. This model, especially the antiferromagnetic variant, is well-studied in condensed matter physics and has recently gained attention in computer science since it can be seen as a quantum generalization of the Max-Cut problem. We will mostly focus on a generalization of the quantum Heisenberg model, known as Quantum Max-d-Cut, that deals with interactions of spins with local Hilbert space of dimension d. Similarly to Quantum Max-Cut, Quantum Max-d-Cut can be seen as the quantum generalization of Max-d-Cut. Additionally, this model is known to be universal and QMA-hard to optimize. There has been a large body of literature recently that focuses on finding classical approximation algo-rithms for Quantum Max-Cut while not much is known for Quantum Max-d-Cut. In this talk, we will discuss a systematic study of Quantum Max d-Cut, as well as preliminary algorithmic results for approximating the ground state of the corresponding Hamiltonian.