John Wright, University of Texas at Austin
The local Hamiltonian problem is one of the most fundamental problems in quantum computing. It is a natural generalization of classical constraint satisfaction problems to the quantum regime, and it is the canonical QMA-complete problem. In addition, it arises naturally in the study of many-body physics. Given an instance of the local Hamiltonian problem, the object is to find its ground state or the energy of this state. As this is a QMA-complete problem, one can also study approximation versions of this problem, in which one is trying to find a state whose energy is as close to the ground state energy as possible.
In this talk, we will discuss a special case of the local Hamiltonian problem known as Quantum Max-Cut, which has been suggested as a useful testbed for developing algorithms. Quantum Max-Cut is a quantum analogue of the Max-Cut problem from classical approximation algorithms, and is related to the well-studied anti-ferromagnetic Heisenberg model. In recent years, researchers have developed various approximation algorithms for the Quantum Max-Cut problem, including one algorithm due to Gharibian and Pareh with an approximation ratio of 0.498 which uses the basic SDP, as well two additional algorithms which improve upon it. We will survey these algorithms in our talk.
We will then discuss our work, which shows several hardness results for Quantum Max-Cut. First, we show that the Gharibian-Parekh algorithm is the optimal algorithm using the basic SDP by exhibiting an integrality gap instance with integrality gap 0.498. This shows a stark contrast between classical and quantum Max-Cut, as the basic SDP is optimal for classical Max-Cut, but by our results it is not optimal for Quantum Max-Cut. The proof of this generalizes a well-known integrality gap instance for classical Max-Cut and involves showing a new variant of Borell's isoperimetric inequality for vector-valued functions. Next, we show that it is NP-hard to achieve approximation ratio 0.956, assuming the Unique Games Conjecture.
Based on joint work with Yeongwoo Hwang, Joe Neeman, Ojas Parekh, and Kevin Thompson.
Login information:
Event address:
https://uwaterloo.zoom.us/j/96153634310?pwd=WmFIYzRkVWJob3p3WVdSM3VwWktUUT09
Event number: 961 5363 4310
Event password: 990914
Time: Dec 13, 2021 14:30 Eastern Time (US and Canada)
Add event to calendar
