Strong Duality between Frustration-Freeness and Semidefinite Programming for Heisenberg Ground States

Jun Takahashi^2,1*, Chaithanya Rayudu², Cunlu Zhou², Robbie King³, Kevin Thompson⁴, Ojas Parekh⁴

¹Institute for Solid State Physics, University of Tokyo, Tokyo, Japan
²Center for Quantum Information and Control, University of New Mexico, Albuquerque, NM, USA
³Computing and Mathematical Sciences, Caltech, Pasadena, CA, USA
⁴Sandia National Labs, Albuquerque, NM, USA

* Presenter:Jun Takahashi, email:5sqrs.17.126.57@gmail.com

A Hamiltonian $H=\sum H_i$ is called to be frustration-free (FF) if the ground state of $H$ gives the lowest eigenvalues for all $H_i$ simultaneously [1]. This FF property in Hamiltonians has played a tremendous role in theoretical physics to deepen our understanding of physical phenomena; the AKLT model for understanding SPT phases and the Haldane conjecture, the toric-code for topological orders, and the Majumdar-Ghosh model for valence-bond solids, to name just a few. Note that the definition of FF depends on the particular way of dividing the Hamiltonian, and in general, given an arbitrary Hamiltonian it is highly nontrivial to decide whether the Hamiltonian admits some decomposition that makes it FF.
In this talk, I will show that the algorithm we developed [2] actually is a dual to an efficient algorithm for finding such FF decomposition with some locality constraints. The algorithm originated from computational complexity considerations for approximating the ground state of Heisenberg-type Hamiltonians, which is a QMA-hard (quantum version of NP) computational task. The duality we exploit here is one that is established in the field of convex optimization, and is called Sum-of-Squares in that context. I will also go through the approximation algorithm to demonstrate its ability, and argue that it is the natural quantum analogue to the classical Goemans-Williamson algorithm [3].

[1] H. Watanabe, H. Katsura, and J-Y. Lee, Phys. Rev. Lett. 133, 176001 (2024)
[2] J. Takahashi, C. Rayudu, C. Zhou, R. King, K. Thompson, and O. Parekh, arxiv:2307.15688
[3] M. Goemans and D. Williamson, Journal of the ACM (JACM) 42. 6, 1115 (1995)

Keywords: Heisenberg model, Frustration-free, Semidefinite Programming, Computational Complexity, Ground State