Quantum games are similar to probability games played in a casino. They usually involve several players who cooperatively play a game against the house (sometimes called referee). The players are given some random inputs, and they have to make a choice on which output to give back to the house. They are not allowed to communicate during the game, so they have to prepare a strategy in advance in order to have the best chance to win the game. To win the game, the outputs given by the players have to satisfy a certain condition characteristic of the game played.
For such games, the players are allowed to use either classical or quantum strategies. We'll see in more details what is meant by classical/quantum strategy once we go into the game. For now, just think of it as the kinds of manipulations they are allowed to do. In classical strategies, they are only allowed to manipulate their inputs classically, that is with the help of objects whose behaviour can be described using classical physics. In quantum strategies, they are allowed to use quantum objects (which follow the rules of quantum mechanics) to manipulate the inputs given to them.
Quantum computation is a new kind of computation which differs from the current way of doing computations in the same way quantum strategies differ from classical strategies. Classical computations can be implemented in several ways, the most successful one today is the circuit model of computation. This is how elements in modern computers are designed. In the circuit model, a computation is made by taking a string of bits as inputs, doing certain operations on them and giving a new string of bits as output. In the current paradigm, these operation are logical operations that follow Boole's logic. It was proved that one needs to be able to carry out a limited set of operation (namely "not gate", and "and gate") in order to implement any operation (addition, multiplication, division, ... ) by a combination of operation from this set. This fundamental set of gates is called an "elementary set of gates" and is all that is required to be able to do any computation. Similarly to classical computation, quantum computation can be done using the circuit model of computation. In this case, bits are replaced by qubits and logic gates must be substituted with quantum gates which can operate on qubits while keeping intact their special quantum properties. Here there is another difference which we haven't mentioned, quantum circuits must be reversible due to the reversibility ineherent in the laws of quantum mechanics. A reversible circuit allows you to run the computation backwards and retrieve the inputs given the outputs. Classical computation can also be imnplemented using reversible gates but there are disadvanteges with regards to the circuit size and complexity. Thus modern computer are built with "irreversible" logic (which means it's impossible to run the computation backwards, see truth table of the "AND" gate for example) and this is the reason why the generate heat! In order to have reversible quantum gates, one must implement these gates using, what is called "unitary operations", that is operations which preserve the sum of the probabilities of seeing each of the measurable values of the qubits. Altough, the probability of seeing any single outcome can change, their sum will always add up to one.
In quantum computation the objects of the computation are quantum objects called qubits. Similarly to bits, qubits can take two values: $$\lvert 0 \rangle , \lvert 1 \rangle .$$
Where the brackets around the number points to the fact that these are quantum objects (see Dirac's notation). Differently from the regular bits stored in a computer, which can either take the value of "0" or "1", qubits can be in a superposition of "0" and "1". $$\alpha \lvert 0 \rangle + \beta \lvert 1 \rangle,$$
where $\alpha$ and $\beta$ are complex numbers and are related to the probability of obtaining the corresponding outcome $\lvert 0 \rangle$ or $\lvert 1 \rangle$.
$$P(qubit \, state = 0) = \lvert \alpha \rvert^{2}$$$$P(qubit \, state = 1) = \lvert \beta \rvert^{2}$$Which means the qubit has simultaneously the value "0" and "1" and, only when measured, will take one of the two values with probability $\lvert \alpha \rvert^{2}$ and $\lvert \beta \rvert^{2}$ respectively. Another interesting property of qubits, which departs from the classical world, is that they can be entangled. If qubits are entangled with each other, the value taken by each of them is strictly related to the value taken by the other. The correlations between the values of entangled qubits is so strong that it cannot be described by classical probability theory. This is one of the most peculiar features of quantum mechanics. In a way, entangled qubits lose their identity as individual objects, as their properties now depend on the properties of the other objects with which they are entangled. It's not possible to separate an entangled system in independent parts and it must be treated as a new unit (in quantum mechanical terms, the state of the whole system is not separable. it cannot be factorized as product state of the state of individual systems). However, in order to know about these quantum objects we must make a measurement of their state. This, causes the system to take one particular value among a set that are compatible to its state. It is not possible to determine with certainity which value the system will take, but one can only know the various probabilities for the allowed values and then sit back and watch what the system "chooses".
Quantum gates implement operations on qubit by keeping intact their quantum properties. Furthermore, they allow some of those properties to arise, for example by putting qubits in a superposition of states or entangling with each other. Let's see some quantum gates:
These gates act on a qubit, affecting its state:
X: flips the state of a qubit from $\lvert 0 \rangle \rightarrow \lvert 1 \rangle $ and $\lvert 1 \rangle \rightarrow \lvert 0 \rangle $ .
Z: flips the phase of a qubit (changes relative sign of $\alpha$ and $\beta$).
Y: flips the state of a qubit and its phase.
H: puts qubit in a superposition of $\lvert 0 \rangle$ and $\lvert 1 \rangle$
Rotations around an axis ($R_x, R_y, R_z$): Rotates qubit, by changing the coefficients $\alpha, \beta$ in a way that depends on the angle of rotation.
The most important two qubit gate is the controlled-not gate:
CX: flips the state of a qubit conditionally on the state of another qubit.
In more details, one of the qubit is taken as control qubit (and it is unaffected by the gate) and the other as target qubit. If the control qubit is in the state $\lvert 0 \rangle$, nothing is done to the target qubit. If the control qubit is in state $\lvert 1 \rangle$, the X gate (bit-flip) is apllied to the target qubit.
Ok, enough with the theory! Let's get our hands dirty and write a simple quantum game which will bring the quantum weirdness all the way from the textbooks to your personal computer!
In this tutorial we will see what has been called the CHSH (John Clauser, Michael Horne, Abner Shimony, and Richard Holt) game. Although related to the CHSH inequality [3], it doesn't really share the same authors and its origin appear to be lost in the history of quantum computation.
The game involves two players (Alice and Bob) who play against the house. Alice and Bob can discuss and pick a strategy before the game starts, but are not allowed to communicate after the beginning of the game. A referee generates two random bits x and y which are then given as inputs to Alice and Bob respectively. Alice and Bob do not know each other's inputs. They can manipulate their own input however they wish, according to their strategy, and then choose a bit to output. Alice will output a bit a and Bob a bit b
Alice and Bob win against the house if the following condition is satisfied:
$$ x \cdot y = a \oplus b $$
In [1]:
# useful packages
import numpy as np
import random as rand
# importing Qiskit
from qiskit import Aer
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute
In [2]:
# You may need to trust this notebook before the button below works
In [1]:
from IPython.display import HTML
HTML('''<script>
code_show=true;
function code_toggle() {
if (code_show){
$('div.input').hide();
} else {
$('div.input').show();
}
code_show = !code_show
}
$( document ).ready(code_toggle);
</script>
<form action="javascript:code_toggle()"><input type="submit" value="Click here to toggle on/off the raw code."></form>''')
Out[1]:
Let's first play the game using a deterministic classical strategy. Remember, this means that Alice can only devise a strategy based on her value of the input bit x and Bob according to its input value y and they cannot communicate with each other. Here are a few possible strategies:
1) output = input
2) output = NOT(input)
3) always output = 1
4) always output = 0
HINT: the best possible classical strategy for Alice and Bob is to always output the same answer, independently of the input. This gives a 75% winning probability!
In [3]:
def cplayer_output(strategy, inp):
if(strategy == 1):
return inp
elif(strategy == 2):
return abs(inp-1)
elif(strategy == 3):
return 1
elif(strategy == 4):
return 0
else:
print("INVALID choice")
return 100
In [4]:
# Pick Alice's classical strategy
A_st = int(input('select the classical strategy for Alice, input 1,2,3 or 4 to pick one of the strategies listed above '))
# Pick Bob's classical strategy
B_st = int(input('select the classical strategy for Bob, input 1,2,3 or 4 to pick one of the strategies listed above '))
In [5]:
# fixes the numbers of games to be played
N=100
# initializes counters used to keep track of the numbers of games won and played by Alice an Bob
cont_win = 0 # counts games won
cont_tot = 0 # counts games played
# play the game N times
for i in range(N):
# generates two random input from the refree, x and y, to be given to Alice and Bob
random_num1 = rand.random() # first random number
random_num2 = rand.random() # second random number
if(random_num1 >= 1/2): # converts the first random number to 0 or 1
x = 0
else: x = 1
if(random_num2 >= 1/2): # converts the second random number to 0 or 1
y = 0
else: y = 1
# generates Alice's and Bob's output
a = cplayer_output(A_st, x) # Alice's output
b = cplayer_output(B_st, y) # Bob's output
# check if the condition for winning the game is met
if(x*y == a^b):
cont_win += 1 # increase thes won games' counter if the condition to win the game is met
cont_tot += 1 # increases the played games' counter
Prob_win = cont_win/cont_tot # winning probability
print('Alice and Bob won the game with probability: ', Prob_win*100, '%')
As a quantum strategy, Alice and Bob play the game by sharing an entangled pair of qubit. That is, two qubits are brought together to form an entangled pair and then Alice and Bob are given one each. Beware, even though the entangled qubits influence each other, it is not possible for Alice and Bob to use them to communicate with each other during the game.
According to the input they receive from the refree they will rotate their entangled qubit and then measure it. For example, pick one of the following strategies:
1) don't rotate the qubit
2) rotate a random amount
3) rotate to maximize winning probability
HINT: It is possible to prove what is the best angle of rotation for Alice and Bob depending on the input x,y that they receive. This allows for a winning probability of around 85%! Better than any classical strategy! More details can be found in [4].
In [6]:
def qAlice_output(strategy, inp):
if(strategy == 1):
return 0
elif(strategy == 2):
return rand.uniform(0,2*np.pi)
elif(strategy == 3):
if(inp == 0):
return 0
elif(inp == 1):
return np.pi/2
else:
print("INVALID choice")
return 100
def qBob_output(strategy, inp):
if(strategy == 1):
return 0
elif(strategy == 2):
return rand.uniform(0,2*np.pi)
elif(strategy == 3):
if(inp == 0):
return np.pi/4
elif(inp == 1):
return -np.pi/4
else:
print("INVALID choice")
return 100
In [7]:
# Alice's strategy
qA_st = int(input('select the quantum strategy for Alice, input 1,2 or 3 to pick one of the strategies listed above: '))
# Bob's strategy
qB_st = int(input('select the quantum strategy for Bob, input 1,2 or 3 to pick one of the strategies listed above: '))
In [8]:
# set parameters of the quantum run of the game
shots = 1 # set how many times the circuit is run, accumulating statistics about the measurement outcomes
backend = Aer.get_backend('qasm_simulator') # set the machine where the quantum circuit is to be run
#fixes the numbers of games to be played
N=100
# initializes counters used to keep track of the numbers of games won and played by Alice an Bob
cont_win = 0 # counts games won
cont_tot = 0 # counts games played
#play N games
for i in range(N):
# creates registers for qubits and bits
# creates a quantum register, it specifies the qubits which are going to be used for the program
q = QuantumRegister(2, name='q')
# creates a classical register, the results of the measurement of the qubits are stored here
c = ClassicalRegister(2, name='c')
# creates quantum circuit, to write a quantum algorithm we will add gates to the circuit
game = QuantumCircuit(q, c, name='game')
# These gates prepare the entangled Bell pair to be shared by Alice and Bob as part of their quantum strategy
# Alice will have qubit 0 and Bob will have qubit 1
game.h(q[0]) # Hadamard gate on qubit 0
game.cx(q[0],q[1]) # CNOT gate on qubit 1 controlled by qubit 0
# generates two random input from the refree, x and y, to be given to Alice and Bob
random_num1 = rand.random() # first random number
random_num2 = rand.random() # second random number
if(random_num1 >= 1/2): # converts the first random number to 0 or 1
x = 0
else: x = 1
if(random_num2 >= 1/2): # converts the second random number to 0 or 1
y = 0
else: y = 1
# The main part of Alice and Bob quantum strategy is to fix different rotation angles for their qubit according to the input x,y
theta = qAlice_output(qA_st, x) # fixes Alice's rotation for her qubit
phi = qBob_output(qB_st, y) # fixes Bob's rotation for his qubit
# The following gates rotate Alice's qubit and Bob's qubit
game.ry(theta,q[0]) #rotates Alice's qubit of an angle theta
game.ry(phi,q[1]) ##rotates Bob's qubit of an angle phi
# These gates are used to measure the value of the qubits
game.measure(q[0], c[0]) # measure Alice's qubit and stores the result in a classical bit
game.measure(q[1], c[1]) # measure Bob's qubit and stores the result in a classical bit
# executes circuit and store the output of the measurements
result = execute(game, backend=backend, shots=shots).result()
data = result.get_counts('game') # extract the outcomes and their statistics from the result of the execution
# reads the result of the measurements of the quantum system
for outcomes in data.keys():
out = outcomes
# converts the result of the measurements contained in the classical register as string '00', '01', '10', '11',
# which are the answers of Alice(a) and Bob (b), from a 'string' type to 'integer' type
if(out == '00'):
a = 0
b = 0
if(out == '01'):
a = 1
b = 0
if(out == '10'):
a = 0
b = 1
if(out == '11'):
a = 1
b = 1
# check if the condition for winning the game is met
if(x*y == a^b):
cont_win += 1 # increase thes won games' counter if the condition to win the game is met
cont_tot += 1 # increases the played games' counter
qProb_win = cont_win/cont_tot
print('Alice and Bob won the game with probability: ', qProb_win*100, '%')
In [9]:
if Prob_win > qProb_win :
print("The classical strategy gave Alice and Bob higher chances of winning")
else:
print("The quantum strategy gave Alice and Bob higher chances of winning")
Let us find the best classical strategy to maximize the winning probability for Alice and Bob. If we consider the following truth table:
| x | y | x.y | . | . | . | . | a | b | a$\oplus$b |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | . | . | . | . | 0 | 0 | 0 |
| 0 | 1 | 0 | . | . | . | . | 0 | 1 | 1 |
| 1 | 0 | 0 | . | . | . | . | 1 | 0 | 1 |
| 1 | 1 | 1 | . | . | . | . | 1 | 1 | 0 |
The following table shows the winning conditions:
| x | y | a$\oplus$b |
|---|---|---|
| 0 | 0 | a=b |
| 0 | 1 | a=b |
| 1 | 0 | a=b |
| 1 | 1 | a=b$\oplus$1 |
Therefore, Alice and Bob can win with probability $3/4$. One possible strategy for Alice and Bob is to ignore the input values and both select "Always Output=0" (strategy 4 for Alice and strategy 4 Bob). Another strategy is for Bob to select "Always Oputput=0" and Alice gamble by selecting "Input=Output" to win if the input $x=1$ and Bob's input $y=0$ (strategy 1 for Alice and strategy 4 Bob). In both strategies, the winning probability is 75%.
Quantum systems offer a degree of freedom with no classical counterpart. If before the game starts Alice and Bob share an entangled bipartite state, they can win with a probability of $cos^{2}(\frac{\pi}{8})\approx 85\%$. The winning strategy is as follows [4]:
1- Alice and Bob share two-qubit EPR (Einstein–Podolsky–Rosen) state: $$ |\Psi\rangle_{AB}=\frac{1}{\sqrt{2}}(|0\rangle_{A}\otimes|0\rangle_{B}+|1\rangle_{A}\otimes|1\rangle_{B}) $$ Where state $A$ belongs to Alice and State $B$ belongs to Bob.
2- They define a measurement bases denoted by $v_{i}(\theta)$ where $\theta \in [0,2\pi)$:
$$ |v_{0}(\theta)\rangle = cos(\theta)|0\rangle + sin (\theta)|1\rangle $$$$ |v_{1}(\theta)\rangle = -sin(\theta)|0\rangle + cos (\theta)|1\rangle $$Based on the input value Alice and Bob a measurement bases. The following are all possible winning probability after substituting $ v_{i}(\theta) $ and $ |\Psi\rangle_{AB}$
Alice and Bob choose a set of angles separated by $22.5^\circ$ To maximize their winning probability. For example, Alice chooses $ \{ \theta_{A0}=0, \theta_{A1}=\frac{\pi}{4} \}$ and Bob chooses $ \{ \theta_{B0}=\frac{\pi}{8}, \theta_{B1}=-\frac{\pi}{8} \}$ . The overall winning probability using the quantum system is: $$ P_{0,0} + P_{0,1} + P_{1,0}+P_{1,1} $$
$$ cos^{2}(\frac{\pi}{8}) + cos^{2}(\frac{\pi}{8})+cos^{2}(\frac{\pi}{8})+sin^{2}(\frac{3\pi}{8}) $$$$ \frac{3}{4} cos^{2}(\frac{\pi}{8}) + \frac{1}{4} sin^{2}(\frac{3\pi}{8}) \approx 85\% $$If Alice and Bob choose "rotate to maximize winning probability" (strategy 3 for Alice and strategy 3 Bob) they get a higher probability of winning using the quantum system than the classical system $ 85\% > 75\%$ .
[1] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000).
[2] J. S. Bell, Speakable and unspeakable in quantum mechanics: Collected papers on quantum philosophy (Cambridge university press, 2004).
[3] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Proposed experiment to test local hidden-variable theories, Physical review letters, 23 (1969), p. 880.
[4] Detailed description of optimal quantum strategy:
https://sergworks.wordpress.com/2016/10/26/chsh-game-in-detail/
[5] connection between CHSH game and Bell's inequalities:
https://cs.uwaterloo.ca/~watrous/CPSC519/LectureNotes/20.
https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/OS_QIT_2016S/Vortrag7.pdf