How does quantum pseudo-telepathy work, as a quantum circuit?

[Strilanc]

I'm trying to understand the wikipedia article on quantum pseudotelepathy. I've been trying to figure out the quantum circuits the players can use to win the game from the wiki article.

(Level of knowledge: Everything I know about quantum physics is from the computer science side. I can explain how Grover's algorithm works and understand quantum logic circuits, but I have no idea how those map to the underlying physics or what an observable is or how eigen values relate to observables or how wavefunctions come into things or etc.)

My main stumbling point is what the heck is going on in the center column and row. For example, here's my current terrible guess at a circuit (using this online simulator) for the center column:

In the above circuit q1 is understood to be entangled with an unseen q1' to be used as part of a corresponding circuit for one of the rows, and the same for q2 and q2'. The circuit is xoring together the X, Y, and Z rotations of the input qubits and using that output to determine the values to place in the cells of the column.

This circuit doesn't work. I know it doesn't work because it's never mixing anything; never taking advantage of superpositions. It could be simulated classically, and the game can't be won with certainty classically.

So... I'm lost. A link to a more introductory explanation would be great. I'm pretty sure I'm missing something related to the pauli XYZ matrices satisfying XYZ = -iI, and rotations in 3d being order-dependent, but I don't know where to apply those facts.

 

[Strilanc]

Found the answers on my own.

I found this paper really helpful: http://arxiv.org/pdf/quant-ph/0407221.pdf .

It gives that actual unitary matrices that the entangled bell states must be transformed by (i.e. the gates to apply in each case) in section 5.2. I wrote a program to go through all the possibilities and those matrices are indeed a winning strategy. No idea what they have to do with pauli matrices, though...

Here's a screenshot of the relevant content: