The latest version of this notebook is available on https://github.com/QISKit/qiskit-tutorial.
Rudy Raymond
We have seen that quantum entanglement enables phenomena that we often see in science fiction, such as, (quantum) teleportation. Now, we will see that it can give rise to a kind of telepathy between two separated parties. Well, strictly speaking, quantum entanglement does not allow communication. However, it can be used for Quantum Pseudo-Telepathy, that is, parties sharing entangled states can be seen as if having some kind of communication to outside observers.
Here, we consider the Magic Square Game, which is also known as The Mermin-Peres Magic Square Game. The magic square is a $3\times 3$ matrix whose entries are either $0$ or $1$ such that the sum of each row is even, and the sum of each column is odd. Notice that such magic square is impossible: because there are odd number of entries, the sum of rows implies that the sum of $1$s must be even, but the sum of columns implies that it must be odd. A contradiction.
The magic square game is played by a referee against two distant parties, say, Alice and Bob. In the game, the referee sends an integer $a \in \{1,2,3\}$ to Alice who must answer with the $a$-th row of the magic square, and an integer $b \in \{1,2,3\}$ to Bob, who must return the $b$-th column of the magic square. Alice and Bob win the game if the sum of entries of Alice's answer is even, the sum of Bob's answer is odd, and their intersecting answer is the same. Otherwise, the referee wins. Prior to the start of the game, Alice and Bob can meet to discuss their strategy and/or share random bits and entangled states, but they are not allowed to communicate during the game.
For example, a simple strategy for Alice and Bob is to answer to the referee according to the following $3x3$ Boolean matrix:
$$ \begin{pmatrix} 1 & 1 & 0\\ 0 & 1 & 1\\ 0 & 1 & ? \end{pmatrix}. $$That is, for $a = 1$ and $b = 2$, Alice's answer is $110$, while Bob's is $111$ and they win. However, they lose when the referee sends them $a = 3$ and $b=3$, because Alice's and Bob's answers do not satisfy the requirement. It can be shown that in the classical setting the winning probability of Alice and Bob is at most $8/9$ (in the above example, there are eight out of nine combinations of $a$ and $b$ that result in Alice and Bob winning the game).
However, with shared quantum states Alice and Bob can always win the game regardless of the values of $a$ and $b$. We show the winning strategy following Brassard, Broadbent, and Tapp, 2004.
First, as usual we prepare the environment.
In [1]:
# useful additional packages
import matplotlib.pyplot as plt
%matplotlib inline
import numpy as np
# useful math functions
from math import pi, cos, acos, sqrt
import random
# importing the QISKit
from qiskit import Aer, IBMQ, execute
from qiskit.backends.ibmq import least_busy
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
# import basic plot tools
from qiskit.tools.visualization import plot_histogram
In [2]:
# To use IBMQ online backends
IBMQ.load_accounts()
Prior to the start of the game, Alice and Bob share the following quantum state. The first two qubits go to Alice, and the rest to Bob.
$$ |\psi\rangle = \frac{1}{2}|0011\rangle - \frac{1}{2}|0110\rangle - \frac{1}{2}|1001\rangle + \frac{1}{2}|1100\rangle $$To generate such quantum state, we first prepare $4$ qubits and the corresponding $4$ classical bits to record the measurement later. Below is a quantum circuit to create the above entangled state.
In [3]:
N = 4
# Creating registers
qr = QuantumRegister(N, name="qr")
# for recording the measurement on qr
cr = ClassicalRegister(N, name="cr")
circuitName = 'sharedEntangled'
sharedEntangled = QuantumCircuit(qr, cr, name=circuitName)
#Create uniform superposition of all strings of length 2
for i in range(2):
sharedEntangled.h(qr[i])
#The amplitude is minus if there are odd number of 1s
for i in range(2):
sharedEntangled.z(qr[i])
#Copy the content of the fist two qubits to the last two qubits
for i in range(2):
sharedEntangled.cx(qr[i], qr[i+2])
#Flip the last two qubits
for i in range(2,4):
sharedEntangled.x(qr[i])
Receiving $a \in \{1,2,3\}$, Alice applies the unitary matrix $A_a$ on her qubits, where $A_a$ is one of the followings:
$$ A_1 = \frac{1}{\sqrt{2}} \begin{pmatrix} i & 0 & 0 & 1\\ 0 & -i& 1 & 0\\ 0 & i & 1 & 0\\ 1 & 0 & 0 & i \end{pmatrix},~ A_2 = \frac{1}{2} \begin{pmatrix} i & 1 & 1 & i\\ -i& 1 &-1 & i\\ i & 1 &-1 &-i\\ -i& 1 & 1 &-i \end{pmatrix},~ A_3 = \frac{1}{2} \begin{pmatrix} -1&-1&-1& 1\\ 1 & 1&-1& 1\\ 1 &-1& 1& 1\\ 1 &-1&-1&-1 \end{pmatrix} $$Meanwhile, receiving $b \in \{1,2,3\}$, Bob applies the unitary matrix $B_b$ on his qubits, where $B_b$ is one of the followings:
$$ B_1 = \frac{1}{2} \begin{pmatrix} i&-i& 1& 1\\ -i&-i& 1&-1\\ 1& 1&-i& i\\ -i& i& 1& 1 \end{pmatrix},~ B_2 = \frac{1}{2} \begin{pmatrix} -1& i& 1& i\\ 1& i& 1&-i\\ 1&-i& 1& i\\ -1&-i& 1&-i \end{pmatrix},~ B_3 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1& 0 & 0 & 1\\ -1& 0 & 0 & 1\\ 0 & 1 & 1 & 0\\ 0 & 1 &-1 & 0 \end{pmatrix} $$After applying their unitary operators, Alice and Bob independently measure their qubits in the computational basis and use the outcome as the answer to their first two bits, while their third bits can be inferred from the parity with each of their first two bits: even for Alice and odd for Bob.
Below are the circuits of Alice's and Bob's operations.
In [4]:
#we first define controlled-u gates required to assign phases
from math import pi
def ch(qProg, a, b):
""" Controlled-Hadamard gate """
qProg.h(b)
qProg.sdg(b)
qProg.cx(a, b)
qProg.h(b)
qProg.t(b)
qProg.cx(a, b)
qProg.t(b)
qProg.h(b)
qProg.s(b)
qProg.x(b)
qProg.s(a)
return qProg
def cu1pi2(qProg, c, t):
""" Controlled-u1(phi/2) gate """
qProg.u1(pi/4.0, c)
qProg.cx(c, t)
qProg.u1(-pi/4.0, t)
qProg.cx(c, t)
qProg.u1(pi/4.0, t)
return qProg
def cu3pi2(qProg, c, t):
""" Controlled-u3(pi/2, -pi/2, pi/2) gate """
qProg.u1(pi/2.0, t)
qProg.cx(c, t)
qProg.u3(-pi/4.0, 0, 0, t)
qProg.cx(c, t)
qProg.u3(pi/4.0, -pi/2.0, 0, t)
return qProg
The last two gates will be used to assign amplitudes with $i$ phase and realize the following unitaries:
$$ U_\mbox{cu1pi2} = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & i \end{pmatrix},~ U_\mbox{cu3pi2} = \frac{1}{\sqrt{2}} \begin{pmatrix} \sqrt{2} & 0 & 0 & 0\\ 0 & \sqrt{2} & 0 & 0\\ 0 & 0 & 1 & -i\\ 0 & 0 & -i & 1 \end{pmatrix} $$Next, we define circuits used by Alice and Bob for each of their inputs.
In [5]:
# dictionary for Alice's operations/circuits
aliceCircuits = {}
# Quantum circuits for Alice when receiving idx in 1, 2, 3
for idx in range(1, 4):
circuitName = "Alice"+str(idx)
aliceCircuits[circuitName] = QuantumCircuit(qr, cr, name=circuitName)
theCircuit = aliceCircuits[circuitName]
if idx == 1:
#the circuit of A_1
theCircuit.x(qr[1])
theCircuit.cx(qr[1], qr[0])
theCircuit = cu1pi2(theCircuit, qr[1], qr[0])
theCircuit.x(qr[0])
theCircuit.x(qr[1])
theCircuit = cu1pi2(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit = cu1pi2(theCircuit, qr[0], qr[1])
theCircuit = cu3pi2(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit = ch(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit.x(qr[1])
theCircuit.cx(qr[1], qr[0])
theCircuit.x(qr[1])
elif idx == 2:
theCircuit.x(qr[0])
theCircuit.x(qr[1])
theCircuit = cu1pi2(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit.x(qr[1])
theCircuit = cu1pi2(theCircuit, qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit.h(qr[0])
theCircuit.h(qr[1])
elif idx == 3:
theCircuit.cz(qr[0], qr[1])
theCircuit.swap(qr[0], qr[1])
theCircuit.h(qr[0])
theCircuit.h(qr[1])
theCircuit.x(qr[0])
theCircuit.x(qr[1])
theCircuit.cz(qr[0], qr[1])
theCircuit.x(qr[0])
theCircuit.x(qr[1])
#measure the first two qubits in the computational basis
theCircuit.measure(qr[0], cr[0])
theCircuit.measure(qr[1], cr[1])
# dictionary for Bob's operations/circuits
bobCircuits = {}
# Quantum circuits for Bob when receiving idx in 1, 2, 3
for idx in range(1,4):
circuitName = "Bob"+str(idx)
bobCircuits[circuitName] = QuantumCircuit(qr, cr, name=circuitName)
theCircuit = bobCircuits[circuitName]
if idx == 1:
theCircuit.x(qr[2])
theCircuit.x(qr[3])
theCircuit.cz(qr[2], qr[3])
theCircuit.x(qr[3])
theCircuit.u1(pi/2.0, qr[2])
theCircuit.x(qr[2])
theCircuit.z(qr[2])
theCircuit.cx(qr[2], qr[3])
theCircuit.cx(qr[3], qr[2])
theCircuit.h(qr[2])
theCircuit.h(qr[3])
theCircuit.x(qr[3])
theCircuit = cu1pi2(theCircuit, qr[2], qr[3])
theCircuit.x(qr[2])
theCircuit.cz(qr[2], qr[3])
theCircuit.x(qr[2])
theCircuit.x(qr[3])
elif idx == 2:
theCircuit.x(qr[2])
theCircuit.x(qr[3])
theCircuit.cz(qr[2], qr[3])
theCircuit.x(qr[3])
theCircuit.u1(pi/2.0, qr[3])
theCircuit.cx(qr[2], qr[3])
theCircuit.h(qr[2])
theCircuit.h(qr[3])
elif idx == 3:
theCircuit.cx(qr[3], qr[2])
theCircuit.x(qr[3])
theCircuit.h(qr[3])
#measure the third and fourth qubits in the computational basis
theCircuit.measure(qr[2], cr[2])
theCircuit.measure(qr[3], cr[3])
Prior to the start of the game, Alice and Bob share the entangled quantum states as described before. Notice that this is performed before their receiving inputs. After sharing entanglement, they are not allowed to communicate. Next, an integer $a$ is given to Alice, and $b$ to Bob. Alice and Bob then independently perform operations with one the circuits defined previously based on their inputs. They generate their answers (three bits each) based on their measurement outcomes so that the parity of Alice's answer is even, and Bob's answer is odd. Here is a program for one round of the game using the circuits previously defined.
In [6]:
a, b = random.randint(1,3), random.randint(1,3) #generate random integers
print("The values of a and b are, resp.,", a,b)
aliceCircuit = aliceCircuits["Alice"+str(a)]
bobCircuit = bobCircuits["Bob"+str(b)]
circuitName = "Alice"+str(a)+"Bob"+str(b)
circuitName = sharedEntangled+aliceCircuit+bobCircuit
# Use local qasm simulator
backend = Aer.get_backend("qasm_simulator")
# Use the IBMQ Quantum Experience
# backend = least_busy(IBMQ.backends())
shots = 1 # We perform a one-shot experiment
results = execute([circuitName], backend=backend, shots=shots).result()
answer = results.get_counts(circuitName)
print(answer)
for key in answer.keys():
aliceAnswer = [int(key[-1]), int(key[-2])]
bobAnswer = [int(key[-3]), int(key[-4])]
if sum(aliceAnswer) % 2 == 0:#the sume of Alice answer must be even
aliceAnswer.append(0)
else:
aliceAnswer.append(1)
if sum(bobAnswer) % 2 == 1:#the sum of Bob answer must be odd
bobAnswer.append(0)
else:
bobAnswer.append(1)
break
print("Alice answer for a = ", a, "is", aliceAnswer)
print("Bob answer for b = ", b, "is", bobAnswer)
if(aliceAnswer[b-1] != bobAnswer[a-1]): #check if the intersection of their answers is the same
print("Alice and Bob lost")
else:
print("Alice and Bob won")
Finally, we can try every combination of $a$ and $b$ to see that Alice and Bob can always win surely. One can also try to run the code below with IBMQ backend and check that the winning probability can be higher than $8/9$ on real devices (unfortunately, perfect probability cannot be achieved due to noise and gate errors).
In [21]:
# Use local qasm simulator
backend = Aer.get_backend("qasm_simulator")
# Use the IBMQ Quantum Experience
# backend = backend = least_busy(IBMQ.backends())
shots = 10 # We perform 10 shots of experiments for each round
nWins = 0
nLost = 0
for a in range(1,4):
for b in range(1,4):
print("Asking Alice and Bob with a and b are, resp.,", a,b)
rWins = 0
rLost = 0
aliceCircuit = aliceCircuits["Alice"+str(a)]
bobCircuit = bobCircuits["Bob"+str(b)]
circuitName = "Alice"+str(a)+"Bob"+str(b)
circuitName = sharedEntangled+aliceCircuit+bobCircuit
if backend in IBMQ.backends(filters=lambda x: x.name()):
IBMQ_backend = backend.configuration()
IBMQ_coupling = backend.configuration()['coupling_map']
results = execute([circuitName], backend=backend, shots=shots, coupling_map=IBMQ_coupling, max_credits=3)
else:
results = execute([circuitName], backend=backend, shots=shots)
answer = results.result().get_counts(circuitName)
for key in answer.keys():
kfreq = answer[key] #frequencies of keys obtained from measurements
aliceAnswer = [int(key[-1]), int(key[-2])]
bobAnswer = [int(key[-3]), int(key[-4])]
if sum(aliceAnswer) % 2 == 0:
aliceAnswer.append(0)
else:
aliceAnswer.append(1)
if sum(bobAnswer) % 2 == 1:
bobAnswer.append(0)
else:
bobAnswer.append(1)
#print("Alice answer for a = ", a, "is", aliceAnswer)
#print("Bob answer for b = ", b, "is", bobAnswer)
if(aliceAnswer[b-1] != bobAnswer[a-1]):
#print(a, b, "Alice and Bob lost")
nLost += kfreq
rLost += kfreq
else:
#print(a, b, "Alice and Bob won")
nWins += kfreq
rWins += kfreq
print("\t#wins = ", rWins, "out of ", shots, "shots")
print("Number of Games = ", nWins+nLost)
print("Number of Wins = ", nWins)
print("Winning probabilities = ", (nWins*100.0)/(nWins+nLost))
The winning strategy described in this note is from Brassard et al. 2004, where there listed many other interesting games that can be accomplished with shared entanglement. The Magic Square game was first proposed by Aravind, 2002 based on the work of Mermin, 1990 and Peres, 1990.
Gawron et al., 2008 showed that the winning probabilities of Magic Square Games is related to the noise of the circuits. Ozaydin, 2016 provided theoretical analysis of the winning probabilities of the thermal entangled state of the spin system for the Magic Square game: the higher the temperature, the lower the winning probability. Interestingly, Pawela et al. 2013 showed that it is possible to achieve higher winning probability under noisy circuits by employing Semidefinite Programming for noise mitigation.
In [ ]: