Quantum advantage and CSP complexity

DOI10.1016/J.JCTB.2025.10.002MaRDI QIDQ6862412zbMATH OpenFDO

Authors Lorenzo Ciardo

Publication date 9 February 2026

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCTB.2025.10.002

zbMATH Keywords

constraint satisfaction problemCSPentangled strategygraph colouringgraph homomorphismminionnon-local gamepolymorphismpromise CSPquantum homomorphism

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• (2+)-Sat is NP-hard
• H-coloring dichotomy revisited
• A dichotomy theorem for nonuniform CSPs
• A multi-prover interactive proof for NEXP sound against entangled provers
• A proof of the CSP dichotomy conjecture
• Algebraic Approach to Promise Constraint Satisfaction
• Approximate Graph Colouring and Crystals
• Approximate graph colouring and the hollow shadow
• Arc consistency and friends
• Characterization of binary constraint system games
• CLAP: A New Algorithm for Promise CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
• Entangled games are hard to approximate
• Estimating quantum chromatic numbers
• Galois theory for minors of finite functions
• Generalized satisfiability problems via operator assignments
• Hierarchies of Minion Tests for PCSPs through Tensors
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
• Local consistency as a reduction between constraint satisfaction problems
• Minimum entangled state dimension required for pseudo-telepathy
• Minimum quantum resources for strong non-locality
• MIP* = RE
• NEEXP is contained in MIP
• New hardness results for graph and hypergraph colorings
• New Separations in Zero-Error Channel Capacity Through Projective Kochen–Specker Sets and Quantum Coloring
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• On the power of unique 2-prover 1-round games
• On the quantum chromatic number of a graph
• Promise constraint satisfaction and width
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Proof Complexity Meets Algebra
• Quantum advantage and CSP complexity
• Quantum homomorphisms
• Quantum mechanics in Hilbert space
• Quantum pseudo-telepathy
• Reducibility among combinatorial problems
• Robustly solvable constraint satisfaction problems
• SDPs and robust satisfiability of promise CSP
• Solving CSPs using weak local consistency
• Spectral lower bounds for the quantum chromatic number of a graph
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Complexity of Near-Optimal Graph Coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• The quantum monad on relational structures
• The wonderland of reflections
• Theoretical analysis of singleton arc consistency and its extensions
• Topology and Adjunction in Promise Constraint Satisfaction

This page was built for publication: Quantum advantage and CSP complexity

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