6 papers
Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism
Lorenzo Ciardo, Iris Hebbeker, Gideo Joubert +2
We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include Kneser graphs, $…
Linear equations mod are pseudo-telepathic
Lorenzo Ciardo
We prove that the quantum monad in dimension admits no natural transformation to the polymorphism clone of linear equations modulo . Consequently, for every , ther…
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…
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…
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…