Understanding a wikipedia article on quantum coordination games

[Strilanc]

I'm trying to understand the strategy being put forward by the wikipedia article on quantum pseudo-telepathy to win the Mermin-Peres magic square game.

It's frustrating, because I do understand how pseudo-telepathy works, I just can't make heads or tails of the grid in the article:

I get that if I multiply the matrices in each cell across any row or column that I'll end up with +- identity matrix. I just don't know what that MEANS. I don't understand what the players are actually DOING that is represented by multiplying those matrices.

I look at it and all I see are questions:

- Where are the entangled qubits being fed into the system?
- If Alice gets row 1, is she computing InputSuperposition * (X tensor I) * (X tensor X) * (I tensor X) on it? What is she computing?
- How does she use the result to determine her moves?
- The X, Y, and Z Pauli matrices never mix their results, so how is this computation relying on quantum mechanics at all? It seems like I could do it all classically, which is clearly wrong because there's no classical winning strategy.
- Am I even right in assuming that the circle-with-X-inside is a tensor product, i.e. <1,2> tensor <3,4> = <3,6,4,8>?

Any help would be appreciated. I've asked in multiple places but mostly gotten silence in response.

 

[Strilanc]

The paper that the table comes from is a bit more descriptive, but I still don't get it:

I think the idea is to observe the outcomes of each entry in a row (or column). What I don't understand is how you observe Z tensor Z without preventing the system from allowing you to measure X tensor X. How does this all play out, in terms of the matrix multiplications?

I'm pretty sure this has something to with doing a partial measurement in an arbitrary basis, but the basis' that I see (e.g. the vectors in the matrix I tensor Z) are all of degree 4 meaning you get 2 bits of output and use up both qubits without being able to do the second or third measurements.

 

[Hypersphere]

I'm still trying to make sense of that matrix in the context of contextuality vs. non-contextuality, and can't really answer your questions. The Wikipedia page seems rather inpenetrable to me as well, but it links to this blog post, which still seems a bit confused about the whole issue. However, it in turn links to this review that seems more helpful. Maybe those resources will help.

 

[Strilanc]

I'm still trying to make sense of that matrix in the context of contextuality vs. non-contextuality, and can't really answer your questions. The Wikipedia page seems rather inpenetrable to me as well, but it links to this blog post, which still seems a bit confused about the whole issue. However, it in turn links to this review that seems more helpful. Maybe those resources will help.

That's actually my blog post, heh. Like I said, I understand pseudo-telepathy I just can't make heads or tails of the solution on the wiki page. That review was in fact helpful, but I've already read it before.

