The Quantum Satisfiability Problem - Algorithms and Complexity Theoretic Hardness

在理论计算机科学中，布尔可满足性问题(k-SAT)是一个典型的“难解”问题，从算法和复杂性理论的角度都引起了人们的广泛关注。K-SAT有一个量子推广，称为量子SAT问题(k-QSAT)，它是通过与低温多体量子系统的性质的联系而被物理激发的。正如k-SAT对经典计算机来说是“难的”一样，k-QSAT在复杂性理论意义上对量子计算机来说也是“难的”。然而，与k-SAT相比，人们对k-QSAT的了解要少得多。在这个提议中，我们旨在通过追求以下目标来帮助弥合这一知识鸿沟：(1)众所周知，2-QSAT可以在“量子比特”上有效地求解，即二维量子系统。然而，在更高维度的系统中，众所周知，2-QSAT是困难的。然而，“容易”和“难”之间的确切门槛尚不清楚。确定这一阈值是目标1。(2)处理诸如k-SAT之类的困难问题的一种方法是研究该问题的“容易”或易于处理的特殊情况。就k-QSAT而言，一类看似“容易”的实例是具有所谓“不同代表制(SDR)”的实例。任何有SDR的k-QSAT实例都有一个解--问题是，一个人能高效地计算出所说的解吗？这个目标旨在考虑开发高效的算法来计算具有SDR的k-QSAT实例的解，和/或通过复杂性类(例如，有向图上的多项式奇偶参数(PPAD))来展示复杂性理论的难度。(3)经典地处理“难”问题的另一种经过充分研究的方法是参数算法理论。虽然这是一个典型的发展良好的领域，但从数量上讲，它还处于初级阶段。目标3的目的是在首席研究人员已有的k-QSAT参数化算法的基础上，给出第一个成熟的k-QSAT的参数化算法。

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.