Groverのアルゴリズム

#はじめに
GroverのアルゴリズムをQiskitで実装しました．
n量子ビットの場合も実装しています．
なぐり書きなので今後修正していきます．
参考になれば嬉しいです．

# Groverのアルゴリズム
グローバーのアルゴリズムは，整列化されていないデータベースから特定のデータを探索するための量子アルゴリズムです．



# Qiskitによる実装
全体のPythonコードは以下です．

## 2量子ビットの場合
```python
import qiskit
from qiskit import QuantumCircuit, Aer, QuantumRegister, IBMQ
from qiskit.providers.aer import noise
from qiskit.tools.visualization import plot_histogram

from qiskit.ignis.mitigation.measurement import complete_meas_cal, CompleteMeasFitter
```


```python
from qiskit import Aer, execute

#状態重ね合わせ
def superposition(nqubits):
    for qubit in range(nqubits):
        qc.h(qubit)

    
#オラクル    
def oracle(nqubits):
    #qc.cz(0, 1)
    qc.x(0)
    qc.x(1)
    # マルチ制御Zゲートをかけます
    qc.h(nqubits-1)
    qc.mct(list(range(nqubits-1)), nqubits-1)  # マルチ制御トフォリ
    qc.h(nqubits-1)
    qc.x(0)
    qc.x(1)

    
def diffuser(nqubits):
    for qubit in range(nqubits):
        qc.h(qubit)
        qc.x(qubit)
        
    # マルチ制御Zゲートをかけます
    qc.h(nqubits-1)
    qc.mct(list(range(nqubits-1)), nqubits-1)  # マルチ制御トフォリ
    qc.h(nqubits-1)
    
    for qubit in range(nqubits):
        qc.x(qubit)
        qc.h(qubit)

        
#測定
def measure(nqubits):
    for qubit in range(nqubits):
        qc.measure(qubit, qubit)
    
    
nqubits = 2
qc = QuantumCircuit(nqubits, nqubits)

superposition(nqubits)
qc.barrier(list(range(nqubits)))

for num in range(1):
    oracle(nqubits)
    qc.barrier(list(range(nqubits)))
    diffuser(nqubits)
    qc.barrier(list(range(nqubits)))

measure(nqubits)
qc.barrier(list(range(nqubits)))

    
    
qc.draw('mpl')
```

![download.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/311228/1b2516e8-e51f-1ad0-f002-d8689442b9cb.png)



```python
backend = Aer.get_backend('qasm_simulator')
results = execute(qc, backend=backend, shots=1024).result()
answer = results.get_counts()
plot_histogram(answer)
```
![download-1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/311228/cc7b0fe6-eafb-16e8-6113-f5a2d70add47.png)


## n量子ビットに拡張
```python
from qiskit import Aer, execute

#状態重ね合わせ
def superposition(nqubits):
    for qubit in range(nqubits):
        qc.h(qubit)

    
#オラクル    
def oracle(nqubits):
    #qc.cz(0, 1)
    qc.x(2)
    qc.x(0)
    # マルチ制御Zゲートをかけます
    qc.h(nqubits-1)
    qc.mct(list(range(nqubits-1)), nqubits-1)  # マルチ制御トフォリ
    qc.h(nqubits-1)
    qc.x(2)
    qc.x(0)

    
def diffuser(nqubits):
    for qubit in range(nqubits):
        qc.h(qubit)
        qc.x(qubit)
        
    # マルチ制御Zゲートをかけます
    qc.h(nqubits-1)
    qc.mct(list(range(nqubits-1)), nqubits-1)  # マルチ制御トフォリ
    qc.h(nqubits-1)
    
    for qubit in range(nqubits):
        qc.x(qubit)
        qc.h(qubit)

        
#測定
def measure(nqubits):
    for qubit in range(nqubits):
        qc.measure(qubit, qubit)
    
    
nqubits = 4
qc = QuantumCircuit(nqubits, nqubits)

superposition(nqubits)
qc.barrier(list(range(nqubits)))

for num in range(2):
    oracle(nqubits)
    qc.barrier(list(range(nqubits)))
    diffuser(nqubits)
    qc.barrier(list(range(nqubits)))

measure(nqubits)

    
qc.draw('mpl')
```


![download-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/311228/ff185115-86a6-0b4f-620c-e20067b19cd6.png)



![download-3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/311228/8c00c2cc-7e98-77b3-b826-4638dbf33bca.png)



#参考文献
L. K. Grover, “A fast quantum mechanical algorithm for database search," arXiv, 9605043, Nov. 1996.