(I want to update the wiki page but I don't feel confident about doing it because I don't understand what it's saying right now.)

 

[Hypersphere]

That's actually my blog post, heh. Like I said, I understand pseudo-telepathy I just can't make heads or tails of the solution on the wiki page. That review was in fact helpful, but I've already read it before.

(I want to update the wiki page but I don't feel confident about doing it because I don't understand what it's saying right now.)

Haha, yeah, that's unfortunate.


Looking at your questions again, I think I can actually say something. Bear in mind though, that my answers might be influenced by my lack of knowledge of the problem at hand.

- Am I even right in assuming that the circle-with-X-inside is a tensor product, i.e. <1,2> tensor <3,4> = <3,6,4,8>?

I think so. They were certainly meant to be interpreted that way in the original Mermin paper (although he didn't consider it a game).

- If Alice gets row 1, is she computing InputSuperposition * (X tensor I) * (X tensor X) * (I tensor X) on it? What is she computing?

My guess is that she measures/computes what is the eigenvalue for the operator (X tensor I) in the InputSuperposition state for the first element, (X tensor X) for the second element of the row etc. This treatment seems to be consistent with "the paper that the table came from", specifically the second exercise. To be honest, if all they are doing is making measurements on an entangled state, I don't see why this is even considered a "game".

I think the idea is to observe the outcomes of each entry in a row (or column). What I don't understand is how you observe Z tensor Z without preventing the system from allowing you to measure X tensor X. How does this all play out, in terms of the matrix multiplications?

Well, it's straightforward to show that
$$\left[ \sigma_x^1 \sigma_x^2, \sigma_z^1 \sigma_z^2 \right] = 0$$
so the two operators actually represent compatible observables. This should also mean that if the state was an eigenstate in the spin z-basis, it should also be an eigenstate of the X tensor X operation.

I'm pretty sure this has something to with doing a partial measurement in an arbitrary basis, but the basis' that I see (e.g. the vectors in the matrix I tensor Z) are all of degree 4 meaning you get 2 bits of output and use up both qubits without being able to do the second or third measurements.

Do you mean how to do it in practice? Because I don't see any reason why we couldn't do something like
$$\hat{O}_1 |\psi \rangle = o_1 |\psi \rangle$$,
read off the eigenvalue and then keep it going through the next measurement
$$\hat{O}_2 o_1 |\psi\ \rangle = o_1 o_2 |\psi \rangle$$
but I might be missing something.

 

[Delta Kilo]

I'll try.

Initially two maximally entangled pairs of qubits are prepared, a entangled with b and c with d. Alice takes a and c and Bob gets b and d. Later on Alice is told row number to fill. She only needs to do 2 measurements, the third is redundant, is is known what is it going to be. Let's say she's got row 1. She measures $+S_x \otimes I$ (which simply means measuring the first qubit along X axis and leaving the second qubit undisturbed) and puts in into cell $M_{11}$. Then she measures measures qubit c along X axis, puts it into $M_{13}$ and finally sets $M_{12}=M_{11} M_{13}$. Row 2 is a bit more tricky. Alice would have to measure for example $-S_x \otimes S_z$ and $S_z \otimes S_x$. One way to do it would be to find a fancy unitary transformation on qubits a and c, such that $-S_x \otimes S_z → Sz \otimes I$ and $S_z \otimes S_x → I \otimes Sz$.
The required transformation is $U = \frac{1}{2} \left| \begin{array}{rrrr} 1 & 1 & 1 & -1 \\ 1 & -1 & 1 & 1 \\ 1 & 1 & -1 & 1 \\ -1 & 1 & 1 & 1 \end{array} \right|$ where the matrix is in the basis $|a_+c_+\rangle$, $|a_+c_-\rangle$, $|a_-c_+\rangle$, $|a_-c_-\rangle$ (or something that looks roughy like that, I might have lost a minus sign somewhere along the way), which can be computed with some quantum gates:

a --H--*--H--X-- a'
       |     |
c -----O-----X-- c'

Since quantum computations are reversible, measuring outputs a' and c' forces qubits a and c into one of the common eigenvectors of observables $-S_x \otimes S_z$ and $S_z \otimes S_x$ (and $S_y \otimes S_y$ since they all commute).
Now, since Bob's qubits b and d were maximally entangled with a and c, they collapse into the same state as Alice's a and c, so when Bob measures one of these values he will get exactly the same result. Even if he does not measure the value in this row at all, two other measurements will come out just right that correct result for the cell can be inferred.

 

[Strilanc]

The required transformation is $U = \frac{1}{2} \left| \begin{array}{rrrr} 1 & 1 & 1 & -1 \\ 1 & -1 & 1 & 1 \\ 1 & 1 & -1 & 1 \\ -1 & 1 & 1 & 1 \end{array} \right|$ where the matrix is in the basis $|a_+c_+\rangle$, $|a_+c_-\rangle$, $|a_-c_+\rangle$, $|a_-c_-\rangle$ (or something that looks roughy like that, I might have lost a minus sign somewhere along the way), which can be computed with some quantum gates:

a --H--*--H--X-- a'
       |     |
c -----O-----X-- c'

Do you mind if I ask how you found gates corresponding to the matrix? I can do it by brute force searching all short circuits but clearly that doesn't scale up very well.

I assume finding the operation that converts between the two operations is standard knowledge I'll just run across in the context of linear algebra.

 

[Strilanc]

...

...

Those are both useful replies. I'll be working things on paper for a bit trying to make sense of it.

To be honest, if all they are doing is making measurements on an entangled state, I don't see why this is even considered a "game".

The measurements aren't the game, they're part of a strategy to win the game. Not a fun game exactly, but a game theory game.

 

[Delta Kilo]

Do you mind if I ask how you found gates corresponding to the matrix?

By accident:) I was reading about it just recently. Apparently there is an algorithm, where you start with matrix R you want to implement and gradually convert it to triangular (which conveniently happens to be diagonal) by multiplying it with a sequence of unitary matrices (gates) $...U_3 U_2 U_1 R$. Main tool is a contolled-U gate. which allows you to do linear combinations of the last two rows. By choosing the right U one can always get a 0 into desired position. NOT and SWAP can be used to move rows around. I'm sure there are better ways of doing it though.

 

[Zafa Pi]

Perhaps this will clear things up.

A pair of photons (electrons) is prepared in the Bell state
|p⟩ = √½(|+⟩|+⟩ + |-⟩|-⟩) = (in computational basis) √½(|00⟩ + |11⟩) =
√½([1,0]⊗[1,0] + [0,1]⊗[0,1]) = √½[1,0,0,1].
One of the pair of photons is given to Alice, the other to Bob. If Alice makes a (Pauli) X or a Y or a Z measurement on her photon she will get + or - 1. If Bob selects the same measurement on his photon he will get the same value. A measurement by always yields +1.
Now another pair of photons is prepared in state |q⟩ in the same state as |p⟩, but independent of |p⟩. Again one of the pair goes to Alice the other to Bob.

Now in the game let's suppose Bob is told to select the middle column. Note that the operators X⊗X, Y⊗Y, and Z⊗Z have a common eigenvector basis of
√½[1,0,0,1] with eigenvalues +1 for X⊗X, -1 for Y⊗Y, and +1 for Z⊗Z
√½[1,0,0,-1] -1 +1 +1
√½[0,1,1,0] +1 +1 -1
√½[0,1,-1,0] -1 -1 -1

For specificity's sake let's further suppose that he measures his two photons 1st with Z⊗Z, i.e. he measures his photon from |p⟩ with the left Z and the one from |q⟩ with the right Z and he gets +1 for both. So +1 times +1 = +1 is the entry for Z⊗Z. The state thus becomes [1,0]⊗[1,0] = [1,0,0,0], which is an eigenvector of Z⊗Z with value +1. Writing this vector in the above eigenbasis gives [1,0,0,0] = ½[1,0,0,1] + ½[1,0,0,-1]. Now measuring this superposition with X⊗X gives either +1 resulting in the state √½[1,0,0,1] which when measured by Y⊗Y yields -1, or the measurement by X⊗X gives -1 resulting in the state √½[1,0,0,-1] which when measured by Y⊗Y yields +1. Hence in either case Bob gets only one -1, as required.

Now let's suppose that Alice was told to take the top row, she will get the same value for for X⊗X as did Bob and it's even easier to see she will get an even number of -1s.

BTW the wikipedia article statement that it is possible to appropriately fill the grid with "the richer algebraic structure based on spin" is false. All that this QM process does is appropriately fill the one row and one column that is requested of Alice and Bob.

 

[Strilanc]

Apparently I need to read up a lot more on how observations are done. I've always thought of them as ending up in a particular possibility, but you're using them more like extracting eigen values and clearly that is the right approach here.

... A measurement by I always yields +1.

This is a good example of how I was confused. I would never have guessed that "measuring with I" always yielded +1, because I thought it meant "apply no transformations and read the bits" when it actually means "output the eigen value of one of the eigen vectors of I" and since I just has a single 4-d eigen space with eigen value 1... you always get +1. A single possible result instead of four.

 

[Delta Kilo]

For specificity's sake let's further suppose that he measures his two photons 1st with Z⊗Z, i.e. he measures his photon from |p⟩ with the left Z and the one from |q⟩ with the right Z and he gets +1 for both. So +1 times +1 = +1 is the entry for Z⊗Z. The state thus becomes [1,0]⊗[1,0] = [1,0,0,0], which is an eigenvector of Z⊗Z with value +1.

I beg to differ. Measuring Z of p and Z of q separately is not the same as measuring Z⊗Z in one go. As you said, your recipe leaves the system in state [1,0,0,0]. On the other hand, measuring Z⊗Z once and getting +1 leaves the system in superposition of [1,0,0,0] and [0,0,0,1] which is not the same thing. Specifically,
$Z \otimes Z = \left| \begin{array}{rr}1&0\\0&-1 \end{array} \right| \otimes \left| \begin{array}{rr}1&0\\0&-1 \end{array} \right| = \left| \begin{array}{rrrr}1&0&0&0\\0&-1&0&0\\0&0&-1&0\\0&0&0&1 \end{array} \right|$
has 2 eigenvalues +1 and -1 of multiplicity 2 each, with corresponding sets of eigenvectors (|00>, |11>) and (|01>, |10>). Measuring +1 projects the state onto subspace spanned by |00> and |11>.
One way of measuring Z⊗Z is to apply CNOT and then measure I⊗Z, which means measuring just the second qubit. Easy to see that Z⊗Z → CNOT† | Z⊗Z | CNOT = I⊗Z

To really get to the bottom of the Mermin square, one should consider all 4 qubits as a whole, which means working in 16-dimension space spanned by |0000>, |0001> ... |1111>

 

[Zafa Pi]

Apparently I need to read up a lot more on how observations are done. I've always thought of them as ending up in a particular possibility, but you're using them more like extracting eigen values and clearly that is the right approach here



This is a good example of how I was confused. I would never have guessed that "measuring with I" always yielded +1, because I thought it meant "apply no transformations and read the bits" when it actually means "output the eigen value of one of the eigen vectors of I" and since I just has a single 4-d eigen space with eigen value 1... you always get +1. A single possible result instead of four.

You do end up with a particular possibility. To measure a state |ψ⟩ with a measurement operator (Hermitian) A you get a particular member of the spectrum (an eigenvalue) of A. The probability of getting a particular eigenvalue = ⟨ψ|e⟩² where e is the eigenvector associated with the eigenvalue. For example Z = the matrix "(1 0)/(0 -1)", it has eigenvectors [1,0] and [0,1] with eigenvalues +1 and -1 respectively. So if |ψ⟩ = √½[1,1] then measuring |ψ⟩ with A is like flipping a fair coin with +1 on one side and -1 on the other. You will get one of +1 or -1.

The operator I has only one eigenvalue 1, and every state (unit vector) is an eigenvector.