The Quantum Satisfiability Problem: Algorithms & Complexity-Theoretic Hardness

In theoretical computer science, the Boolean Satisfiability Problem (k-SAT) is a canonical "intractable" problem, and has attracted much attention from both algorithms and complexity theoretic perspectives. There is a quantum generalization of k-SAT, denoted the Quantum SAT problem (k-QSAT), which is physically motivated via connections to properties of low-temperature many-body quantum systems. Just as k-SAT is "hard" for classical computers, k-QSAT is "hard" for quantum computers in a complexity theoretic sense. However, much less is known about k-QSAT than about k-SAT. In this proposal, we aim to help close this knowledge gap by pursuing the following objectives:

(1) It is known that 2-QSAT can be solved efficiently on "qubits", i.e. 2-dimensional quantum systems. On higher-dimensional systems, however, 2-QSAT is known to be hard. However, the precise threshold between "easy" and "hard" is not known. Determining this threshold is Objective 1.

(2) One approach for dealing with hard problems such as k-SAT is to study "easy" or tractable special cases of the problem. In the case of k-QSAT, one seemingly "easy" class of instances are those with a so-called "System of Distinct Representatives (SDR)". Any k-QSAT instance with an SDR always has a solution - the question is, can one compute said solution efficiently? This objective aims to consider both developing efficient algorithms for computing solutions to k-QSAT instances with SDRs, and/or showing complexity theoretic hardness via complexity classes such as "Polynomial Parity Arguments on Directed graphs (PPAD)".

(3) Another well-studied approach for dealing with "hard" problems classically is the theory of parameterized algorithms. While this is a well-developed field classically, quantumly it is in its infancy. Objective 3 aims to build on the Principal Investigator's existing preliminary work on parameterized algorithms for k-QSAT to give the first full-fledged parameterized algorithm for k-QSAT.

DFG Programme Research Grants