 |
Center for Nonlinear Studies |
The Heisenberg model plays a central role in understanding quantum materials, realizing numerous quantum phases as ground states. However, the task of obtaining the ground state of a given Heisenberg-type Hamiltonian is in general very hard. While quantum Monte Carlo methods and tensor network type methods can be extremely powerful in many cases, they are not a single panacea for the problem; as a matter of fact, the ground state problem of the Heisenberg models is known to be QMA-complete (quantum analogue of NP-complete).
Here, we focus on the fact that for the (antiferromagnetic) Ising model, computational complexity theory provides strong evidence for the Goemans-Williamson algorithm, a semidefinite programming (SDP) based approach, to be *optimal* in the approximation ratio sense. As the Heisenberg model could be regarded as a natural quantum extension of the Ising model, we can ask the question "what would be the similarly optimal algorithm for the Heisenberg model?". This problem has triggered a number of recent research in the quantum computation community known as the "quantum Max Cut problem". Focusing on the SU(2) symmetry and its algebraic structure, we construct an SDP algorithm that is both theoretically most natural and practically implementable for the first time. We prove that it could be regarded as a first-order of a systematically improving sequence of approximations (properly converging Lasserre/NPA-hierarchy in the mathematics language), as well as exactness and inexactness for some natural families of Heisenberg models.
In the talk I will start from the classical Goemans-Williamson result and motivate our approach before introducing the algorithm. I will also show its potential use for understanding ground states of actual condensed matter stems as well as how it connects to "frustration-free" models known in the context of exact solvability, as well as sum-of-squares proof systems. If we have time, I would also like to discuss its connection to other approaches for solving the Heisenberg ground state problem and its computational complexity.
Bio: After getting a PhD at University of Tokyo, Jun Takahashi studied numerical condensed matter physics under the supervision of Prof. Anders Sandvik, and is currently a postdoc at University of New Mexico. He works on computational complexity aspects of condensed matter physics.
Host: Samuel Slezak (CCS-3)