QAA,Grover,QAEを勉強する。

# 量子振幅推定(Quantum Amplitude Estimation)
 量子振幅推定(Quantum Amplitude Estimation :QAE)は、量子ゲートコンピュータのアルゴリズムにおいて極めて重要なものの１つです。
ただ、中級レベル？のアルゴリズムなので、理解がちょっと難しいです。


- 論文
[Practical numerical integration on NISQ devices](https://arxiv.org/abs/2004.05739)

- 記事/HP
[Grover の検索アルゴリズム と Quantum Amplitude Amplification/Estimation]
(https://whyitsso.net/physics/quantum_mechanics/AA_AE_Grover.html)
[量子アルゴリズムの基本：Groverのアルゴリズムの確認](https://qiita.com/SamN/items/0d021e5a81260b6d5def)
[反復法による量子振幅推定](https://jijtech.hatenablog.com/entry/2020/08/19/064954)

- qiskit tutorial
[Grover のアルゴリズムと振幅増幅](https://qiskit.org/documentation/locale/ja_JP/tutorials/algorithms/07_grover.html)

# QAE、QAA、Groverのアルゴリズムを整理する

QAEは、QAA及びGroverのアルゴリズムと深い関係があります。この関係性や用途の違いが度々わからなくなるので、整理しておきます。

- Quantum amplitude amplification (QAA)

求めたい問題の解に相当する状態 (これをgood state とか solutionとも呼ぶ)$|\psi_{1} \rangle$と、解ではない状態(bad state)$|\psi_{0} \rangle$を考えます。$|\psi_{0} \rangle$ や$|\psi_{1} \rangle$は1量子ビット状態とは限りません。$|\psi_{0,1} \rangle$は正規直交とします。
我々は、bad state と　good state の”和”でかけるようなうまい初期状態$|\psi \rangle$を（もちろん既知の方法で）準備できるとします。


$|\psi \rangle = \cos\theta|\psi_{0} \rangle + e^{i\phi}\sin\theta|\psi_{1} \rangle$


と書き下すことが出来ます。イメージとしては、$(|\psi_{0} \rangle$,$|\psi_{1} \rangle)$ 平面上で偏角$\theta$のベクトルだということです。
このような状態があるとき、偏角を$2\theta$回す回転ゲート$Q$を作る方法が知られています。
($Q$をかけるたびに、$\theta \to 3\theta \to 5\theta \to....$ と遷移します)

$\theta$が変化するということは、解状態（および非解状態)の振幅が変化します。
適当なところで回転を止めれば、解状態の振幅が$1$で非解状態の振幅が$0$という状況を作れます。
これを測定すれば、解状態が得られます。

上記の手続きは、振幅を増幅させているとも取れるので、 **Quantum amplitude amplification (QAA)**と呼ばれています。
（ただし回転させすぎると減少に転ずることに注意してください。以下のように、周期性があります。)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/878664/3eca0211-c897-7fed-d9a5-ae1d9c780887.png)

QAAにおいて、初期状態は当然自分が用意しないといけません。
更に、初期偏角$\theta$も既知でないといけません。(これが分からないと、何回目の$Q$で増幅を止めたら良いのかわかりません)

結構制約が多いことに注意しましょう。

- Groverのアルゴリズム

Groverは、QAAの特別な場合です。
QAAにおいて、初期状態がアダマールゲートによる均等重ね合わせである場合をGroverと呼んでいます。

- Quantum Amplitude Estimation (QAE)

QAEは、QAAで使うゲート$Q$とQPE(Quantum Phase Estimation) を組み合わせた発展的アルゴリズムです。
QAEは、ゲート$Q$を用いますが、振幅増幅が目的ではありません。
QAEでは、初期状態の偏角$\theta$、つまり**初期状態に含まれる解状態の重み$\sin\theta$が未知である状況**を扱います。
$Q$とは、初期状態の偏角を$\theta$としたときに、その偏角を$2\theta$回す回転ゲートのようなイメージでした。
実は、ここから$Q$の固有値の位相は、$2\theta$に等しいという性質が導かれます。
よって、ゲート$Q$が用意できれば、そこへQPEを適応して固有値の位相を読み出すことで$\theta$が分かります。
これで、初期状態に含まれていた解状態の重み$\sin\theta$が推定できました。
振幅を推定するので、amplitude estimation と呼ばれます。

ただ、よく考えると
**自分で準備した初期状態なのに、解状態の重み(係数$\sin\theta$)は知らない**という、一見して不思議な設定になっています。
不思議ですが、量子数値積分アルゴリズムではこのような状況が出現します。
$f(x)$はしっている(ゲートで書ける)が$ \int f(x) dx$は知らない　ということがこれに対応します。

[Practical numerical integration on NISQ devices](https://arxiv.org/abs/2004.05739)

# 実装してみる

qiskit.aquaでQAAをやってみます。QAEは別記事の予定です。
問題設定は、
[Practical numerical integration on NISQ devices](https://arxiv.org/abs/2004.05739)
を使っています。

2qubit状態から、'01'を増幅します。
ただし、「解状態とそうでない状態」を明確に（2値に）識別するために、補助量子ビットを1個つけています。
補助量子ビットが0のときは解ではなく、1のときは解であるようにしています。
結果的に、増幅されるのは '011' です。


```python
from qiskit import QuantumCircuit
from qiskit.aqua.algorithms import Grover, QPE
from qiskit.circuit.library import ZGate
from qiskit.extensions import UnitaryGate
from qiskit.circuit.add_control import add_control
from qiskit import Aer, execute
from qiskit.aqua import QuantumInstance
import numpy as np

nqubit = 3
# the state we desire to find is '011'
good_state = ['011']

# specify the oracle that marks the state '011' as a good solution
oracle = QuantumCircuit(nqubit)
oracle.z(0)

# initial state
state_preparation = QuantumCircuit(nqubit, name='State preparation')
state_preparation.h([1,2])
state_preparation.x(2)
state_preparation.ccx(2,1,0)
state_preparation.x(2)



# define Grover's algorithm
grover = Grover(oracle=oracle, good_state=good_state, state_preparation=state_preparation)
```
初期状態は以下のような回路でセットします。
（これは問題によって構造が変わるので、気にしなくて良いです）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/878664/1d79d92d-f55e-2cd6-2d74-b34d047e9d2f.png)
なお、初期位相$\theta = \pi/6$ になっています。

オラクル（Groverアルゴリズムにおける解状態の符号反転）は、以下のように簡単です。（補助量子ビットの恩恵）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/878664/983013e9-1580-c126-3d88-0a09bc1597ec.png)

オラクルを用いて、ゲート$Q$を作ります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/878664/40c92c7f-5f00-564c-a540-3d420906cb38.png)

最後に、初期状態生成回路とくっつけます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/878664/b62a475b-d6e0-5083-2682-4a7debf6df9e.png)


