On efficiently solvable cases of quantum k-SAT
General topics in linear spectral theory for PDEs (35P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum gates (81P65) Quantum computation (81P68) Selfadjoint operator theory in quantum theory, including spectral analysis (81Q10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)
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.
- A quantum Lovász local lemma
- Algorithms for propositional model counting
- An efficient algorithm for Helly property recognition in a linear hypergraph
- Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
- Bounds on the number of edges in hypertrees
- Complexity of Finding Embeddings in a k-Tree
- Computational Complexity of Projected Entangled Pair States
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Efficient algorithm for a quantum analogue of 2-SAT
- Extremal combinatorics. With applications in computer science
- scientific article; zbMATH DE number 3900787 (Why is no real title available?)
- scientific article; zbMATH DE number 4096783 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1175369 (Why is no real title available?)
- scientific article; zbMATH DE number 1776257 (Why is no real title available?)
- scientific article; zbMATH DE number 6789292 (Why is no real title available?)
- Intersection graphs of k-uniform linear hypergraphs
- Linear time algorithm for quantum 2SAT
- Maximal Flow Through a Network
- Model counting for CNF formulas of bounded modular treewidth
- On satisfiability problems with a linear structure
- Quantum Hamiltonian Complexity
- Quantum Lovász local lemma: Shearer's bound is tight
- Quasi-gcd computations
- Random quantum satisfiability
- Simulating Quantum Computation by Contracting Tensor Networks
- Solving #SAT and MAXSAT by Dynamic Programming
- Tensor network contractions. Methods and applications to quantum many-body systems
- The Complexity of Decision Versus Search
- Theory and Applications of Satisfiability Testing
- When a local Hamiltonian must be frustration-free
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- scientific article; zbMATH DE number 1583866 (Why is no real title available?)
- Difficult instances of the counting problem for 2-quantum-SAT are very atypical
- Linear time algorithm for quantum 2SAT
- On efficiently solvable cases of quantum k-SAT
- When a local Hamiltonian must be frustration-free
- 2-step nilpotent \(L_{\infty}\)-algebras and hypergraphs
- Testing quantum satisfiability
- Three ``quantum algorithms to solve 3-SAT
This page was built for publication: On efficiently solvable cases of quantum \(k\)-SAT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223725)
