On efficiently solvable cases of quantum \(k\)-SAT

DOI10.1007/s00220-020-03843-9zbMath1462.81085OpenAlexW3114592709MaRDI 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

zbMATH Keywords

dimer coveringquantum k-SATtransfer filtrations

Mathematics Subject Classification ID

Quantum computation (81P68) General topics in linear spectral theory for PDEs (35P05) 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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum gates (81P65)

Related Items (1)

2-step nilpotent \(L_{\infty}\)-algebras and hypergraphs

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

This page was built for publication: On efficiently solvable cases of quantum \(k\)-SAT