Implementing Quantum PseudoTelepathy
“If you can’t explain it to a computer, you don’t understand it.”
Last week, I thought I understood quantum pseudotelepathy. Then I tried to make sense of the details of the Wikipedia article, and realized I had no idea what was going on. This week, I understand well enough to explain it to a computer. Now we find out if I can explain it to humans.
The Game
Pseudotelepathy is a bit of a funny name. The idea is that you could fool a person into thinking you were a telepath by using quantum physics. You would do so, with a partner, by consistently winning a coordination game which has no classical consistentlywinning strategy.
Not all games benefit from quantum techniques (i.e. exhibit pseudotelepathy). For example, suppose two isolated players are being told random words and must say “Same” when told the same word, and “Different” otherwise. Classical players can’t consistently win that game, and players using quantum physics do no better. On the other hand, if the players just have to say the same word, they can already consistently win using only classical physics (hint: just say “cat”).
The simplest game that benefits from pseudotelepathy is known as the MerminPeres magic square game. In that game each player is assigning 0s and 1s to cells on a 3×3 board while trying to satisfy some parity constraints.
I find the MerminPeres magic square game a bit difficult to explain, so I tweaked it a bit. The resulting game is mathematically equivalent, but hopefully easier to grok. The rules are as follows:
 There’s a 3×3 grid, and two players (Alice and Bob).
 Alice and Bob each get two tokens, and are isolated from each other.
 A referee picks a row from the grid, and tells it to Alice.
 A referee picks a column from the grid, and tells it to Bob.
 Alice can either cover two cells of the indicated row with her tokens, or place no tokens.
 Bob has a similar choice: place no tokens, or cover two cells of the indicated column.
 They win if the cell common to the indicated row and column ends up covered by exactly one token.
