Tech Blog

勉強したことをまとめます。

木構造を使った振幅エンコーディング

はじめに

 前回、振幅エンコーディングの手順を示した。その手法では、確率(前回の式(4))

{\displaystyle
\begin{align*}
P=\dfrac{1}{N}\sum_{i=0}^{N-1}v_i^2
\end{align*}
}


が小さいとき、何度も測定を繰り返す必要があり効率が悪くなる。今回は、エンコーディングを行う過程の中に「測定」を含まない手法(木構造を用いた振幅エンコーディング)を説明する。

木構造

 8次元ベクトル{\bf v}=(v_0,\cdots,v_7)を振幅に埋め込んだ状態

{\displaystyle
\begin{align}
|\psi\rangle
&=\sum_{k=0}^{7}v_k|k\rangle\\
&=v_0|000\rangle+v_1|001\rangle+v_2|010\rangle+v_3|011\rangle+v_4|100\rangle+v_5|101\rangle+v_6|110\rangle+v_7|111\rangle
\label{eq0}
\end{align}
}


を作ることを目的とする。規格化条件

{\displaystyle
\begin{align*}
\sum_{k=0}^{7}|v_k|^2=1
\end{align*}
}


は満たされているとする。v_kは実数値である。8次元ベクトルを埋め込むのに必要な最小の量子ビット数は3であるので、ここでは3個の量子ビットを用いる。

   最初に以下に示す木構造を作る。

図1. 木構造のデータ
次に、3個の量子ビットからなるAレジスタm個の量子ビットからなるBレジスタを用意する。すべてのビットは0に初期化されている。

{\displaystyle
\begin{align*}
|000\rangle_A\;|0\cdots0\rangle_B
\end{align*}
}


Aレジスタをアドレスとして扱い、木構造からデータを取り出し、Bレジスタに入れる仕組みを作る(実現の仕方はここでは言及しない)。取り出す手順は以下の通り。

  1. Aレジスタの値aを読む。
  2. Node aの左側の子ノードの値を、Bレジスタに基底エンコーディングにより読み込む。

たとえば、最初の操作ではAレジスタの最初のビットの値をアドレスaとする。a=0の場合、BレジスタにNode 00の値を読み込む。a=1の場合、BレジスタにNode 10の値を読み込む。次の操作ではAレジスタの最初の2ビットをアドレスとして扱い同じことを繰り返す。a=00の場合、BレジスタにNode 000の値を読み込む。a=01の場合、BレジスタにNode 010の値を読み込む。

 以下具体的に木構造を用いた振幅エンコーディングの手順を示す。

振幅エンコーディング

1. 初期状態

 上に述べた初期状態を作る。

{\displaystyle
\begin{align*}
|\psi_1\rangle=|000\rangle_A\;|0\cdots0\rangle_B
\end{align*}
}


2. Node 0のデータ取り出し

 rootノードの左側の子ノードNode 0からデータを取り出す。この操作は上の手順を踏まない例外的な操作である。

{\displaystyle
\begin{align*}
|\psi_2\rangle=|000\rangle_A\;|b(V_1^2)\rangle_B
\end{align*}
}


ここで

{\displaystyle
\begin{align*}
V_1^2=\sum_{i=0}^{3}v_i^2
\end{align*}
}


b(x)xの2進数表記を表す(前回と同じ)。

3. 算術演算

 Cレジスタを追加して、ここにBレジスタの値V^2を引数とする関数の値 f(V_1^2)=\dfrac{1}{\pi}\cos^{-1}{V_1} を入力する。

{\displaystyle
\begin{align*}
|\psi_3\rangle
&=
|000\rangle_A\;|b(V_1^2)\rangle_B\;|b(\dfrac{1}{\pi}\cos^{-1}{V_1})\rangle_C \\
&=
|000\rangle_A\;|b(V_1^2)\rangle_B\;|a_0\cdots a_{m-1}\rangle_C
\end{align*}
}


2行目の式は、Cレジスタ内の値を2進数で書いたものである。詳細は前回の解説にある。

4. 回転ゲートの適用

 Aレジスタの最初のビットを明示すると

{\displaystyle
\begin{align*}
|\psi_3\rangle=
|0\rangle_A\;|00\rangle_A\;|b(V_1^2)\rangle_B\;|a_0\cdots a_{m-1}\rangle_C \\
\end{align*}
}


となる。Cレジスタの各ビットを制御ビットにして、Aレジスタの最初のビットにR_y(\pi 2^{-k})を作用させる。

{\displaystyle
\begin{align*}
|\psi_4\rangle=
\left(V_1|0\rangle_A+\sqrt{1-V_1^2}|1\rangle_A\right)
\;|00\rangle_A\;|b(V_1^2)\rangle_B\;|a_0\cdots a_{m-1}\rangle_C
\end{align*}
}


ここで

{\displaystyle
\begin{align*}
V_1&=\sqrt{\sum_{i=0}^3 v_i^2}\\
\sqrt{1-V_1^2}&=\sqrt{\sum_{i=4}^7 v_i^2}
\end{align*}
}


である。|\psi_4\rangleを得るまでの計算の詳細は、前回の解説に記載してある。

5. B,Cレジスタの初期化

 B,Cレジスタに逆演算を施して初期化する。

