Cover Image

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Zhengyu, Bright, Curtis, Ganesh, Vijay
Format:	Preprint
Published:	2023
Subjects:	Quantum Physics Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

SAT + NAUTY: Orderly Generation of Small Kochen-Specker Sets Containing the Smallest State-independent Contextuality Set
by: Li, Zhengyu, et al.
Published: (2026)

Verified Certificates via SAT and Computer Algebra Systems for the Ramsey $R(3, 8)$ and $R(3, 9)$ Problems
by: Li, Zhengyu, et al.
Published: (2025)

AlphaMapleSAT: An MCTS-based Cube-and-Conquer SAT Solver for Hard Combinatorial Problems
by: Jha, Piyush, et al.
Published: (2024)

Triacontagonal proofs of the Bell-Kochen-Specker theorem
by: Aravind, P. K., et al.
Published: (2025)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
by: Mondada, Luca, et al.
Published: (2023)

Quantum k-SAT Related Hypergraph Problems
by: Kremer, Simon-Luca, et al.
Published: (2025)

Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras
by: Dawar, Anuj, et al.
Published: (2026)

Quantum complexity of the Kronecker coefficients
by: Bravyi, Sergey, et al.
Published: (2023)

Quantum search by continuous-time quantum walk on t-designs
by: Lugão, Pedro H. G., et al.
Published: (2023)

Learning stabilizer structure of quantum states
by: Arunachalam, Srinivasan, et al.
Published: (2025)

Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)

Improving SAT Solvers on Orthogonal Latin Square Problems
by: Barnoff, Aaron, et al.
Published: (2026)

Algorithmic Cluster Expansions for Quantum Problems
by: Mann, Ryan L., et al.
Published: (2023)

Kochen-Specker sets in four-dimensional spaces
by: Elford, Brandon, et al.
Published: (2019)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
by: Cardoso, Ricardo Rivera, et al.
Published: (2025)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
by: Han, Zicheng, et al.
Published: (2026)

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

The Tensor as an Informational Resource
by: Christandl, Matthias
Published: (2023)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
by: Panova, Greta
Published: (2025)

Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
by: Chen, Yu-Zhen Janice, et al.
Published: (2025)

Efficient Algorithms for Weakly-Interacting Quantum Spin Systems
by: Mann, Ryan L., et al.
Published: (2026)

A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
by: Schreiber, Franz J., et al.
Published: (2025)

Non-Kochen-Specker Contextuality
by: Pavicic, Mladen
Published: (2023)

The simplest Kochen-Specker set
by: Cabello, Adán
Published: (2025)

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses
by: Wu, Mingyou
Published: (2024)

On the satisfiability of random $3$-SAT formulas with $k$-wise independent clauses
by: Caragiannis, Ioannis, et al.
Published: (2024)

On Computational Aspects of Ordered Matching Problems
by: Čertík, Michal, et al.
Published: (2025)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
by: Samar, Sahil, et al.
Published: (2026)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
by: Rudolph, Dorian, et al.
Published: (2024)

On Simplest Kochen-Specker Sets
by: Pavicic, Mladen
Published: (2025)

Parameterised Holant Problems
by: Aivasiliotis, Panagiotis, et al.
Published: (2024)

SAT, Gadgets, Max2XOR, and Quantum Annealers
by: Ansótegui, Carlos, et al.
Published: (2024)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)

An algebraic characterisation of Kochen-Specker contextuality
by: Frembs, Markus
Published: (2024)

Finding Minimum Matching Cuts in $H$-free Graphs
by: Lucke, Felicia, et al.
Published: (2025)

Queen Domination by SAT Solving
by: Rostami, Taha, et al.
Published: (2025)

The Rank-Ramsey Problem and the Log-Rank Conjecture
by: Beniamini, Gal, et al.
Published: (2024)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
by: Grüne, Christoph
Published: (2022)