Let’s go through a run of the game. Suppose the referee(s) pick the top row and the right column. By herself, Alice is told the row and decides not to use her tokens. By himself, Bob is told the column, decides to use his tokens, and places one in the top row (of the right column) and one in the bottom row. They then get together and compare. The top right cell is the one they have in common. Alice didn’t place a token on it, but Bob did, so there’s exactly one token in the common cell. They won!
The following diagram shows some examples of game outcomes, where the players either won, lost, or failed to follow the rules. The blue B tokens belong to Bob, and the green A tokens belong to Alice. When player chose to not use their tokens, the tokens are shown next to the board:
You can check that the diagram of outcomes makes sense, given the rules.
The above game has no consistentlywinning strategy, if you’re limited to classical physics. Basically, the problem is that the number of placed tokens must be even whereas the total number of cells is odd. As a result, Alice and Bob can’t agree on a nonoverlapping covering. They’ll end up expecting to win at most 8/9 games on average. (Exercise: Actually prove this instead of handwaving it away.)
However, if you have access to quantum mechanics, you can win 100% of the time instead of only ~88% of the time.
Telepathic Solution
The last time I talked about quantum computing, explaining Grover’s Quantum Search Algorithm, I started from low level concepts and explained upward until we reached the solution. (It might be helpful to read or even reread the Grover post first, but I’ll try to cover all the relevant concepts again here.) This time, I’m going to start by showing the solution and explaining downward.
So… here’s a diagram, which you are not expected to understand yet, which shows the components of the solution:
Allow me to break down the process that the above diagram is supposed to communicate.
The diagram shows six quantum logic circuits, one for each row and one for each column. In the case shown, the referee(s) have picked the top row and the right column, so Alice has chosen the circuit corresponding to the top row and Bob has chosen the circuit corresponding to the right column.
The inputs to the chosen circuits are preshared entangled qubits. The qubit is entangled with the qubit , and with . They are entangled such that the result of any circuit run on both and or on both and will agree on the result. (Of course, the “magic” requires running different circuits, manipulating that relationship.)
After Alice and Bob each run their respective entangled qubits through their chosen circuit, they measure both wires (they entangle themselves into the system). For each wire, they get an ‘On’ or ‘Off’ result. Alice and Bob use those outputs to decide on how to play their tokens.
Alice’s top wire controls whether or not she places a token on the leftmost cell of the indicated row. When the wire ends up On, she places a token. When it’s Off, she doesn’t place a token. She also does the same thing with her bottom wire, except it controls the center cell of the indicated row. She places a token in the remaining cell, the rightmost one, if she already played one token but not the other.
Bob’s wires control his moves in the same fashion, except he matches up his left wire with the topmost cell of the indicated column, his right wire with the center cell, and uses the bottommost cell to ensure he played both tokens or neither token.
It turns out that this strategy ensures they always win the game. Understanding why requires understanding the operation of a quantum circuit.
Quantum Circuits: Wires=Vectors, Gates=Matrices
As I explained in Grover’s Quantum Search Algorithm, a quantum circuit is made up of wires and gates.
Each wire is a qubit. It’s a qubit, instead of a bit, because the wires can be placed into quantum superposition. A superposition pairs a complex number with every classical state the system can be in. The complex number associated with a state is called the state’s amplitude. When you measure a superposition, the probability of finding it in state S is equal to the squared magnitude of S’s amplitude.
Superpositions are often represented using BraKet notation, where states are placed between a pipe and an angle braket , and amplitudes are multiplied against the states. For example, if you measured the four wire superposition you’d always end up discovering the first wire being On, and the other three being Off. Conversely, if you measured the 2 wire superposition , you’d find each possible outcome occurring with 25% probability.
Superpositions can also be represented as a raw complex vector. Of course, we need to decide on a mapping between each entry of the vector and the possible states. For our purposes, we’ll be interpreting as the binary number 1000 and so the ‘th entry of a 16dimensional vector will correspond to the amplitude of the state .
The other type of component, gates, represent operations to apply to the vector of states. Quantum operations must be linear, and must preserve the fact that probabilities add up to 100%. In other words, every gate must correspond to a unitary complex matrix. That’s pretty convenient: we can simulate operations by multiplying , where is the vector corresponding to the superposition of our wires and is the matrix corresponding to the gate to apply.
Gates are where the phases of the amplitudes actually matter. Quantum gates can mix the components of a superposition, causing the various ways an output can be reached from an input to interfere. Whether this interference is destructive or constructive depends on the relative phases of the amplitudes.
Used Gates
Now that you know gates correspond to matrices, I can tell you what each gate used in the solution does.
As a reminder, here are the circuits we used:
Each symbol on a wire corresponds to a gate. There are six different gates shown, three that apply to one wire and three that apply to two wires.
The three gates I used that apply to a single wire are the Hadamard Gate, the Square Root of Not Gate, and what I call a Splitter Gate (because it does to a wire what beam splitters do to photons). The following diagram shows the symbol and equivalent matrix of each gate:
Notice that each of these gates mixes their inputs together. That’s where the fact that we’re quantum, instead of classical, comes into play: two components of a superposition can destructively interfere when being run through a gate. Stealing a diagram from Grover’s Quantum Search Algorithm, showing this in action for the Hadamard Gate:
Notice how the blue superposition starts off as On, gets mixed into 50% On/Off, then gets unmixed back into On. The red superposition does the same thing, but with Off! This would obviously be kind of difficult to do with a classical circuit and one wire that carried only a single bit. The magic is in the phases of the intermediate state: they agree when the initial state was On and disagree when it was Off, and so the interference plays out differently when applying the second gate.
The 2wire gates I used are actually simpler than the 1wire gates, because none of them do any mixing. They all have classical equivalents. The Swap Gate swaps the two wires’ states, the Controlled Not Gates invert one wire only if the other is On, and the Decrement Gate decreases the binary number represented by the wires (when interpreted as binary digits) by 1. The following diagram shows the symbol and equivalent matrix of each gate:
These gates, as well as several others, are included in the Gates class of my implementation.
The effect of two gates, one after the other, is equivalent to , where is the second gate’s matrix and is the first gate’s matrix. When gates apply to distinct wires, the order of and doesn’t matter.
Note that when you want to apply a gate meant for one wire to a circuit that has two wires, you use the tensor product against an identity matrix to expand the gate’s equivalent matrix from 2×2 to 4×4. If the gate is supposed to apply to the first wire, the equivalent twowire gate is , where is the 1wire gate’s equivalent matrix and is the identity matrix. If the gate is supposed to apply to the second wire, then the equivalent gate is . The next section has an example of this.
Matrices Equivalent to the Circuits
Now that we know what each individual gate does, we can multiply their effects together to get a single matrix equivalent to each circuit. For the circuit that applies to the right column, made up of a Decrement gate followed by a Square Root of Not Gate on the second wire, that works like this:
As you can see, I used the tensor product to adjust the Square Root of Not Gate to apply to the second wire out of two wires instead of just a single wire. Then I multiplied the resulting matrix against the Decrement Gate’s matrix. The resulting 4×4 matrix represents the circuit’s operation in its entirety.
The PseudoTelepathyCircuits class of my implementation includes both the circuits and their equivalent matrices. I’ll include the matrices here as well, just to be nice. Note that, since it turns out that the phase of each row doesn’t matter (will explain), I’ve simplified them slightly by adjusting the row phases.
In many ways, the matrices are simpler to work with than the circuits.
Tangent: How I Found the Matrices/Circuits
I suppose now’s the time to point out that I didn’t actually start with the circuits and get the matrices from that. Things went the other way. First, I found the matrices.
Finding the matrices was actually quite difficult. At the time, I was still confused how the heck the details of this pseudotelepathy worked. I had no idea what the hell the Wikipedia article, as it was at the time of this writing, was trying to communicate by placing Pauli matrices into a 3×3 grid (fun fact: I still don’t). I started googling and reading the papers and articles Wikipedia cited, and reading the promising things those things cited.
Eventually, I found the paper Quantum PseudoTelepathy by Gilles Brassard et al. It’s a review of games that exhibit pseudotelepathy, and happens to include the matrices for the operations used by Alice and Bob (see Section 5.2). Once I had the matrices, I could hack together code to make sure they worked and tweak them to work with my game instead of the original MerminPeres magic square game.
Now, in reality, quantum computers will not be able to just have gates for every arbitrary unitary matrix we can imagine. We’ll build them out of simpler gates. Circuits are also more concrete when it comes to diagramming things, so I wanted to find circuits made out of simple gates that ended up matching these matrices.
First, I tried to build up these circuits by hand. Apparently I’m terrible at this because my circuits each used like 20 gates. Second, I wrote a program to brute force search for circuits that matched the matrices. That worked a lot better, using at most 6 gates per circuit. Finally, I realized that the phases of the rows don’t matter (you can multiply any row by or or without affecting whether or not the solution works). Weakening the constraints on the brute force search found the circuits I’m using in this article, each using at most 4 gates.
Here’s links to the code that explores the space of circuits, and the code matching that space against the matrices.
(One interesting question that I haven’t explored much is whether there are alternative sets of matrices that correspond to much simpler or more enlightening circuits. That’s probably what the Wikipedia article was trying to communicate.)
Entangling Bits
I’ve mentioned that Alice and Bob need two pairs of entangled bits to use as inputs to their circuits. This raises the question: how do they generate them?
Well, since we’re already assuming they have the ability to evaluate quantum circuits, the simplest way would be to just do it as a quantum circuit. It turns out this is really straightforward:
The above diagram shows a circuit. Its input must be the Off,Off state. The circuit then applies a Hadamard Gate to the first wire, uniformly randomizing it, and Xors the randomized first wire into the second wire with a Controlled Not Gate. Now the two wires are in a superposition containing every possibility where the wires are in the same state. More exactly, the system ends up in the superposition with each wire corresponding to an entangled qubit (called and respectively).
We actually need two pairs entangled qubits, so let’s repeat that same trick twice:
The output of this circuit is the superposition . The top two qubits, and (which are not measured yet), go to Alice. The bottom two, and (did I stress not measuring them yet enough?), go to Bob.
Playing the Game
We now have all the components we need in order to understand a full playthrough of the game, although the why it wins part is still to come. The only thing left to realize is that, because the entangled qubits haven’t been measured, Alice and Bob are actually still part of the same circuit when they apply their individual circuits.
The following diagram shows how the game plays out, represented as a quantum logic circuit:
The code in the PlayGame function of the PseudoTelepathy class essentially just simulates the above circuit and then measures the result.
The question now is: given this circuit, what is the final state of the system?
Initially, the system is in the state. Actually, I’m going to represent that as to cut down on the amount of text.
Then the two Hadamard and Controlled Not Gates are applied, creating two entangled qubits. This places the system into the state .
Next the two top and bottom wires are fed to the isolated Bob and Alice respectively. This does not affect the state of the system.
Penultimately, Bob and Alice each apply their circuits. It doesn’t matter what order this happens in (the operations commute because they apply to different wires). To represent the effect of the 2wire circuits on the 4wire system, we use the same trick for going from 1 wire to 2 wires: tensor product against the identity matrix. Actually, since , we can just tensor product their circuits together.
The state of the system, after applying , is times .
Finally, Alice and Bob will measure their parts of the system. They end up in each state shown in the above superposition with equal probability. For example, they could end up in which is for Alice and for Bob. Let’s see how the game plays out in this case.
Since his high wire is On, Bob places a token in the the center cell of the indicated column (i.e. he covers the center left cell). Since his low wire is Off, he places no token in the top cell. Finally, he places a token on the the bottom left cell to correct the fact that he had an unpaired token. Alice places no tokens in her center or leftmost cells, since her high and low wires are respectively Off, and since she placed no unpaired token she also places no token in her rightmost cell.
Hey, they just won! Bob placed a token on the common cell, the bottom left, and Alice didn’t. In fact, if you go through every possible case in the final superposition, they’re all winning results. If you’re really determined, and try playing on the other possible rows and columns, you’ll find that the same thing happens in every single case!
How can this be?
Matrix Constraints
Now we get to the meat of how things work. Let’s take a closer look at :
I’ve obscured almost all of this matrix. Why? Because almost none of it matters to the result. Most columns are never used, and most rows don’t affect whether or not we have a winning solution.
Note that the input to a circuit, in our case it’s the superposition over two pairs of entangled qubits, applies a scale factor to each column based on each state’s amplitude. The output superposition is then determined by summing across rows. Simplifying a bit, columns=inputs and rows=outputs.
We know our circuit’s input is the superposition . This superposition only uses 4 of the 16 possible states (all the others have an amplitude of 0). That means all columns, except the four columns corresponding to the states in our input superposition, will be multiplied by zero. That’s why I’ve obscured them: they don’t affect the result. The remaining four columns all contribute equally.
We also know that only some outputs correspond to losing. We don’t really care how we win, as long as we don’t lose. It’s fine if the amplitudes of winning outputs get scrambled, but the amplitudes of any losing output must be zero. Otherwise we don’t have a consistently winning strategy. So the obscured rows actually correspond to the winning outputs, which we don’t care about constraining, and the nonobscured rows are the losing outputs.
Notice that all of the nonobscured rows in the diagram sum out to zero (counting only the nonobscured columns). That means that, in this case, losing results all get no amplitude. Only winning results get any amplitude. Winning is guaranteed. With this in mind, we can stop seeing winning in terms of the game and start seeing it in terms of a constraint satisfied by the matrix combinations: for each losing row, the sum over the four columns that matter must be zero. (Note that the positions of the losing rows change based on which matrices are being combined, since those correspond to different cases in the game.)
Since we always use the same input, it’s always the same columns that matter: the 1st, 6th, 11th, and 16th. We can understand where these columns come from by analyzing what the tensor product does when combining Alice and Bob’s matrices. The 1st column is the tensor product of the 1st column of the matrix chosen by Alice and the 1st column of the matrix chosen by Bob. The 6th is the tensor product of the second columns, the 11th of the third columns, and the 16th of the fourth columns.
The important thing to realize about what I just said is that the columns that matter in the 16×16 matrix are generated entirely by pairing columns in the same position from the 4×4 matrices Alice and Bob use. That means summing across the columns that matter is actually just computing the dot product of an Alice row and a Bob row. That allows us to rewrite all our notlosing constraints into the form .
Since we have 9 matrix combinations and 8 losing rows per combination, not losing gives us 72 equations that must be satisfied, over the 96 complex numbers making up our 6 matrices. Solving that system of equations (while also considering other constraints, like ‘must be unitary’) would allow us to find matrices that constituted a pseudotelepathic solution to the game. The matrices I presented above are a particular example of a solution to the system.
The End
We’re actually done. All the information required to understand the solution has been stated. Implementing (a simulation of) the solution is just a matter of multiplying the initial vector against the correct matrices and confirming that the result only has amplitude in winning states.
The matrices that correspond to the “winning” circuits have the property that they transform the initial entangled state in a way that gives no amplitude to losing states. That’s all there is to it. The game exhibits pseudotelepathy because the system of constraints the matrices must satisfy is solvable when the matrices are unitary (i.e. you’re using quantum mechanics) but infeasible when the matrices are stochastic (i.e. classical physics).
Actually, come to think of it, there are still some questions left over. For example, there are probably other interesting sets of matrices that solve the problem. The six I used are probably not the only ones. Are there simpler ones? Ones that correspond to really simple circuits? Ones that make it intuitively obvious that the circuits form a solution? I don’t know. I’ll leave that to you to find out. (Presumably whatever Wikipedia is trying to explain corresponds to a simpler set of six matrices.)
You can peruse my pseudotelepathy simulating implementation over at github, in case you feel anything was left ambiguous. I almost definitely made sign errors and endian errors in this post, but I know for a fact that the code works. If you clone the repo, open it in visual studio, and run it then you should see something like this:
Winning Strategy: Check!
Game:
 Referee picks random row and col.
 Alice is told row and covers 0 or 2 cells in row with 'A' tokens.
 Bob is told col and covers 0 or 2 cells in col with 'B' tokens.
 (They can't communicate, but they can have preshared entangled qubits.)
 Alice and Bob win if their common cell has exactly one token on it
 (Without entangled qubits they can't win CONSISTENTLY. Can they do it with???)
Press enter to run a game...
+
 Ref picked row = 0, col = 2

 Ref tells Alice the row and Bob the col.
 They each pick a circuit and run their qubits through.
 They measure the outputs of their circuits:
 Alice: On On, Bob: On Off

 Alice independently places 2 tokens
 Bob independently places 2 tokens
 The result:
 A  A >B
 ++
    
 ++
     B

+
 They Won!
+
Press enter to run a game...
Update: This post had some errata. One of the controlled not gates had the wrong associated matrix. Half the circuits were wrong because I thought I could get away with not testing my matrix multiplication code. I've fixed the issues.
Summary
Quantum pseudotelepathy refers to the ability to consistently win games that can't be won consistently by players limited to classical physics.
Strategies for these games can be understood as quantum logic circuits that involve entangled qubits, which can be thought of as being equivalent to unitary matrices. Winning can be thought of as constraints these matrices must satisfy. Classical strategies are limited to stochastic matrices, so sometimes they can't win consistently when quantum strategies can.
I wrote code, available on github, that simulates the quantum circuits that solve the game I described in this post.

Discuss on Reddit

My Twitter: @CraigGidney

Twisted Oak Studios offers consulting and development on hightech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.
Archive
 strilanc
 What Quantum Computers Do Faster, with Caveats
 Naming Things: FailUseful
 Detecting Simple Cycles Forming, Faster
 Third Party Bit Commitment
 Angular Velocity is Simple
 Collection Equality is Hard
 Deadlocks in Practice: Don’t Hold Locks While Notifying
 Brute Force Parallelization
 A Year’s Worth of Opinions about ObjectiveC
 Referencing Substrings Faster, without Leaking Memory
 Not Crying Over Old Code
 Exploring Universal Ternary Gates
 Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks
 Achieving Exponential Slowdown by Enumerating Twice
 Using Immortality to Kill Accidental Callback Cycles
 Cancellation Tokens (and Collapsing Futures) for ObjectiveC
 Visualizing the Eigenvectors of a Rotation
 Collapsing Futures in ObjectiveC
 Bug Hunting #1: Garbled Audio from End to End
 Impractical Experiments #1: Representing Numbers as Polynomials
 Implementing Quantum PseudoTelepathy
 Turn On Your Damn Warnings
 BigO Made Trivial
 Unfathomable Bugs #7: The Broken Oven
 Solomonoff’s Mad Scientist
 Yearly Blogging Roundup #1
 What isn’t a Monad
 Searching a Sorted Matrix Faster
 How to Read Nested Ternary Operators
 Making Sublime Text 2 Jump to the Correct Line with Unity on OS X
 My Bug, My Bad #4: Reading Concurrently
 Whole API Testing with Reflection
 Optimizing a Parser Combinator into a memcpy
 Don’t Treat Paths Like Strings
 Breaking a Toy Hash Function
 Counting Iterators Lazily
 Unfathomable Bugs #6: Pretend Precision
 My Bug, My Bad #3: Accidentally Attacking WarCraft 3
 Collapsing Types vs Monads (followup)
 Collapsing Futures: Easy to Use, Hard to Represent
 Eventual Exceptions vs Programming in a Minimal Functional Style
 The Mystery of Flunf
 Explain it like I’m Five: The Socialist Millionaire Problem and Secure MultiParty Computation
 Computer Science Blows My Mind
 A visit to Execution Labs in Montréal
 Transmuting Dice, Conserving Entropy
 Rule of Thumb: Ask for the Clock
 Rule of Thumb: Use Purposefully Weakened Methods
 Rule of thumb: Preconditions Should be Checked Explicitly
 Intersecting Linked Lists Faster
 Mouse Path Smoothing for Jack Lumber
 My Bug, My Bad #2: Sunk by Float
 Repeat Yourself Differently
 Grover’s Quantum Search Algorithm
 Followup to NonNullable Types vs C#
 Optimizing Just in Time with Expression Trees
 When OneWay Latency Doesn’t Matter
 Determining exactly if/when/where a moving line intersected a moving point
 Emulating Actors in C# with Async/Await
 Making an immutable queue with guaranteed constant time operations
 Improving Checked Exceptions
 Perishable Collections: The Benefits of RemovalbyLifetime
 Decoupling shared control
 Decoupling inlined UI code
 Linq to Collections: Beyond IEnumerable<T>
 Publish your .Net library as a NuGet package
 When null is not enough: an option type for C#
 Unfathomable Bugs #5: Readonly or not
 Minkowski sums: examples
 My Bug, My Bad #1: Fractal Spheres
 Working around the brittle UI Virtualization in Windows 8
 Encapsulating Angles
 Unfathomable Bugs #4: Keys that aren’t
 How would I even use a monad (in C#)?
 Useful/Interesting Methods #1: Observable.WhenEach
 Unfathomable Bugs #3: Stringing you along
 Anonymous Implementation Classes – A Design Pattern for C#
 Tasks for ActionScript 3 – Improving on EventDriven Programming
 Minkowski sums and differences
 NonNullable Types vs C#: Fixing the Billion Dollar Mistake
 Unfathomable Bugs #2: Slashing Out
 Script templates and base classes
 Unity font extraction
 Abusing “Phantom Types” to Encode List Lengths Into Their Type
 Constructive Criticism of the Reactive Extensions API
 Quaternions part 3
 Quaternions part 2
 Quaternions part 1
 Unfathomable Bugs #1: You can have things! You can have things IN things! You can have …
 Coroutines – More than you want to know
 Asset Bundle Helper
 The Visual Studio goes away
 .Net’s time traveling StopWatch
 Introducing Catalyst