{\displaystyle
\begin{align}
|\psi_5\rangle
&=
\left(V_1|0\rangle_A+\sqrt{1-V_1^2}|1\rangle_A\right)
\;|00\rangle_A\;|0\rangle_B\;|0\rangle_C \nonumber \\
&=
V_1|0\rangle_A\;|00\rangle_A\;|0\rangle_B\;|0\rangle_C
+\sqrt{1-V_1^2}|1\rangle_A\;|00\rangle_A\;|0\rangle_B\;|0\rangle_C
\label{eq1}
\end{align}
}


6. Node 00のデータの取り出し

 式(\ref{eq1})の第1項を考える。Aレジスタの最初のビット0をアドレスとして、木構造からNode 0の左側の子ノードNode 00の値を取り出しBレジスタに入れる。

{\displaystyle
\begin{align*}
|\psi_6\rangle
=
V_1|0\rangle_A\;|00\rangle_A\;|b(V_2^2)\rangle_B\;|0\rangle_C
\end{align*}
}


ここで

{\displaystyle
\begin{align*}
V_2^2=\dfrac{v_0^2+v_1^2}{P}
\end{align*}
}


である。

7. Node 10のデータの取り出し

 式(\ref{eq1})の第2項を考える。Aレジスタの最初のビット1をアドレスとして、木構造からNode 1の左側の子ノードNode 10の値を取り出しBレジスタに入れる。

{\displaystyle
\begin{align*}
|\psi_7\rangle
=
\sqrt{1-V_1^2}|1\rangle_A\;|00\rangle_A\;|b(V_3^2)\rangle_B\;|0\rangle_C
\end{align*}
}


ここで

{\displaystyle
\begin{align*}
V_3^2=\dfrac{v_4^2+v_5^2}{Q}
\end{align*}
}


である。

8. Node 00とNode 10のデータを取り出した結果

 |\psi_6\rangle|\psi_7\rangleを合わせて

{\displaystyle
\begin{align*}
|\psi_8\rangle
=
V_1|0\rangle_A\;|00\rangle_A\;|b(V_2^2)\rangle_B\;|0\rangle_C+
\sqrt{1-V_1^2}|1\rangle_A\;|00\rangle_A\;|b(V_3^2)\rangle_B\;|0\rangle_C
\end{align*}
}


9. 算術演算と初期化

 |\psi_8\rangleに以下の操作を行う。

  1. 先と同様にBレジスタの値を用いた算術演算を行いCレジスタに値を入れる。
  2. Cレジスタ内の各ビットを制御ビットとして、回転ゲートをAレジスタの2つ目のビットに施す。
  3. B,Cレジスタに逆演算を施し初期化する。

これらを行うと以下を得る。

{\displaystyle
\begin{align*}
|\psi_9\rangle
&=\left(
V_1V_2|00\rangle_A\;|0\rangle_A+
V_1\sqrt{1-V_2^2}|01\rangle_A\;|0\rangle_A+
\sqrt{1-V_1^2}V_3|10\rangle_A\;|0\rangle_A+
\sqrt{1-V_1^2}\sqrt{1-V_3^2}|11\rangle_A\;|0\rangle_A\right)\\
&&\hspace{10cm}\otimes
\;|0\rangle_B\;|0\rangle_C\\
&=
\left(
\sqrt{v_0^2+v_1^2}|00\rangle_A\;|0\rangle_A+
\sqrt{v_2^2+v_3^2}|01\rangle_A\;|0\rangle_A+
\sqrt{v_4^2+v_5^2}|10\rangle_A\;|0\rangle_A+
\sqrt{v_6^2+v_7^2}|11\rangle_A\;|0\rangle_A\right)\\
&\hspace{10cm}\otimes
\;|0\rangle_B\;|0\rangle_C
\end{align*}
}


10. 最後のステップ

 Aレジスタの最初の2つのビットをアドレスとして木構造からデータを取り出し、Bレジスタに入れる。たとえば、最初の2つのビットが00のとき、Node 00の左側の子ノードNode 000の値を取り出す。算術演算など同様な計算を繰り返すと次の状態を得る。

{\displaystyle
\begin{align*}
|\psi_{10}\rangle&=
\left(
\sqrt{v_0^2}|000\rangle_A+
\sqrt{v_1^2}|001\rangle_A+
\sqrt{v_2^2}|010\rangle_A+
\sqrt{v_3^2}|011\rangle_A+
\sqrt{v_4^2}|100\rangle_A
\right.\\
&\hspace{5cm}+
\left.
\sqrt{v_5^2}|101\rangle_A+
\sqrt{v_6^2}|110\rangle_A+
\sqrt{v_7^2}|111\rangle_A
\right)\otimes
|0\rangle_B\;|0\rangle_C
\end{align*}
}


一番深いノードに格納してあるv_kの符号も取り出して根号を外す。

{\displaystyle
\begin{align*}
|\psi_{10}\rangle&=
\bigl(
v_0|000\rangle_A+
v_1|001\rangle_A+
v_2|010\rangle_A+
v_3|011\rangle_A+
v_4|100\rangle_A
\bigr.\\
&\hspace{5cm}+
\bigl.
v_5|101\rangle_A+
v_6|110\rangle_A+
v_7|111\rangle_A
\bigr)\otimes
|0\rangle_B\;|0\rangle_C
\end{align*}
}


目的とする式(\ref{eq0})が得られた。

まとめ

 今回は木構造を利用した振幅エンコーディングを説明した。N次元ベクトル{\bf v}=(v_0\cdots v_{N-1})のとき、\log_2{N}多項式のオーダでエンコーディングを行うことができる。前回の方法は、エンコーディング過程に測定行為が含まれており、場合によっては効率が悪くなる欠点があった。

参考文献