4 papers · 1 filter
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…
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…