On efficiently solvable cases of quantum \(k\)-SAT
From MaRDI portal
Publication:2223725
DOI10.1007/s00220-020-03843-9zbMath1462.81085MaRDI QIDQ2223725
Marco Aldi, Seyran Saeedi, Sevag Gharibian, Niel de Beaudrap
Publication date: 1 February 2021
Published in: Communications in Mathematical Physics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00220-020-03843-9
81P68: Quantum computation
35P05: General topics in linear spectral theory for PDEs
81Q10: Selfadjoint operator theory in quantum theory, including spectral analysis
82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
81P65: Quantum gates
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounds on the number of edges in hypertrees
- Model counting for CNF formulas of bounded modular treewidth
- Quasi-gcd computations
- Intersection graphs of k-uniform linear hypergraphs
- Algorithms for propositional model counting
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Extremal Combinatorics
- Computational Complexity of Projected Entangled Pair States
- Solving #SAT and MAXSAT by Dynamic Programming
- Maximal Flow Through a Network
- Quantum Hamiltonian Complexity
- Simulating Quantum Computation by Contracting Tensor Networks
- Complexity of Finding Embeddings in a k-Tree
- The Complexity of Decision Versus Search
- Linear Time Algorithm for Quantum 2SAT
- On Satisfiability Problems with a Linear Structure
- Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
- An Efficient Algorithm for Helly Property Recognition in a Linear Hypergraph
- Tensor Network Contractions
- Quantum Lovász local lemma: Shearer’s bound is tight
- Theory and Applications of Satisfiability Testing
- A quantum Lovász local lemma
