Kieran Mastel, University of Waterloo
The weighted algebra approach to constraint system games
Entanglement allows for correlations between spatially separated experiments that are not possible classically. One way to study the computational power of entanglement is via nonlocal games. I will discuss my recent works with Eric Culf and William Slofstra on constraint system games. Different types of perfect entangled strategies for these games can be understood as representations of the algebra of the underlying constraint system. The weighted algebra formalism, introduced by Slofstra and me, extends this to non-perfect strategies. Using this formalism we can show that classical reductions between constraint systems are sound against quantum provers, which allows us to prove the RE-completeness of some constraint system games and to show that MIP* admits two prover perfect zero knowledge proofs.
MC 5417