On efficiently solvable cases of quantum \(k\)-SAT (Q2223725)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On efficiently solvable cases of quantum \(k\)-SAT |
scientific article |
Statements
On efficiently solvable cases of quantum \(k\)-SAT (English)
0 references
1 February 2021
0 references
The authors address the question of special cases of k-QSAT which can be solved efficiently on a classical computer. Here, k-QSAT is the question of whether a given local Hamiltonian is frustration free. There are three main results obtained by the authors. First, they show how to efficiently solve k-QSAT with sufficiently bounded occurrence of variables. Second, they provide a general framework for parameterized algorithms for k-QSAT. Finally, the authors conduct a graph theoretic study of 3-QSAT interaction graphs which have a dimer covering. New tools to study QSAT are obtained throughout the article, including graph theoretic concepts.
0 references
quantum k-SAT
0 references
dimer covering
0 references
transfer filtrations
0 references