Quantum circuit equivalent of quantum pseudo-telepathy game

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.

-

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:

-

I found the answer and wrote up a blog post about it. I have no idea what the pauli gates have to do with anything, but I did find circuits that work.

Here's an example game run, where the referees picked bottom and left, as a quantum circuit:

And the circuits for each case:

Note that these circuits are not for the mermin-peres game, but for a variant where you try to cover the common cell with exactly one token. Rule examples:

And descriptions of the gates used in the circuit diagrams:

-

To convert an observable, like $X \otimes I$, into a circuit you:

1. Compute a set of eigenvectors.

$(X \otimes I) v= \lambda v$

$v~ \tilde\in \left\{ (+1)\begin{bmatrix}1\\1\\0\\0\end{bmatrix}, (-1)\begin{bmatrix}1\\-1\\0\\0\end{bmatrix}, (+1)\begin{bmatrix}0\\0\\1\\1\end{bmatrix}, (-1)\begin{bmatrix}0\\0\\1\\-1\end{bmatrix} \right\}$

2. Create a unitary matrix whose rows are along said eigenvectors

$U = \frac{1}{\sqrt{2}}\begin{bmatrix}1&1&0&0\\1&-1&0&0\\0&0&1&1\\0&0&1&-1\end{bmatrix}$

3. Convert that matrix into a circuit. Also, you need the inverse circuit.

M = ──H── = M^(-1)
─────

4. Apply the operation you created.

5. Arbitrarily interpret the eigenvalues as true/false.

6. Use controlled nots to toggle a fresh zero qubit if the system is in a state corresponding to one of the eigenvectors with a "true" eigenvalue.

───◦──
───┼──
│
0 ─X──

7. Finish off by applying the inverse operation.

──H──◦──H──
─────┼─────
│
0 ───X─────

8. The target qubit now contains the desired measurement, and the system hasn't been otherwise disturbed.

Repeat this procedure to get the circuits for all 9 observables (some are harder than others).

To measure multiple observables, just concatenate the circuits (but use a different fresh qubit for each circuit). You only need two of the three in this case, since the third will always be the xor of the other two.

It's possible to avoid introducing the extra qubits, but you can reach that point by applying lots of small optimizations to the circuits.

-