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!
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
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 a 3 x 3 square if they want to satisfy consistency.
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.
With quantum resources, Alice and Bob can win with probability 1!
Alice
Bob
Operational consequence:
“Observing” a winning probability greater than 8/9
“certifies” the presence of genuine quantumness.
Alice
Bob
Make the two devices play MAGIC SQUARE game!
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?
Seems like these two processes are deterministic if you “look closely enough”
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!