AF: Small: Approximation algorithms for quantum mechanical problems

Virginia Commonwealth University, Richmond VA

Investigators

Abstract

A fundamental problem in computer science is the constraint satisfaction problem MAX-SAT, which asks: Given a set of Boolean constraints on n bits, what is the maximum number of constraints which can be simultaneously satisfied by an assignment to all the bits? Despite its many applications, MAX-SAT is unfortunately believed to be impossible to solve efficiently. Fortunately, such problems can often be solved approximately via so-called approximation algorithms. In the quantum setting, a physically motivated generalization of MAX-SAT exists, known as LH, which concerns the computation of important properties of quantum systems at very low temperatures. Unfortunately, like MAX-SAT, LH is also believed intractable. This project hence asks the question: Can we compute approximate solutions to k-LH via the framework of approximation algorithms? The resolution of this question will yield deep insight into our ability to approximately compute properties of quantum systems in nature. The results obtained will be disseminated through a variety of avenues, including conferences, high school workshops, and engineering public lecture series aimed at exposing the general public to the frontiers of research. At a high level, this project aims to design polynomial-time approximation algorithms for a variety of classes of the local Hamiltonian problem (LH), from physically motivated special cases to more general settings. The techniques used are inspired primarily by ideas from the fields of approximation algorithms and quantum information theory. Among other results, a key aim of the project is to obtain insight into how well classically efficiently representable quantum states can approximate solutions to genuinely quantum problems involving ground spaces of local Hamiltonians.