木構造を使った振幅エンコーディング
はじめに
前回、振幅エンコーディングの手順を示した。その手法では、確率(前回の式(4))
が小さいとき、何度も測定を繰り返す必要があり効率が悪くなる。今回は、エンコーディングを行う過程の中に「測定」を含まない手法(木構造を用いた振幅エンコーディング)を説明する。
木構造
8次元ベクトルを振幅に埋め込んだ状態
を作ることを目的とする。規格化条件
は満たされているとする。は実数値である。8次元ベクトルを埋め込むのに必要な最小の量子ビット数は3であるので、ここでは3個の量子ビットを用いる。
最初に以下に示す木構造を作る。
次に、3個の量子ビットからなるレジスタと個の量子ビットからなるレジスタを用意する。すべてのビットは0に初期化されている。
レジスタをアドレスとして扱い、木構造からデータを取り出し、レジスタに入れる仕組みを作る(実現の仕方はここでは言及しない)。取り出す手順は以下の通り。
たとえば、最初の操作ではレジスタの最初のビットの値をアドレスとする。の場合、レジスタにNode 00の値を読み込む。の場合、レジスタにNode 10の値を読み込む。次の操作ではレジスタの最初の2ビットをアドレスとして扱い同じことを繰り返す。の場合、レジスタにNode 000の値を読み込む。の場合、レジスタにNode 010の値を読み込む。
以下具体的に木構造を用いた振幅エンコーディングの手順を示す。
振幅エンコーディング
1. 初期状態
上に述べた初期状態を作る。
2. Node 0のデータ取り出し
rootノードの左側の子ノードNode 0からデータを取り出す。この操作は上の手順を踏まない例外的な操作である。
ここで
はの2進数表記を表す(前回と同じ)。
3. 算術演算
レジスタを追加して、ここにレジスタの値を引数とする関数の値 を入力する。
2行目の式は、レジスタ内の値を2進数で書いたものである。詳細は前回の解説にある。
4. 回転ゲートの適用
レジスタの最初のビットを明示すると
となる。レジスタの各ビットを制御ビットにして、レジスタの最初のビットにを作用させる。
ここで
である。を得るまでの計算の詳細は、前回の解説に記載してある。
5. レジスタの初期化
レジスタに逆演算を施して初期化する。
6. Node 00のデータの取り出し
式(\ref{eq1})の第1項を考える。レジスタの最初のビット0をアドレスとして、木構造からNode 0の左側の子ノードNode 00の値を取り出しレジスタに入れる。
ここで
である。
7. Node 10のデータの取り出し
式(\ref{eq1})の第2項を考える。レジスタの最初のビット1をアドレスとして、木構造からNode 1の左側の子ノードNode 10の値を取り出しレジスタに入れる。
ここで
である。
8. Node 00とNode 10のデータを取り出した結果
とを合わせて
9. 算術演算と初期化
に以下の操作を行う。
これらを行うと以下を得る。
10. 最後のステップ
レジスタの最初の2つのビットをアドレスとして木構造からデータを取り出し、レジスタに入れる。たとえば、最初の2つのビットが00のとき、Node 00の左側の子ノードNode 000の値を取り出す。算術演算など同様な計算を繰り返すと次の状態を得る。
一番深いノードに格納してあるの符号も取り出して根号を外す。
目的とする式(\ref{eq0})が得られた。
まとめ
今回は木構造を利用した振幅エンコーディングを説明した。次元ベクトルのとき、の多項式のオーダでエンコーディングを行うことができる。前回の方法は、エンコーディング過程に測定行為が含まれており、場合によっては効率が悪くなる欠点があった。