BB84をQiskitで実装してみた

量子コンピューターのAdvent Calendar25日目の記事になります。

量子鍵配送プロトコルの一つBB84プロトコルを、個人的に面白いなと思ったので紹介します。

# はじめに
この記事ではQiskitを利用してBB84プロトコルの性質をみていきます。準備としてQiskitのインストールは[こちら](https://qiskit.org/documentation/locale/ja/install.html)が参考になると思います。

## BB84とは
量子情報理論の一分野に量子鍵配送（QKD）があります。現在利用されている秘密鍵暗号を使ってイメージするならば、その鍵を共有する方法に該当すると考えられます。
BB84はその鍵配送のうちの一つのプロトコル名であり、BennetとBrassardにより1984年に提案されました。お二人の頭文字と年号からこのようなプロトコル名になっているみたいです。
量子鍵配送のプロトコルは他にもB92プロトコル、EPRプロトコルと呼ばれるものがあります。BB84が4つの状態を利用するのに対し、B92は2つの状態、EPRはEPR対を利用している点が異なります。

## BB84のアルゴリズムの流れ
BB84は以下のようにざっくり4つの段階に分けられます。
![Alice_Bob.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78339/ad8e7ee2-da05-60f9-3d81-e4339b5e3955.png)
（本当は④のあとに検査等あるみたいですが今回は割愛します。）

ちなみに慣例？に従いAliceとBobに登場してもらいます。後ほどEveにも登場してもらいます。

### Aliceの準備
#### 準備1 2つの2進数の生成
Aliceはまず適当な桁数の2進数を2つ作成します。例えば

```math
\begin{align}
a = 0100010111& \\
b = 1110101001& \\
{\rm count} = 9876543210&
\end{align}
```

各2進数は桁数の小さい方から番号0,1,2…と数えることにします。

#### 準備2 量子状態の生成
準備1で作成したパラメタa,bのカウントが同じ部分をペアにし（縦に並んでいるものをペアとします。）それに該当する量子状態$|Ψ\rangle_{a_ib_i}$

```math
\begin{align}
|Ψ\rangle_{00} &= |0\rangle \\
|Ψ\rangle_{10} &= |1\rangle \\
|Ψ\rangle_{01} &= (|0\rangle + |1\rangle)/\sqrt{2} = |+\rangle \\
|Ψ\rangle_{11} &= (|0\rangle - |1\rangle)/\sqrt{2} = |-\rangle \\
\end{align}
```
を作成します。先ほどのパラメタa,bを元に具体的に書くと、(うまく表示できず。。。隙間に意味はありません。)

```math
\begin{align}
{\rm count} = &9&8&7&6&5&4&3&2&1&0& \\
a = &0&1&0&0&0&1&0&1&1&1& \\
b = &1&1&1&0&1&0&1&0&0&1& \\
Ψ = &+&-&+&0&+&1&+&1&1&-&
\end{align}
```
となります。この量子状態$|Ψ\rangle_{a_ib_i}$の中に$|+\rangle$と$|-\rangle$が混ざっていることで外部からの盗聴を困難にしていることになります。

### AliceからBobへ量子状態の送信
AliceはBobへ「Aliceの準備」で作成した量子状態$|\Psi\rangle$を送信します。
具体的な伝送方法は書籍「Quantum Computation and Quantum Information」で紹介されており、IBMで実験が行われたそうです。
>D. S. Bethune and W. P. Risk. An autocompensating quantum key distribution system using polarization splitting of light
In IQEC ’98 Digest of Postdeadline Papers, pages QPD12–2, Optical Society of America, Washington, DC, 1998.
> Quantum Computation and Quantum Information  Michael A. Nieelsen & Isaac L. Chuang
![BB84.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78339/242d4879-1747-f92b-a2ed-1dd709ede2be.png)

簡単に実験概要を記載しておきます。
Bobは強いコヒーレント状態$|\alpha\rangle$を生成し、Aliceに送信します。
Aliceはそれを減衰させ単一光子にして、4つの状態の一つに光子を偏光させてBobに返します。
$|0\rangle$,$|1\rangle$が水平・垂直偏光で、$|+\rangle$,$|-\rangle$は右回り左回り偏光です。Bobは偏光子を利用しランダムな基底で測定します。

### Bobによる測定

#### 準備 1つの2進数を生成
Bobは10桁（今回Aliceが作成した桁数が10桁なので）の2進数を作成します。例えば
$$
 b' = 1110110101
$$
とします。

#### 測定
Bobは準備で作成したパラメタb'をもとにAliceから送られてきた量子状態をそれぞれ測定していきます。測定の方法は、

```math
 b'=0 \quad → Z測定 \\
 b'=1 \quad → X測定
```

これによりBobは送られてきたそれぞれの量子状態で測定値が得られます。その結果をcとすると(これも隙間に意味はありません。)

```math
\begin{align}
{\rm count} &= &9&8&7&6&5&4&3&2&1&0& \\
Ψ &= &+&-&+&0&+&1&+&1&1&-& \\
b' &= &1&1&1&0&1&1&0&1&0&1& \\
c &= &0&1&0&0&0&0&1&0&1&1& \\
\end{align}
```

となったとします。
$|Ψ\rangle$の$|+\rangle$をX測定したら0、$|-\rangle$をX測定したら1、$|0\rangle$をZ測定したら0、$|1\rangle$をZ測定したら1という性質を利用しています。$|+\rangle$や$|-\rangle$をZ測定したり、$|0\rangle$や$|1\rangle$をX測定したりすると結果は確率になるのでその部分は適当に設定しています。ここではcountの値が2,3,4のときcを適当に設定しています。

### 一致している桁の確認

Bobが測定を終わった段階で、AliceとBobは互いのパラメタb、b'を見比べます。この作業はだれに見られても問題ありません。

```math
\begin{align}
b &= 1110101001 \\
b' &= 1110110101
\end{align}
```
各桁で一致、不一致を確認し、不一致の部分を捨てることにします。
すなわちAliceならばパラメタaの各桁において、パラメタb,b'の不一致部分を削除し、Bobならばcの各桁においてb,b'の不一致部分を削除することになります。

```math
\begin{align}
b &= 1110101001 \\
b' &= 1110110101 \\
a  &= 01000\overline{1}\overline{0}\overline{1}11 \\
c  &= 01000\overline{0}\overline{1}\overline{0}11 \\
{\rm count} &= 9876543210 \\
\end{align}
```

$\overline{x}$の部分はb,b'が異なっている箇所を表しています。

よって

```math
\begin{align}
 a'  &= 0100011\\
 c'  &= 0100011
\end{align}
```

となり、確かにAliceとBobでキーを共有できていることがわかります。

パラメタb,b'の各桁は測定の方法を定義していることに注意します。
bが0ならばz測定、1ならばX測定するための準備を行い、b'で実際にどの測定を行うか決めています。aは、各測定で0、1（＋、－）になるかを決めていることになります。
bとb'が異なるとき、例えばZ測定してほしいのにX測定してしまうとすると、確率半々で結果が異なることになりますが、これは捨て去るので結局鍵を共有する際には確率による影響は出ないことになります。

## AliceとBobだけの通信
実際にどのようになっているか、Qiskitを利用して確認したいと思います。
ちなみに、量子状態の伝送はできないので、プログラム中では、量子ビットのオブジェクトをクラス間でやり取りするといったふうに模擬的に伝送を行っています。
簡単なクラス図です。AliceとBobはPersonを継承しています。継承線が消えていますが・・・
![classes.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78339/42320f09-bfc3-9703-f272-b66fbb4521d6.png)

 ベースとなる親クラスを定義します。下のプログラムでは桁数を10にしています。bnの値を変更することでいろいろな桁数を試すことができます。

```Python
class Person(object):
    
    def __init__(self):
        self.bn = 10

    # 任意の2進数を生成する。
    def generate_bit(self):
        max = int('1' * self.bn,2)
        tmp = random.randint(1, max)
        return format(tmp,'b').zfill(self.bn)
    
    # キーを生成する
    def generate_key(self,b1,b2,target):
        key = ''
        x = format(int(b1, 2)^int(b2, 2),'b').zfill(self.bn)
        for i in range(self.bn):
            if '0' == x[i]:
                key += target[i]
        return key
```

Aliceのクラスを定義します。

```Python
class Alice(Person):
    
    # 初期化
    def __init__(self):
        super().__init__()
    
    # Aliceのaを生成する (Aliceの準備 準備1 2つの2進数の生成)
    def generate_a_alice(self):
        self.a_alice = super().generate_bit()
    
    # Aliceのbを生成する (Aliceの準備 準備1 2つの2進数の生成)
    def generate_b_alice(self):
        self.b_alice = super().generate_bit()
        
    # Aliceのbを送信する (一致している桁の確認)
    def send_b_alice(self):
        return self.b_alice
    
    # Aliceが作成した量子状態を送信する make_qbit実行後でないと意味がない(AliceからBobへ量子状態の送信)
    def translate_qbit(self):
        return self.qc_alice,self.q_alice
    
    # Aliceはa,bをもとに量子状態を生成する (Aliceの準備 準備2 量子状態の生成)
    def make_qbit(self):
        # 量子回路を準備
        self.q_alice = QuantumRegister(self.bn, 'q_alice') 
        self.qc_alice = QuantumCircuit(self.q_alice)
        self.qc_alice = self.__generate_qbit(self.qc_alice,self.q_alice,self.a_alice,self.b_alice,self.bn)
        return self.qc_alice.draw(output='mpl')
    
    # デモ用
    def show_alice_a_b_for_demo(self):
        print('Alice a : ' + self.a_alice)
        print('Alice b : ' + self.b_alice)
    
    # デモ用
    def show_alice_b_for_demo(self):
        print('Alice b : ' + self.b_alice)
    
    # 量子状態を生成する
    def __generate_qbit(self,qci,q,a_alice,b_alice,bn):
        for i in range(bn):
            if '0' == a_alice[bn-1-i]:
                if '1' == b_alice[bn-1-i]:
                    # |+>
                    qci.h(q[i])
            else:
                if '0' == b_alice[bn-1-i]:
                    # |0>
                    qci.x(q[i])
                else:
                    # |->
                    qci.x(q[i])
                    qci.h(q[i])
        qci.barrier(q)
        return qci

```

Bobのクラスを定義します。

```Python

class Bob(Person):
    
    # 初期化
    def __init__(self):
        super().__init__()
    
    # Bobのbを生成する (Bobによる測定 準備 1つの2進数を生成)
    def generate_b_bob(self):
        self.b_bob = super().generate_bit()
    
    # 量子状態を受信する (AliceからBobへ量子状態の送信)
    def recieve_q_alice(self,q):
        # 量子回路を準備
        self.c_bob = ClassicalRegister(self.bn, 'c_bob')
        self.qc_bob = QuantumCircuit(self.c_bob)
        self.qc_bob = q[0] + self.qc_bob
        self.q_bob = q[1]
    
    # Bobのbを送信する (一致している桁の確認)
    def send_b_bob(self):
        return self.b_bob
    
    # Bobによる測定 (Bobによる測定 測定)
    def measure_qbit(self):
        for i in range(self.bn):
            if '0' == self.b_bob[self.bn-1-i]:
                self.__z_measure(self.qc_bob,self.q_bob[i],self.c_bob[i])
            else:
                self.__x_measure(self.qc_bob,self.q_bob[i],self.c_bob[i])
        r = execute(self.qc_bob, Aer.get_backend('qasm_simulator')).result()
        rc = r.get_counts()
        self.result_bob = random.choice(list(rc.keys()))
        return self.result_bob
    
    # デモ用
    def show_bob_b_for_demo(self):
        print('Bob b   : ' + self.b_bob)
    
    # Bobによる測定（デモ用）
    def measure_qbit_for_display_circit(self):
        for i in range(self.bn):
            if '0' == self.b_bob[self.bn-1-i]:
                self.__z_measure(self.qc_bob,self.q_bob[i],self.c_bob[i])
            else:
                self.__x_measure(self.qc_bob,self.q_bob[i],self.c_bob[i])

        return self.qc_bob.draw(output='mpl')
    
    # Bobによる測定（デモ用） measure_qbit_for_displayのあとに実行しないといけない。
    def measure_qbit_for_display_result(self):
        r = execute(self.qc_bob, Aer.get_backend('qasm_simulator')).result()
        rc = r.get_counts()
        self.result_bob = random.choice(list(rc.keys()))
        print("List of results Bob can measure")
        print(rc)
        print("Bob's measurement : " + self.result_bob)
        return plot_histogram(rc)
        
    # Z測定を行う
    def __z_measure(self,qci,q,c):
        qci.measure(q,c)
    
    # X測定を行う
    def __x_measure(self,qci,q,c):
        qci.h(q)
        qci.measure(q,c)

```
アルゴリズムに従ってAliceとBobの通信を疑似的に再現します。

```Python
from qiskit import *
from qiskit.tools.visualization import *
import random

alice = Alice()
bob = Bob()
# Aliceの準備 準備1 2つの2進数の生成
alice.generate_a_alice()
alice.generate_b_alice()
# Aliceの準備 準備2 量子状態の生成
alice.make_qbit()
# Bobによる測定 準備 1つの2進数を生成
bob.generate_b_bob()
# デモ
alice.show_alice_a_b_for_demo()
bob.show_bob_b_for_demo()
# Bobの測定
bob.recieve_q_alice(alice.translate_qbit())
print('Bob result :' + bob.measure_qbit())
# 一致している桁の確認　AliceのbとBobのbを共有する
# 一致している桁の確認　Bob側でキーを生成する
print('Bob key : ' + bob.generate_key(alice.send_b_alice(),bob.b_bob,bob.result_bob))
# 一致している桁の確認　Alice側でキーを生成する
print('Alice key : ' + alice.generate_key(bob.send_b_bob(),alice.b_alice,alice.a_alice) )

```

上記のプログラムをJupyterなどで実行してもらえると確かにAliceとBobが鍵を共有できていることが分かります。
実行結果例

```math
\begin{align}
{\rm Alice \quad a} &: 0110101000 \\
{\rm Alice \quad b} &: 0100100101 \\
{\rm Bob \quad b}   &: 0111000001 \\
{\rm Bob \quad result} &:0111101000 \\
{\rm Bob \quad key} &: 010100 \\
{\rm Alice \quad key} &: 010100 \\
\end{align}
```

## Eveがいた場合（事前漏洩があり）
BB84の作業の順番はとても重要です。Bobが測定する前に、AliceとBobがパラメタb,b'を共有してしまい、それがEveによって傍受されていたとすると、Aliceが送る量子状態は全て複製されてしまうことになります。
![Alice_Bob_Eve.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78339/f92c4f57-b7aa-a186-0552-66ba308a3ee1.png)

Eveのクラスを定義します。

```Python
class Eve(Alice,Bob):
    
    # 初期化
    def __init__(self,b_alice,b_bob):
        super().__init__()
        self.b_alice = b_alice
        self.b_bob = b_alice
        self.tmp_b_bob = b_bob
    
    # Eveが測定した値をAliceのaとする
    def set_a_alice(self,a_alice):
        self.a_alice = a_alice

```

アルゴリズムに従ってAliceとBobの通信をEveが傍受する内容を疑似的に再現します。

```Python
from qiskit import *
from qiskit.tools.visualization import *
import random

alice = Alice()
bob = Bob()
# Aliceの準備 準備1 2つの2進数の生成
alice.generate_a_alice()
alice.generate_b_alice()
# Aliceの準備 準備2 量子状態の生成
alice.make_qbit()
# Bobによる測定 準備 1つの2進数を生成
bob.generate_b_bob()
# デモ
alice.show_alice_a_b_for_demo()
bob.show_bob_b_for_demo()
# Eve登場 AliceのbとBobのbを事前に知っているものとする。(AliceのbとBobのbを間違って先に共有してしまう。)
# Eveの傍受開始
# b,b'傍受
eve = Eve(alice.send_b_alice(),bob.send_b_bob())
# 量子状態傍受
eve.recieve_q_alice(alice.translate_qbit())
# 測定
eve.set_a_alice(eve.measure_qbit())
# 複製
eve.make_qbit()
# Eve側でキーを生成する
print('Eve key : ' + eve.generate_key(eve.tmp_b_bob,eve.b_alice,eve.a_alice))
# Bobの測定
bob.recieve_q_alice(eve.translate_qbit())
bob.measure_qbit()
# Bob側でキーを生成する
print('Bob key : ' + bob.generate_key(alice.send_b_alice(),bob.b_bob,bob.result_bob))
# Alice側でキーを生成する
print('Alice key : ' + alice.generate_key(bob.send_b_bob(),alice.b_alice,alice.a_alice))

```
上記のプログラムをJupyterなどで実行してもらえると確かにAliceとBobとEveが鍵を共有できてしまっていることが分かります。
実行結果例

```math
\begin{align}
{\rm Alice \quad a} &: 0010101110\\
{\rm Alice \quad b} &: 1000010110\\
{\rm Bob \quad b}   &: 1110110110 \\
{\rm Eve \quad key} &: 0001110 \\
{\rm Bob \quad key} &: 0001110 \\
{\rm Alice \quad key} &: 0001110 \\
\end{align}
```

Eveはパラメタbと量子状態を傍受したことでAliceのパラメタaを全て分かったことになってしまいました。なのでAliceが送りたかった量子状態を複製可能となり、それをBobに送信すればBobにとってはAliceから送られてくる量子状態と違いはないことになります。上記の例ではBobもご丁寧にAliceと一緒にパラメタb'を共有しているため、EveはBobの測定を待たずにキーを取得できています。
今回はパラメタb,b'を量子状態を送信するまえにPublicで共有したことを前提としましたが、別に共有しなくてもなんらかの事象で漏洩していたりすると問題になることがわかります。

## Eveがいた場合 (事前漏洩なし)

今度はパラメタbの共有の順番を間違わないで行った場合を考えます。依然としてEveは量子状態のみを傍受出来るとします。この場合[ノー・クローニング定理](https://ja.wikipedia.org/wiki/%E9%87%8F%E5%AD%90%E8%A4%87%E8%A3%BD%E4%B8%8D%E5%8F%AF%E8%83%BD%E5%AE%9A%E7%90%86)により複製ができません。よってEveは完全なコピーを取得することができません。測定を行ってしまうと状態が変わるのでBobとAliceのキーは不一致となり二人は伝送途中で何かおかしなことが起きていると分かることになります。
![Alice_Bob_Eve2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78339/9f206496-1208-ed52-9684-e56064c7f491.png)

Eveのクラスを再度定義します。

```Python

class Eve(Alice,Bob):
    
    # 初期化
    def __init__(self):
        super().__init__()
        # Eveはaliceのbが分からないので自分で生成しないといけない、ついでにBobのbも
        self.b_alice = super().generate_bit()
        self.b_bob = super().generate_bit()
        self.tmp_b_bob = super().generate_bit()
    
    # Eveが測定した値をAliceのaとする
    def set_a_alice(self,a_alice):
        self.a_alice = a_alice
```

アルゴリズムに従ってAliceとBobの通信をEveが傍受する内容を疑似的に再現します。

```Python
from qiskit import *
from qiskit.tools.visualization import *
import random

alice = Alice()
bob = Bob()
# Aliceの準備 準備1 2つの2進数の生成
alice.generate_a_alice()
alice.generate_b_alice()
# Aliceの準備 準備2 量子状態の生成
alice.make_qbit()
# Bobによる測定 準備 1つの2進数を生成
bob.generate_b_bob()
# デモ
alice.show_alice_a_b_for_demo()
bob.show_bob_b_for_demo()
# Eveの傍受開始
eve = Eve()
# 量子状態傍受
eve.recieve_q_alice(alice.translate_qbit())
# 測定
eve.set_a_alice(eve.measure_qbit())
# 複製
eve.make_qbit()
# Bobの測定
bob.recieve_q_alice(eve.translate_qbit())
bob.measure_qbit()
# Bob側でキーを生成する
print('Bob key : ' + bob.generate_key(alice.send_b_alice(),bob.b_bob,bob.result_bob))
# Alice側でキーを生成する
print('Alice key : ' + alice.generate_key(bob.send_b_bob(),alice.b_alice,alice.a_alice))
# Eve側でキーを生成する
print('Eve key : ' + eve.generate_key(eve.tmp_b_bob,eve.b_alice,eve.a_alice))

```
上記のプログラムをJupyterなどで実行してもらえるとAliceとBobとEveが保持する鍵が異なるものになっていることが分かります。
実行結果例

```math
\begin{align}
{\rm Alice \quad a} &: 0100010001\\
{\rm Alice \quad b} &: 0000000110\\
{\rm Bob \quad b}   &: 1001000010\\
{\rm Bob \quad key} &: 1100001 \\
{\rm Alice \quad key} &: 1001001 \\
{\rm Eve \quad key} &: 1110 \\
\end{align}
```
ここではEveはAliceのパラメタbとBobのパラメタb'が分からないので適当に設定しています。そのことでAliceのキーとBobのキーが不一致となっています。
AliceとBobが定期的に鍵を見比べて不一致が目立っていないか確認すれば、ある程度は盗聴の有無を判別することが可能です。

上記の書いた内容をGitHubにあげておきました。JupyterでQiskitインストール後動かせると思います。
https://github.com/kUmezawa/BB84/blob/master/BB84.ipynb

# まとめ
- BB84は4状態を利用する量子鍵配送のプロトコルです。
- BB84では量子状態を送る前にパラメタb,b'を共有（漏洩）していると安全ではありません。

# 参考文献
1. Quantum Computation and Quantum Information  Michael A. Nieelsen & Isaac L. Chuang
2. 佐川弘幸/吉田宣章　著　『量子情報理論』
3. 西野友年　著　『今度こそわかる　量子コンピュータ』