IQIM Postdoctoral and Graduate Student Seminar

Abstract: There are believed to be fundamental limits on how accurately we can solve computationally hard optimization problems in polynomial time. Such limits apply to finding the ground state energy of a classical Ising antiferromagnet on an arbitrary graph. In recent years, this notion of "hardness of approximation" has been extended to strongly interacting quantum systems, such as spin-1/2 Heisenberg antiferromagnets on arbitrary graphs. We summarize these developments and present a family of computationally hard quantum optimization problems that interpolates between the quantum and classical extremes.