Improved Approximation Algorithm for Quantum Max-Cut

IQC Student Seminar Featuring - Robbie King, Caltech - ZOOM 

It is impossible to solve the local Hamiltonian problem exactly, assuming P is not equal to QMA. Instead, one can ask for approximation algorithms, which output states achieving good energy uniformly across all instances. Semi-definite programming (SDP) has achieved great success in approximation algorithms for classical constraint satisfaction. But how can we round the SDP to an entangled quantum state? Variational quantum algorithms can capture entangled quantum states. But how can we classically efficiently choose the parameters? We combine these two techniques to get an improved approximation algorithm for the quantum max-cut problem for triangle-free graphs. In addition, we give an approximation algorithm for the EPR Hamiltonian. We argue this is a natural intermediate problem which isolates some key quantum features of local Hamiltonian problems.

Seminar is taking place on ZOOM, but please feel free to come and watch the livestream alongside others in QNC 3206

Join Zoom Meeting
https://uwaterloo.zoom.us/j/99895281161?pwd=WHh3T1hkZlU2b0JZQzFNOUlPaXY4UT09
 
Meeting ID: 998 9528 1161
Passcode: 851695
 

Add event to calendar