"Local Hamiltonians and Quantum Cuts", Alexandra Kolla, University of California, Santa Cruz

Local Hamiltonians and Quantum Cuts
Abstract: 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.
Bio: I am a professor at University of California, Santa Cruz. My research focuses on Theoretical Computer Science, and more specifically, spectral graph theory, statistical physics, and quantum computing. I received my PhD from UC Berkeley, and have held faculty positions at UIUC and CU Boulder, prior to joining UC Santa Cruz.