Non-local games
An example: the Magic Square game.
Alice
Bob
Alice
Bob
1
0
0
odd parity
even parity
1
1
consistency
Alice and Bob win if their answers satisfy all three conditions.
Referee
Can Alice and Bob win perfectly?
No communication
“column i”
“row j”
“100”
“101”
(assuming the Referee chooses the questions uniformly at random)
Strategies for the Magic Square game
1
0
0
Alice
Bob
0
1
1
1
1
1
1
0
0
1
1
0
0
1
1
odd parity
even parity
Alice and Bob can decide on how they are each going to answer all of their possible questions (deterministically).
This induces a 3x3 square of answers for Alice and one for Bob (which need not be the same).
Strategies for the Magic Square game
1
0
0
Alice
Bob
0
1
1
1
1
1
1
0
0
1
1
0
0
1
1
Alice and Bob can decide on how they are each going to answer all of their possible questions (deterministically).
This induces a 3x3 square of answers for Alice and one for Bob (which need not be the same).
Strategies for the Magic Square game
1
0
0
Alice
Bob
0
1
1
1
1
1
1
0
0
1
1
0
0
1
1
Alice and Bob should agree on the same 3 x 3 square if they want to satisfy consistency!
The question of whether there exists a perfect strategy becomes: does there exist a 3 x 3 square that satisfies all of the parity constraints?
Alice and Bob can win perfectly if and only if such a 3 x 3 square exists.
Magic square?
Do randomized strategies help?
No.
Magic square?
Does not exist.
Parity of sum of all 9 entries:
= Odd + Odd + Odd = Odd.
= Even + Even + Even = Even.
This is a contradiction.
1
0
0
Alice
Bob
0
1
1
1
1
1
1
0
0
1
1
0
0
1
1
Best winning probability is 8/9
(in the classical world..)
What about in the quantum world?
They can do this by sharing an EPR pair:
With quantum resources, Alice and Bob can win with probability 1!
Alice
Bob
Note: Alice and Bob are still not allowed to communicate! And the game is identical as before. The only difference is: before the game began, they created an EPR pair. Alice took one qubit, and Bob took the other. Their strategy now consists of making a measurement on their qubit dependent on the question they each receive.
How does quantum information evade the previous argument that led to an 8/9 upper bound?
(technically they need two EPR pairs, but this is not important for the discussion here)
Operational consequence: a “test” for quantumness
“Observing” a winning probability greater than 8/9
“certifies” the presence of genuine quantumness.
Alice
Bob
Make the two devices play MAGIC SQUARE game!
No communication
The magic square game as “proof” of non-determinism
Is nature deterministic?
In other words, if we fixed all of the initial conditions of a system (or of the universe), would everything that happens afterwards also be deterministically fixed?
If physical systems evolve according to the laws of physics (which we assume to be fixed), and if we fix the state of every particle in a system at a certain time,
couldn’t everything that happens later be derived exactly by solving some equations?
What does it mean for an event to be truly random?
These two processes might actually be deterministic if you could “look closely enough”! The probabilities that we assign are a proxy for our lack of information.
What does it mean for an event to be truly random?
Is any event in the universe “truly” random? �Or is it the case that every process can be predicted exactly if one were able to look closely enough?
Alice
Bob
What does a strategy look like in a deterministic world?
Any strategy of this form succeeds at most with probability 8/9!
There is a quantum strategy that succeeds with probability 1!