AF: Small: Exact algorithms for the quantum satisfiability problem

Virginia Commonwealth University, Richmond VA

Investigators

Abstract

Among the most fundamental problems in theoretical computer science is the k-SATISFIABILITY problem (k-SAT), which roughly asks: Given a set of Boolean constraints of a special form, each acting on k out of n bits, does there exist an assignment to all n bits which simultaneously satisfies every constraint? This problem has far-reaching applications in areas ranging from artificial intelligence to electronic design automation to theorem proving, thus underscoring its significance. More recently, a quantum generalization of k-SAT has arisen, known as k-QSAT, which finds applications in areas such as quantum error-correcting codes. Moreover, k-QSAT is physically well-motivated, as it can be thought of as modeling how quantum systems in nature are governed by local quantum constraints. Unlike k-SAT, however, much less is known about k-QSAT. The aim of this project is precisely to close this fundamental knowledge gap. In particular, this project broadly asks: In what cases can non-trivial algorithms be developed for solving k-QSAT? The resolution of this question will yield deep insights into which properties of quantum systems can be computed efficiently by a classical computer. Moreover, the results obtained will be disseminated through a variety of avenues, including conferences, new course materials, and high school workshops aimed at exposing young computer scientists to the frontiers of research.