<jupyter_start><jupyter_text>Trusted Notebook" width="250 px" align="left">  _*Winning The Game of Magic Square with Quantum Pseudo-Telepathy *_ The latest version of this notebook is available on https://github.com/QISKit/qiskit-tutorial.*** Contributors<NAME>  IntroductionWe 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Quantum_pseudo-telepathy), 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).      Quantum Winning StrategyHowever, 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](https://arxiv.org/abs/quant-ph/0407221). Preparing the environmentFirst, as usual we prepare the environment.<jupyter_code># Checking the version of PYTHON; we only support > 3.5
import sys
if sys.version_info < (3,5):
    raise Exception('Please use Python version 3.5 or greater.')

# 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 QuantumProgram
import Qconfig

# import basic plot tools
from qiskit.tools.visualization import plot_histogram<jupyter_output><empty_output><jupyter_text>Sharing entangled quantum statesPrior 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.<jupyter_code>Q_program = QuantumProgram()
Q_program.set_api(Qconfig.APItoken, Qconfig.config["url"]) # set the APIToken and API url

N = 4
# Creating registers
qr = Q_program.create_quantum_register("qr", N)

# for recording the measurement on qr
cr = Q_program.create_classical_register("cr", N)

circuitName = "sharedEntangled"
sharedEntangled = Q_program.create_circuit(circuitName, [qr], [cr])

#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])<jupyter_output><empty_output><jupyter_text>Alice's and Bob's operationsReceiving $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.<jupyter_code>#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<jupyter_output><empty_output><jupyter_text>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.<jupyter_code># 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] = Q_program.create_circuit(circuitName, [qr], [cr])
    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] = Q_program.create_circuit(circuitName, [qr], [cr])
    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])<jupyter_output><empty_output><jupyter_text>A quantum program for one round of the gamePrior 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.<jupyter_code>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)
Q_program.add_circuit(circuitName, sharedEntangled+aliceCircuit+bobCircuit)

backend = "local_qasm_simulator"
##backend = "ibmqx2"

shots = 1 # We perform a one-shot experiment
results = Q_program.execute([circuitName], backend=backend, shots=shots)
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")<jupyter_output>The values of a and b are, resp., 2 1
{'0100': 1}
Alice answer for a =  2 is [0, 0, 0]
Bob answer for b =  1 is [1, 0, 0]
Alice and Bob won<jupyter_text>Checking Alice's and Bob's answers for all combinations of their inputsFinally, 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 `ibmqx2` 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).<jupyter_code>backend = "local_qasm_simulator"
#backend = "ibmqx2"
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)
        Q_program.add_circuit(circuitName, sharedEntangled+aliceCircuit+bobCircuit)

        if backend == "ibmqx2":
            ibmqx2_backend = Q_program.get_backend_configuration('ibmqx2')
            ibmqx2_coupling = ibmqx2_backend['coupling_map']
            results = Q_program.execute([circuitName], backend=backend, shots=shots, coupling_map=ibmqx2_coupling, max_credits=3, wait=10, timeout=240)
        else:
            results = Q_program.execute([circuitName], backend=backend, shots=shots)
        answer = results.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))<jupyter_output>Asking Alice and Bob with a and b are, resp., 1 1
	#wins =  10 out of  10 shots
Asking Alice and Bob with a and b are, resp., 1 2
	#wins =  10 out of  10 shots
Asking Alice and Bob with a and b are, resp., 1 3
	#wins =  10 out of  10 shots
Asking Alice and Bob with a and b are, resp., 2 1
	#wins =  10 out of  10 shots
Asking Alice and Bob with a and b are, resp., 2 2
	#wins =  10 out of  10 shots
Asking Alice and Bob with a and b are, resp., 2 3
	#wins =  10 out of  10 shots
Asking Alice and Bob with a and b are, resp., 3 1
	#wins =  10 out of  10 shots
Asking Alice and Bob with a and b are, resp., 3 2
	#wins =  10 out of  10 shots
Asking Alice and Bob with a and b are, resp., 3 3
	#wins =  10 out of  10 shots
Number of Games =  90
Number of Wins =  90
Winning probabilities =  100.0<jupyter_text>About Quantum Pseudo-Telepathy for the Magic Square Game The winning strategy described in this note is from [Brassard et al. 2004](https://arxiv.org/abs/quant-ph/0407221), where there listed many other interesting games that can be accomplished with shared entanglement. The Magic Square game was first proposed by [Aravind, 2002](https://arxiv.org/abs/quant-ph/0206070) based on the work of [Mermin, 1990](http://blog.umd.edu/phil858/files/2015/10/Mermin1990-2jvtdbh.pdf) and [Peres, 1990](http://blog.umd.edu/phil858/files/2015/10/Peres1990-2g8uzi6.pdf).[Gawron et al., 2008](https://arxiv.org/pdf/0801.4848v1.pdf) showed that the winning probabilities of Magic Square Games is related to the noise of the circuits. [Ozaydin, 2016](https://arxiv.org/abs/1609.03881) 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](http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0064694) showed that it is possible to achieve higher winning probability under noisy circuits by employing Semidefinite Programming for noise mitigation.<jupyter_code>%run "../version.ipynb"<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12270116609618843, 'fraction_numerical': 0.03596913616058479, 'mean_word_length': 3.332244282483036, 'pattern_counts': {'":': 1, '<': 29, '<?xml version=': 0, '>': 30, 'https://': 8, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '62987', 'license': 'Apache-2.0', 'n_tokens_mistral': 6438, 'n_tokens_neox': 5766, 'n_words': 1984, 'path': '5_games/quantum_magic_square.ipynb', 'repo_name': 'sharmasas/qiskit-tutorial', 'size': '17243'}