これを実行すれば増幅1回を行った後の状態が得られます。
とはいえ何度も増幅していくとどうなるかが見たいので、for文を入れて繰り返し実行します。

```python
# define QAA
Amplitude_list = []
num_iteration = range(1,21)
for k in num_iteration:
  grover = Grover(oracle=oracle, good_state=good_state,  state_preparation=state_preparation, iterations=k) # k iteration
  circ_grover = grover.construct_circuit()
  result = execute(circ_grover, backend=Aer.get_backend('statevector_simulator'), shots=shots).result()
  phi = result.get_statevector()
  Amplitude = phi[3]　#extract 011
  Amplitude_list.append(Amplitude)

import matplotlib.pyplot as plt
fig, ax = plt.subplots()
ax.set_xlabel('num of iteration')  # x軸ラベル
ax.set_ylabel('amplitude of good state')  # y軸ラベル
plt.plot(num_iteration,Amplitude_list, marker='o')

```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/878664/2aba7614-8ec1-8333-4728-df0a88864e7c.png)

確かに振幅が上がったり下がったりしています。
初期位相は$\theta = \pi/6$　なので、
1度目の実行で　$\theta = \pi/6+2*\pi/6$, $\sin\theta = 1$
2度目の実行で　$\theta = \pi/6+4*\pi/6$, $\sin\theta = 0.5$
3度目の実行で　$\theta = \pi/6+6*\pi/6$, $\sin\theta = -0.5$
4度目の実行で　$\theta = \pi/6+8*\pi/6$, $\sin\theta = -1$
のように変化しています。


Groverアルゴリズムの場合も、ほぼ同じ要領で出来ます。
-  state_preparation　の指定をやめる (ライブラリのデフォルトが均等重ね合わせです)
-  オラクルを修正する　（cczで01をctrl state とすればOKだと思います)

# 結論
QAA,Groverアルゴリズムは統一的に理解できる。
QAEは、増幅という視点をちょっと忘れて、都合のいい演算子があるからQPEで情報を抜いてしまおう精神。