QISkit ドイチ･ジョサのアルゴリズム

1. はじめに
参考文献2)では，2ビットのドイチ･ジョサのアルゴリズムが紹介されている．本報告では，アルゴリズムの定式化について説明するとともに，4ビットの場合（拡張は可能）についてプログラムを作成したので報告する．
 
2.問題設定
1)ドイチ･ジョサのアルゴリズムの定式化
2)2ビット，4ビットのドイチ･ジョサのアルゴリズムの作成
3)解析システム
　　RaspberryPi4＋Python＋QISkit
3. ドイチ･ジョサのアルゴリズム
参考文献1),2),3)他を参考にして纏めておく．
3.1目的
ビット列を入力として受け取り，0 または1のいずれかを返す以下のようなブール関数fがあるとき，
f({x0,x1,x2,...})→0または1（ここで，xnは0または1）
このブール関数の特性は，分布型か定値型かのどちらかである．定値型の場合は，任意の入力に対してすべて0またはすべて1を返しますが，分布型の場合は、半分の入力に対して0を返し、残りの半分の入力には1を返します．問題は，与えられた関数が分布型か定値型かを判断することである．
ドイチ-ジョサ問題は、1ビットであるドイチ問題のnビットへの拡張である．
3.1 定式化
ドイチ-ジョサのアルゴリズムの一般的な回路を図1に示す．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2010670/a1ea531d-3ec5-475b-2bc5-8d5d07b35a81.png)

　　　　　図1 ドイチ-ジョサのアルゴリズムの一般的な回路

　ステップ1,2,3での出力を，ψ1，ψ2，ψ3とする．
　ステップ1出力はステップ0をH変換の公式を利用して変換すると下記となる．
　　　 ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2010670/ec2d1c2c-1a9f-8003-a255-191cc18d43d2.png)
　ステップ2出力はステップ1出力にオラクルを加えると下記となる．
　　　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2010670/fb18eb8e-c00a-3da4-f000-4ac6baebd68f.png)
　ステップ3出力はステップ2出力をアダマール変換し下記となる．
　　　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2010670/0c07ecc7-86bb-4dd6-867d-f019fc27669a.png) 
　最後の式変形の参考に2ビットの場合の変形例を下記に示しておく．
　　 ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2010670/6b5735b9-990f-0bdb-a1d5-da3a9c027c27.png)

3.2 計算例2ﾋﾞｯﾄ
　3.1の計算例として2ﾋﾞｯﾄの場合を下記に示しておく．
 　　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2010670/d00aee83-4f4d-29c4-c896-86e1bb124772.png)
4. QISkitによるプログラム作成
　2ビットのドイチ･ジョサのアルゴリズムは下記の通り．
(1)ライブラリのインポート
import numpy as np
from qiskit import IBMQ, Aer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, assemble, transpile
from qiskit.visualization import plot_histogram
(2)オラクル作成
　与えられたb_strに従って制御not回路（cx）を構成．

def dj_oracle(n, b_str):
    oracle_qc = QuantumCircuit(n+1)  
    print(b_str)   
    for qubit in range(len(b_str)):
            print("str=",b_str[qubit])
            if b_str[n-1-qubit] == '1':
                oracle_qc.cx(qubit, n)          
    print(oracle_qc.draw()) 
    oracle_gate = oracle_qc.to_gate()
    oracle_gate.name = "Oracle" # To show when we display the circuit
    return oracle_gate
(3)ドイチ･ジョサのアルゴリズムの実行
def dj_algorithm(oracle, n):
    dj_circuit = QuantumCircuit(n+1, n)
    # Set up the output qubit:
    dj_circuit.x(n)
    dj_circuit.h(n)
    # And set up the input register:
    for qubit in range(n):
        dj_circuit.h(qubit)
    # Let's append the oracle gate to our circuit:
    dj_circuit.append(oracle, range(n+1))
    # Finally, perform the H-gates again:
    for qubit in range(n):
        dj_circuit.h(qubit)     
    return dj_circuit
(4)メイン部
　nは変更可能
n = 2
　　オラクル設定
oracle_gate = dj_oracle(n, "10")
dj_circuit = dj_algorithm(oracle_gate, n)
print(dj_circuit.draw())
(5)シミュレーション実行
for i in range(n):
    dj_circuit.measure(i, i)
    
aer_sim = Aer.get_backend('aer_simulator')
transpiled_dj_circuit = transpile(dj_circuit, aer_sim)
qobj = assemble(transpiled_dj_circuit)
results = aer_sim.run(qobj).result()
answer = results.get_counts()
fig=plot_histogram(answer)
fig.show()
　図2に計算結果を示す．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2010670/975a29af-ef56-b1c9-fd7c-2d31d4a7034e.png)
　　　　図2 2ビットのドイチ･ジョサのアルゴリズム計算結果

[参考]
コメントのない実行ファイル（4ビット）を添付する．

```
# initialization
import numpy as np
from qiskit import IBMQ, Aer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, assemble, transpile
from qiskit.visualization import plot_histogram

def dj_oracle(n, b_str):
    oracle_qc = QuantumCircuit(n+1)  
    print(b_str)
    
    for qubit in range(len(b_str)):
            print("str=",b_str[qubit])
            if b_str[n-1-qubit] == '1':
                oracle_qc.cx(qubit, n)          
    print(oracle_qc.draw()) 
    
    oracle_gate = oracle_qc.to_gate()
    oracle_gate.name = "Oracle" # To show when we display the circuit
    return oracle_gate

def dj_algorithm(oracle, n):
    dj_circuit = QuantumCircuit(n+1, n)
    # Set up the output qubit:
    dj_circuit.x(n)
    dj_circuit.h(n)
    # And set up the input register:
    for qubit in range(n):
        dj_circuit.h(qubit)
    # Let's append the oracle gate to our circuit:
    dj_circuit.append(oracle, range(n+1))
    # Finally, perform the H-gates again:
    for qubit in range(n):
        dj_circuit.h(qubit)     
    return dj_circuit

n = 4
oracle_gate = dj_oracle(n, "1010")
dj_circuit = dj_algorithm(oracle_gate, n)
print(dj_circuit.draw())

for i in range(n):
    dj_circuit.measure(i, i)
    
aer_sim = Aer.get_backend('aer_simulator')
transpiled_dj_circuit = transpile(dj_circuit, aer_sim)
qobj = assemble(transpiled_dj_circuit)
results = aer_sim.run(qobj).result()
answer = results.get_counts()
fig=plot_histogram(answer,figsize = (12,7))
fig.show()
```

計算結果を図3に示す．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2010670/af701fdf-0ba3-31c7-5a20-7070d6080489.png) 
　　　　　　図3 4ビットのドイチ･ジョサのアルゴリズム計算結果

５．おわりに
　ドイチ･ジョサのアルゴリズムの定式化を行うとともに，2bit，4bitデータ対象としたアルゴリズムプログラムを作成した．

参考文献
(1)竹内繁樹：量子コンピュータ（BLUEBACKS）
(2)中山茂：Python量子プログラミング入門（Gaia教育シリーズ8）
(3)Qiskitを使った量子計算の学習：ドイチ-ジョサのアルゴリズム