データセットをオラクルと回路として実装するには？

データセットをオラクルと回路として実装するには？

量子アルゴリズムでは、古典的なデータセットを通常のデータベースにおける表のような意味で量子コンピュータに読み込むことは、ふつうありません。代わりに、データはオラクルを通じて公開されます。オラクルとは、アルゴリズムから問い合わせることのできる可逆な操作です。回路としての実装は、そのオラクルがどの問いに答える必要があるかによって決まります。

よく使われる形は次のものです。

\[O_f: |xrangle |yrangle mapsto |xrangle |y oplus f(x)rangle,\]

ここで x はインデックスまたはキー、y はターゲットレジスタ、f(x) は x に対応するデータ値またはラベルです。f(x) が 1 ビットなら、ターゲットレジスタは 1 量子ビットです。f(x) が m ビットの値なら、ターゲットレジスタは m 量子ビットを持ち、XOR はビットごとに行われます。

もう一つよく使われる形は、位相オラクルです。

\[O_f: |xrangle mapsto (-1)^{f(x)} |xrangle.\]

位相オラクルは通常、ターゲット量子ビットを |-rangle = (|0rangle - |1rangle)/sqrt{2} に準備し、位相キックバックを使うことでビットオラクルから得られます。

例：小さな二値データセット

古典的なデータセットが次のものだとします。

| index x | value f(x) |
| --- | --- |
| 00 | 0 |
| 01 | 1 |
| 10 | 1 |
| 11 | 0 |

これは XOR 関数です。

\[f(x_1,x_0)=x_1 oplus x_0.\]

ビットオラクルは次のように実装できます。

\[|x_1x_0rangle |yrangle mapsto |x_1x_0rangle |y oplus x_1 oplus x_0rangle.\]

回路は単純に 2 つの CNOT ゲートです。一つは x_1 を制御、もう一つは x_0 を制御とし、どちらも y をターゲットにします。

x1: ──■──────
      │
x0: ──┼──■───
      │  │
y : ──X──X───

これは、各 CNOT が制御ビットが 1 のときにターゲットを反転するために機能します。ターゲットはインデックス内の各 1 ビットにつき一度反転されるので、結果は 2 つのインデックスビットのパリティになります。

有限ルックアップテーブルの一般的な方法

任意の有限テーブルに対する直接的な構成は次の通りです。

  1. すべての行をアドレス指定するのに十分な n 量子ビットを、インデックスレジスタに使う。
  2. 各値を格納するのに十分な m 量子ビットを、出力レジスタに使う。
  3. 出力ビット j が 1 である各行 x = a について、出力量子ビット j をターゲットとし、インデックスレジスタが a に一致することを制御条件とする多重制御 NOT ゲートを追加する。
  4. ある制御が 0 に一致しなければならない場合は、その制御線を多重制御操作の前後で X ゲートで挟む。

たとえば、テーブルに次の行があるとします。

x = 101, f(x) = 011

この場合、オラクルはインデックスが 101 のときに下位 2 つの出力ビットを反転しなければなりません。制御条件は x2 = 1、x1 = 0、x0 = 1 です。0 の制御は、x1 に X を適用し、通常の全ビットが 1 であることを条件にした制御操作を使い、その後で再び x1 に X を適用することで処理します。

擬似コードでは次のようになります。

for each row a in table:
    for each output bit j where f(a)[j] == 1:
        flip index qubits whose required control value is 0
        apply multi-controlled X from all index qubits to output[j]
        flip those index qubits back

この構成は理解しやすく検証もしやすい一方で、常に効率的とは限りません。N 行と m 個の出力ビットを持つテーブルでは、ターゲットのデバイスまたはシミュレータがサポートする基本ゲート集合へ分解する前の段階で、最大 N * m 個の多重制御ゲートが必要になることがあります。

可逆性が重要

量子オラクルはユニタリでなければならないため、単純にデータを消去したり上書きしたりすることはできません。通常のオラクルが XOR によって書き込むのはこのためです。

\[|xrangle |yrangle mapsto |xrangle |y oplus f(x)rangle.\]

アルゴリズムが一時的な作業領域を必要とする場合は、値を補助レジスタに計算し、それを使ってから、同じ回路を逆向きに実行してアンコンピュートします。これにより、答えのレジスタと作業用量子ビットの間に不要なエンタングルメントが残るのを防げます。

標準的なパターンは次の通りです。

compute f(x) into work register
use f(x)
uncompute f(x) by applying the inverse circuit

X、CNOT、Toffoli、多重制御 X ゲートから作られた古典的な可逆回路では、逆回路はしばしば同じゲートを逆順に並べたものになります。

データ読み込みはオラクルとは異なる

ときどき、次のようにデータを含む量子状態を準備する回路を求める人がいます。

\[sum_x d_x |xrangle.\]

これは状態準備であり、ルックアップオラクルとは同じではありません。任意のデータに対する状態準備は高コストになり得ます。振幅を正規化し、回転によって符号化しなければならないためです。ルックアップオラクルは「f(x) は何か？」という形の問い合わせに答える一方、状態準備はデータを振幅として持つ重ね合わせを作ります。

適切な実装はアルゴリズムによって異なります。

  • Grover 探索では、よいインデックスをマークする位相オラクルが必要になることが多い。
  • 算術アルゴリズムでは、f(x) を計算する可逆回路が必要になることが多い。
  • 振幅エンコーディングでは、状態準備回路または QRAM 的な仮定が必要になる。
  • 小規模なデモでは、直接的なルックアップテーブル回路で通常は十分である。

実用的な確認事項

小さなオラクルでは、より大きなアルゴリズムの中で使う前に真理値表を検証してください。単純で再現可能な確認方法は、すべての計算基底入力をシミュレートし、出力レジスタが y XOR f(x) になることを確認することです。

チェックリストは次の通りです。

  1. フレームワークで使われているビット順を確認する。Qiskit、Cirq、その他のツールでは、量子ビットやビット列の表示順が異なる場合がある。
  2. すべてのインデックス値 x をテストする。
  3. 出力レジスタをゼロ値と非ゼロ値の両方に初期化してテストする。オラクルは上書きではなく XOR するべきだからである。
  4. 補助量子ビットを使う場合は、アンコンピュート後にそれらが |0rangle に戻っていることを確認する。
  5. 回路をバックエンドの基底ゲートに分解し、深さとゲート数を調べる。

小さな静的データセットでは、直接的な多重制御ゲートの方法が最も明快な実装です。より大きな構造化データセットでは、可逆な算術と論理を使って関数を代数的に実装する方がよいでしょう。非常に大きな非構造化データでは、オラクル構成のコストはアルゴリズムモデルの一部であり、「オラクル」という言葉の背後に隠すべきではありません。

Leave a Reply