QAA,Grover,QAEを勉強する。

量子振幅推定(Quantum Amplitude Estimation)

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

• 論文
  Practical numerical integration on NISQ devices

• 記事/HP
  [Grover の検索アルゴリズム と Quantum Amplitude Amplification/Estimation]
  (https://whyitsso.net/physics/quantum_mechanics/AA_AE_Grover.html)
  量子アルゴリズムの基本：Groverのアルゴリズムの確認
  反復法による量子振幅推定

• qiskit tutorial
  Grover のアルゴリズムと振幅増幅

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)**と呼ばれています。
（ただし回転させすぎると減少に転ずることに注意してください。以下のように、周期性があります。)

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

実装してみる

qiskit.aquaでQAAをやってみます。QAEは別記事の予定です。
問題設定は、
Practical numerical integration on NISQ devices
を使っています。

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

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)

初期状態は以下のような回路でセットします。
（これは問題によって構造が変わるので、気にしなくて良いです）

なお、初期位相$\theta = \pi/6$ になっています。

オラクル（Groverアルゴリズムにおける解状態の符号反転）は、以下のように簡単です。（補助量子ビットの恩恵）

オラクルを用いて、ゲート$Q$を作ります。

最後に、初期状態生成回路とくっつけます。

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

# 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')

確かに振幅が上がったり下がったりしています。
初期位相は$\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で情報を抜いてしまおう精神。