Unique Games hardness of Quantum Max-Cut, and a vector-valued Borell's inequality
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.