4 papers
Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
Lorenzo Ciardo, Gideo Joubert, Antoine Mottet
We introduce the concept of quantum polymorphisms to the complexity theory of quantum constraint satisfaction. Via this notion, we build an algebraic framework of reductions betwee…
New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami +2
In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023 / Discrete Analysis 2025), and obtain…
On the Quantum Chromatic Gap
Lorenzo Ciardo
The largest known gap between quantum and classical chromatic number of graphs, obtained via quantum protocols for colouring Hadamard graphs based on the Deutsch--Jozsa algorithm a…
Classical Simulation of Quantum CSP Strategies
Demian Banakh, Lorenzo Ciardo, Marcin Kozik +1
We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra…