The Quantum Satisfiability Problem - Algorithms and Complexity Theoretic Hardness

量子可满足性问题 - 算法和复杂性理论硬度

• 批准号: 432788384
• 负责人: Professor Dr. Sevag Gharibian, Ph.D.
• 金额: --
• 依托单位: Fachgebiet Algorithmen und Komplexität
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/432788384?language=en
• 关键词: Quantum; Satisfiability; Problem; Algorithms; Complexity

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.

在理论计算机科学中，布尔可满足性问题（k-SAT）是一个典型的“棘手”问题，从算法和复杂性理论的角度都引起了广泛的关注。k-SAT有一个量子化的推广，称为量子SAT问题（k-QSAT），它是通过与低温多体量子系统的性质的联系而产生的物理动机。正如k-SAT对于经典计算机是“困难的”，k-QSAT对于量子计算机在复杂性理论意义上是“困难的”。然而，对k-QSAT的了解远少于对k-SAT的了解。在这项提案中，我们的目标是通过追求以下目标来帮助缩小这一知识差距：（1）众所周知，2-QSAT可以在“量子比特”上有效地求解，即2维量子系统。然而，在高维系统中，2-QSAT已知是困难的。然而，“容易”和“困难”之间的确切界限尚不清楚。确定该阈值是目标1。(2)一种处理像k-SAT这样的困难问题的方法是研究问题的“简单”或易处理的特殊情况。在k-QSAT的情况下，一个看似“简单”的实例类别是具有所谓的“不同代表系统（SDR）”的实例。任何带有SDR的k-QSAT实例总是有一个解-问题是，可以有效地计算所述解吗？该目标旨在考虑开发用于计算具有SDR的k-QSAT实例的解决方案的有效算法，和/或通过复杂性类（例如“有向图上的多项式奇偶参数（PPAD）"）显示复杂性理论硬度。(3)另一个研究得很好的方法来处理“硬”问题的经典是参数化算法的理论。虽然这在经典上是一个发展良好的领域，但在量子上它仍处于起步阶段。目标3的目的是建立在主要研究者的参数化算法k-QSAT的现有初步工作，给第一个成熟的参数化算法k-QSAT。