Quantum Coin Flipping

This example implements the Quantum Coin Flipping protocol. A detailed description can be found here and a description about its implementation is briefly summarized here.

We chose the two quantum states needed for the protocol as

  • \(\Psi = c |0\rangle + s |1\rangle\)

  • \(\Psi = c |0\rangle - s |1\rangle\)

where

  • \(c = \Re(e^{i \theta})\)

  • \(s = \Im(e^{i \theta})\)

and Θ can be chosen. It is suggested that \(\theta = \frac{\pi}{9}\).

For the implementation of the protocol, first, we allocate all variables we need during the protocol. They consist of:

  • The hosts own random bits, \(b_j\) and \(d_ij\)

  • The random bits of the partner host, \(a_j\)

  • The qubits from the partner, \(\Psi_{e_{ij}}\) and \(\Psi_{\bar{e}_{ij}}\)

  • The final sorted qubits which are left at the end of the protocol in this host, \(\Psi_{a_j}\) and \(\Psi_{\bar{b}_{j}}\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# own random bits
random_bits_b = np.random.randint(0, 2, m, dtype=int)
random_bits_d = np.random.randint(0, 2, (n, m), dtype=int)

# random bits received from partner
random_bits_a = np.zeros(m, dtype=int)

# qubits received by partner
# Qubits are Ψ_e_ij and Ψ_e_ij_bar
partner_qubits = np.ndarray(shape=(n, m, 2), dtype=Qubit)

# Qubits which are at the end of the protocol
# at this host. First index determines the state,
# Ψ_a_j and Ψ_b_j_bar, where the second index (1,...,m)
# should be m copies of this state.
psi_a = np.ndarray(shape=(n, m), dtype=Qubit)
psi_b_bar = np.ndarray(shape=(n, m), dtype=Qubit)

In the first step, for every random number \(d_{ij}\), two qubits are prepared; The first in the state \(\Psi_{d_{ij}}\) and the second in the state \(\Psi_{\bar{d}_{ij}}\). This two states are send to the partner. The states of the partner, from his random bits, are received and stored in partner_qubits.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
for i in range(n):
    for j in range(m):
        q1 = Qubit(host)
        q2 = Qubit(host)

        # Generate q1 as Ψ_d and
        # q2 as Ψ_d_bar
        if random_bits_d[i, j] == 0:
            # q1 is Ψ_0
            q1.rx(rot_angle)
            # q2 is Ψ_1
            q2.rx(-1.0 * rot_angle)
        else:
            # q1 is Ψ_1
            q1.rx(-1.0 * rot_angle)
            # q2 is Ψ_0
            q2.rx(rot_angle)

        # send and get q1 from our partner
        host.send_qubit(partner_id, q1, await_ack=True)
        partner_q1 = host.get_qubit(partner_id)

        # send and get q2 from our partner
        host.send_qubit(partner_id, q2, await_ack=True)
        partner_q2 = host.get_qubit(partner_id)

        partner_qubits[i, j, 0] = partner_q1
        partner_qubits[i, j, 1] = partner_q2

In the second step, a new bit, \(f_{ij}\), is generated from the random bits generated in the beginning. This bit is send to the partner and determines which of the two quantum states, which have been send to the partner earlier, is in the state \(\Psi_{b_j}\). However, the partner only knows if it is the first or second of the qubits received, but does not gain any information about the random variable \(b_j\). The partner returns the qubit in the state \(\Psi_{\bar{b}_j}\). The partner also generates such a bit, \(e_{ij}\), and the host returns the quantum state \(\Psi_{\bar{a}_j}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
for i in range(n):
    for j in range(m):
        # random bit generated from own two random bits
        f_ij = random_bits_b[j] ^ random_bits_d[i, j]

        # give partner information about this two bits
        host.send_classical(partner_id, str(f_ij))

        # get the partners generated bit of his two
        # random bits by a XOR operation
        msg = host.get_next_classical(partner_id)
        e_ij = int(msg.content)

        # dependent on this bit, send him one of the
        # qubits received. The other qubit should be
        # in the state Ψ_a_j.
        if e_ij == 0:
            host.send_qubit(partner_id, partner_qubits[i, j, 1])
            psi_a[i, j] = partner_qubits[i, j, 0]
        else:
            host.send_qubit(partner_id, partner_qubits[i, j, 0])
            psi_a[i, j] = partner_qubits[i, j, 1]

        # The partner should send the qubit Ψ_b_j_bar back.
        psi_b_bar[i, j] = host.get_qubit(partner_id, wait=10)

After this procedure, the host has m qubits of the state \(\Psi_{\bar{b}_j}\) and m qubits of \(\Psi_{a_j}\), for all j. If one of the two partners of the protocol want to cheat and manipulate the outcome of the final random bit, they first have to know the numbers chosen by their partner. However, at this point the host has a stack of quantum states from the chosen numbers of his partner, making it impossible for the partner to change its prior chosen numbers. Therefore, the two partners can now start to share their chosen random numbers and measure their stack of qubits to verify the numbers haven’t been tampered with.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
for j in range(m):
    # Send own random bits b_j to partner
    host.send_classical(partner_id, str(random_bits_b[j]))

    # Get partner base to decode her qubits
    msg = host.get_next_classical(partner_id)
    a_j = int(msg.content)

    for i in range(n):
        # Meaure in Psi_0 basis or Psi_1 basis
        # Because Partner has to tell us the right basis,
        # our measurement outcome should always be 0.
        q = psi_a[i, j]
        res = -1
        if a_j == 0:
            q.rx(-1.0 * rot_angle)
        else:
            q.rx(rot_angle)

        res = q.measure()
        # Check if all results match the random number
        # partner has shared with us.
        if res != 0:
            raise ValueError("Cheater!")

    # a_j got accepted
    random_bits_a[j] = a_j

    # Check if returned psi_b_bar is valid
    # or if partner has measured it to gain information
    # about b.
    for i in range(n):
        q = psi_b_bar[i, j]
        if 1 - random_bits_b[j] == 0:
            q.rx(-1.0 * rot_angle)
        else:
            q.rx(rot_angle)
        res = q.measure()
        if res != 0:
            raise ValueError("Cheater!")

In the last step, the final random number on which both partners can agree on is generated. The final random number is \(\left(\oplus_j a_j\right) \oplus \left(\oplus_j b_j\right)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# random number generated by singe random numbers
# of partner
randomnes_from_partner = 0
for j in range(m):
    randomnes_from_partner ^= random_bits_a[j]

# random number generated by own single random numbers
own_randomnes = 0
for j in range(m):
    own_randomnes ^= random_bits_b[j]

# concatenation of both random numbers
random_bit = randomnes_from_partner ^ own_randomnes
print("%s: random bit is %d" % (host.host_id, random_bit))
return random_bit

The full example is given below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
 import numpy as np

 from qunetsim.objects import Qubit
 from qunetsim.components import Host
 from qunetsim.components import Network
 from qunetsim.backends import EQSNBackend
 # from qunetsim.backends import CQCBackend
 # from qunetsim.backends import ProjectQBackend


 def quantum_coin_flipping(host, m, n, partner_id, rot_angle):
     """
     Quantum Coin Flipping Protocol.
     see https://arxiv.org/abs/quant-ph/9904078
     or https://wiki.veriqloud.fr/index.php?title=Quantum_Coin_Flipping

     The two quantum states we use are:
     Ψ_0 = c |0> + s |1>
     Ψ_1 = c |0> - s |1>
     where
     c = Re{e^(iΘ)}
     s = Im{e^(iΘ)}
     and Θ is given by the rot_angle.

     Own random bits are b_j and d_ij.
     Partners random variables are a_j and c_ij.

     Own shared: f_ij = b_j ^ d_ij
     Partner shared: e_ij = a_j ^ c_ij

     final own: B = ^b_j for all j
     final partner: A_tilde = ^a_j for all j

     final random bit: A_tilde ^ B
     """
     # own random bits
     random_bits_b = np.random.randint(0, 2, m, dtype=int)
     random_bits_d = np.random.randint(0, 2, (n, m), dtype=int)

     # random bits received from partner
     random_bits_a = np.zeros(m, dtype=int)

     # qubits received by partner
     # Qubits are Ψ_e_ij and Ψ_e_ij_bar
     partner_qubits = np.ndarray(shape=(n, m, 2), dtype=Qubit)

     # Qubits which are at the end of the protocol
     # at this host. First index determines the state,
     # Ψ_a_j and Ψ_b_j_bar, where the second index (1,...,m)
     # should be m copies of this state.
     psi_a = np.ndarray(shape=(n, m), dtype=Qubit)
     psi_b_bar = np.ndarray(shape=(n, m), dtype=Qubit)

     for i in range(n):
         for j in range(m):
             q1 = Qubit(host)
             q2 = Qubit(host)

             # Generate q1 as Ψ_d and
             # q2 as Ψ_d_bar
             if random_bits_d[i, j] == 0:
                 # q1 is Ψ_0
                 q1.rx(rot_angle)
                 # q2 is Ψ_1
                 q2.rx(-1.0 * rot_angle)
             else:
                 # q1 is Ψ_1
                 q1.rx(-1.0 * rot_angle)
                 # q2 is Ψ_0
                 q2.rx(rot_angle)

             # send and get q1 from our partner
             host.send_qubit(partner_id, q1, await_ack=True)
             partner_q1 = host.get_qubit(partner_id)

             # send and get q2 from our partner
             host.send_qubit(partner_id, q2, await_ack=True)
             partner_q2 = host.get_qubit(partner_id)

             partner_qubits[i, j, 0] = partner_q1
             partner_qubits[i, j, 1] = partner_q2

     for i in range(n):
         for j in range(m):
             # random bit generated from own two random bits
             f_ij = random_bits_b[j] ^ random_bits_d[i, j]

             # give partner information about this two bits
             host.send_classical(partner_id, str(f_ij))

             # get the partners generated bit of his two
             # random bits by a XOR operation
             msg = host.get_next_classical(partner_id)
             e_ij = int(msg.content)

             # dependent on this bit, send him one of the
             # qubits received. The other qubit should be
             # in the state Ψ_a_j.
             if e_ij == 0:
                 host.send_qubit(partner_id, partner_qubits[i, j, 1])
                 psi_a[i, j] = partner_qubits[i, j, 0]
             else:
                 host.send_qubit(partner_id, partner_qubits[i, j, 0])
                 psi_a[i, j] = partner_qubits[i, j, 1]

             # The partner should send the qubit Ψ_b_j_bar back.
             psi_b_bar[i, j] = host.get_qubit(partner_id, wait=10)

     for j in range(m):
         # Send own random bits b_j to partner
         host.send_classical(partner_id, str(random_bits_b[j]))

         # Get partner base to decode her qubits
         msg = host.get_next_classical(partner_id)
         a_j = int(msg.content)

         for i in range(n):
             # Meaure in Psi_0 basis or Psi_1 basis
             # Because Partner has to tell us the right basis,
             # our measurement outcome should always be 0.
             q = psi_a[i, j]
             res = -1
             if a_j == 0:
                 q.rx(-1.0 * rot_angle)
             else:
                 q.rx(rot_angle)

             res = q.measure()
             # Check if all results match the random number
             # partner has shared with us.
             if res != 0:
                 raise ValueError("Cheater!")

         # a_j got accepted
         random_bits_a[j] = a_j

         # Check if returned psi_b_bar is valid
         for i in range(n):
             q = psi_b_bar[i, j]
             if 1 - random_bits_b[j] == 0:
                 q.rx(-1.0 * rot_angle)
             else:
                 q.rx(rot_angle)
             res = q.measure()
             if res != 0:
                 raise ValueError("Cheater!")

     # random number generated by singe random numbers
     # of partner
     randomnes_from_partner = 0
     for j in range(m):
         randomnes_from_partner ^= random_bits_a[j]

     # random number generated by own single random numbers
     own_randomnes = 0
     for j in range(m):
         own_randomnes ^= random_bits_b[j]

     # concatenation of both random numbers
     random_bit = randomnes_from_partner ^ own_randomnes
     print("%s: random bit is %d" % (host.host_id, random_bit))
     return random_bit


 def main():
     network = Network.get_instance()

     # backend = ProjectQBackend()
     # backend = CQCBackend()
     backend = EQSNBackend()

     nodes = ['A', 'B']
     network.delay = 0.1
     network.start(nodes, backend)

     host_A = Host('A', backend)
     host_A.add_connection('B')
     host_A.delay = 0
     host_A.start()

     host_B = Host('B', backend)
     host_B.add_connection('A')
     host_B.delay = 0
     host_B.start()

     network.add_host(host_A)
     network.add_host(host_B)

     m = 2
     n = 4
     rot_angle = np.pi/9

     t1 = host_A.run_protocol(quantum_coin_flipping,
                             arguments=(m, n, host_B.host_id, rot_angle))
     t2 = host_B.run_protocol(quantum_coin_flipping,
                             arguments=(m, n, host_A.host_id, rot_angle))

     t1.join()
     t2.join()

     network.stop(True)

     if __name__ == "__main__":
         main()