Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Home 
 People 
 Current 
 Postdocs 
 Visitors 
 Students 
 Research 
 Publications 
 Conferences 
 Workshops 
 Sponsorship 
 Talks 
 Seminars 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 P/T Colloquia 
 Archive 
 Ulam Scholar 
 
 Postdoc Nominations 
 Students 
 Student Program 
 Visitors 
 Description 
 Past Visitors 
 Services 
 General 
 
 History of CNLS 
 
 Maps, Directions 
 CNLS Office 
 T-Division 
 LANL 
 
Thursday, February 22, 2024
12:30 PM - 1:30 PM
T-4 Conference Room (TA03, Building 524, Room 105)

Quantum Lunch

Correction- Title - Probing ground states of Heisenberg models with semi-definite programming (SDP) relaxations

Jun Takahashi
University of New Mexico

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)