Random quantum satisfiability

MaRDI QIDQ3400468zbMATH OpenFDO

Authors

Publication date 5 February 2010

zbMATH Keywords

average case complexitydisordered quantum satisfiabilityQSATSAT

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Recommendations

• Difficult instances of the counting problem for 2-quantum-SAT are very atypical
• Quantum 3-SAT Is QMA₁-complete
• Exact location of the phase transition for random (1,2)-QSAT
• New Results on the Phase Transition for Random Quantified Boolean Formulas
• Classical and quantum satisfiability

Cited in

(16)

• Resonant transition-based quantum computation
• On efficiently solvable cases of quantum \(k\)-SAT
• Matched instances of quantum satisfiability (QSat) -- product state solutions of restrictions
• Quantum 3-SAT Is QMA₁-complete
• A quantum Lovász local lemma
• Difficult instances of the counting problem for 2-quantum-SAT are very atypical
• On the quantum spin glass transition on the Bethe lattice
• New Results on the Phase Transition for Random Quantified Boolean Formulas
• On efficiently solvable cases of quantum k-SAT
• Exact location of the phase transition for random (1,2)-QSAT
• Gapped and gapless phases of frustration-free spin-\(\frac{1}{2}\) chains
• A quantum Lovász local lemma
• Classical and quantum satisfiability
• 2-step nilpotent \(L_{\infty}\)-algebras and hypergraphs
• Testing quantum satisfiability
• The quantum setting with randomized queries for continuous problems

This page was built for publication: Random quantum satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3400468)