量子アルゴリズム④　量子鍵配送

前回，Quantum walk をやると書きましたが，都合により今回は量子鍵配送です．
[今回使ったコードのディレクトリ](https://github.com/awlaplace/Quantum/tree/master/QKD/BB84)

## 概要

C. H. BENNETT AND G. BRASSARD (1984), 
Quanttum cryptography: Public key distribution and coin tossing, 
in Proc. IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, pp. 175-179.

量子鍵配送は盗聴を検知することができ，その内容を盗聴されることなく安全に情報を伝達できるプロトコルです．
今回はその中でも初めて提案されたBB84プロトコルをいつもどおり Qiskit Textbook に従って，実装していきます．
理論的なことはそのうちまとめます．

##量子鍵配送

i). Alice はランダムなビット列とランダムな基底を選ぶ
ii). Alice はビットと基底を使って、量子ビット列上にエンコードし、Bob に送信する
iii). Bob はランダムな基底を使って、Alice のメッセージを測定する
iv). Alice と Bob は基底を公開し、秘密鍵を共有する
v). Alice と Bob は鍵のランダムサンプリングを比較する


## 実装

今回も[Qiskit Textbook](https://qiskit.org/textbook/ch-algorithms/quantum-key-distribution.html) を参考にしています．
＊[和訳](https://qiskit.org/textbook/ja/ch-algorithms/quantum-key-distribution.html)

以下，100量子ビットで固定して seed $= 0$ とします．

```python:QKD_import.py
## 前処理
from qiskit import QuantumCircuit, Aer, transpile, assemble
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from numpy.random import randint
import numpy as np

## 100 量子ビットで固定
n = 100
## seed は 0 で固定
np.random.seed(seed=0)
```

i)

```python:QKD_step1.py
## Step 1
### Alice はランダムなビット列とランダムな基底を選ぶ

alice_bits = randint(2, size=n)
alice_bases = randint(2, size=n)
```

ii)

```python:QKD_step2.py
## Step 2
### Alice は量子ビット列上にエンコードし、Bob に送信する

def encode_message(bits, bases):
    message = []
    for i in range(n):
        qc = QuantumCircuit(1,1)
        if bases[i] == 0: # Prepare qubit in Z-basis
            if bits[i] == 0:
                pass 
            else:
                qc.x(0)
        else: # Prepare qubit in X-basis
            if bits[i] == 0:
                qc.h(0)
            else:
                qc.x(0)
                qc.h(0)
        qc.barrier()
        message.append(qc)
    return message
```

iii)

```python:QKD_step3.py
## Step 3
### Bob はランダムな基底を使って、Alice のメッセージを測定する

def measure_message(message, bases):
    backend = Aer.get_backend('aer_simulator')
    measurements = []
    for q in range(n):
        if bases[q] == 0: # measuring in Z-basis
            message[q].measure(0,0)
        if bases[q] == 1: # measuring in X-basis
            message[q].h(0)
            message[q].measure(0,0)
        aer_sim = Aer.get_backend('aer_simulator')
        qobj = assemble(message[q], shots=1, memory=True)
        result = aer_sim.run(qobj).result()
        measured_bit = int(result.get_memory()[0])
        measurements.append(measured_bit)
    return measurements
```

iv)

```python:QKD_step4.py
## Step 4
### Alice と Bob は基底を公開し、秘密鍵を共有する

def remove_garbage(a_bases, b_bases, bits):
    good_bits = []
    for q in range(n):
        if a_bases[q] == b_bases[q]:
            # If both used the same basis, add
            # this to the list of 'good' bits
            good_bits.append(bits[q])
    return good_bits
```

v)

```python:QKD_step5.py
## Step 5
### Alice と Bob は鍵のランダムサンプリングを比較する

def sample_bits(bits, selection):
    sample = []
    for i in selection:
        # use np.mod to make sure the
        # bit we sample is always in 
        # the list range
        i = np.mod(i, len(bits))
        # pop(i) removes the element of the
        # list at index 'i'
        sample.append(bits.pop(i))
    return sample
```

以上のサブルーチンを基にしたmain関数

```python:QKD_step3.py
def main(): 
    ## Step 1
    alice_bits = randint(2, size=n)
    alice_bases = randint(2, size=n)

    ## Step 2
    message = encode_message(alice_bits, alice_bases)

    ## Step 3
    bob_bases = randint(2, size=n)
    bob_results = measure_message(message, bob_bases)

    ## Step 4
    bob_key = remove_garbage(alice_bases, bob_bases, bob_results)
    alice_key = remove_garbage(alice_bases, bob_bases, alice_bits)

    ## Step 5
    sample_size = 15
    bit_selection = randint(n, size=sample_size)

    bob_sample = sample_bits(bob_key, bit_selection)
    print("  bob_sample = " + str(bob_sample))
    alice_sample = sample_bits(alice_key, bit_selection)
    print("alice_sample = "+ str(alice_sample))
```

アウトプットは次のようになります．

```
bob_sample = [0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
alice_sample = [0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
```

サンプリングが一致しているため，正しく情報を伝達できたことがわかります．

ちなみに ii) と iii) の間で Eve が次のように盗聴しようとしたとします．

```python:QKD_interception.py
## 盗聴
### Eve はランダムな基底を使って、Alice のメッセージを盗聴（測定）する
eve_bases = randint(2, size=n)
intercepted_message = measure_message(message, eve_bases)
```

このとき，最後に測定される互いの鍵のサンプリングは次のようになります．

```
bob_sample = [0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0]
alice_sample = [0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1]
```

今回はサンプリングが高い確率で一致していません．よって途中で Eve による盗聴が検知できたことになります．

## まとめ
実は，NQCの体験型人材育成コースというところに所属？していて,この間，量子鍵配送の講義があったので，これを機にスクラッチ実装をまとめてみたって感じです．

https://nqc.nict.go.jp/program/experience/

次回こそQuantum walkをやリます．