# 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

# To use IBMQ online backends
IBMQ.load_accounts()

"""
Explanation: <img src="../../../images/qiskit-heading.gif" alt="Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook" width="500 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
Rudy Raymond
Introduction
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).     
Quantum Winning Strategy
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.
Preparing the environment
First, as usual we prepare the environment.
End of explanation
"""


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])

"""
Explanation: Sharing entangled quantum states
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.
End of explanation
"""


#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

"""
Explanation: Alice's and Bob's operations
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.
End of explanation
"""


# 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])

"""
Explanation: 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.
End of explanation
"""


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")

"""
Explanation: A quantum program for one round of the game
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.
End of explanation
"""


# 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))

"""
Explanation: Checking Alice's and Bob's answers for all combinations of their inputs
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).
End of explanation
"""


