4 papers · 1 filter
Mermin-Peres magic rectangles modulo odd primes
Josse van Dobben de Bruyn, Remy van Dobben de Bruyn, Peter Zeman
The Mermin-Peres magic square provides a simple example of a system of linear equations over which has no classical solutions but does have a finite-dimens…
Quantum polymorphism characterisation of commutativity gadgets in all quantum models
Eric Culf, Josse van Dobben de Bruyn, Peter Zeman
Commutativity gadgets provide a technique for lifting classical reductions between constraint satisfaction problems to quantum-sound reductions between the corresponding nonlocal g…
Existence and nonexistence of commutativity gadgets for entangled CSPs
Eric Culf, Josse van Dobben de Bruyn, Matthijs Vernooij +1
Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the corresponding entangled CSP…
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Prem Nigam Kar, David E. Roberson, Tim Seppelt +1
Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. Atserias et al. [JC…