コラム:量子ランダムアクセスメモリー (qRAM)

前項 Harrow-Hassidim-Lloyd (HHL) アルゴリズム の説明でも述べたように、量子コンピュータ上で古典データを扱う際は、そのデータを量子状態としてエンコードする必要がある。とくにバイナリデータの集まり(ベクトル)を量子状態として効率的に読み出すことは、量子機械学習などの応用において極めて重要である。本コラムでは、そうしたQuantum Random Access Memory (qRAM) について簡単に解説する。

RAM

古典コンピュータにおける random access memory (RAM) とは、メモリアドレスと対応するデータをセットとして格納し、引き出せるようにする装置である。すなわち、RAMにメモリアドレス \(i\) を与えると、バイナリデータ\(x_i\) を引き出すことができる。

\[i \quad \xrightarrow{RAM} \quad x_i\]

同様に、qRAM はあるバイナリデータ \(x_i\) のアドレス \(i\) を記述する量子ビット列 \(|i \rangle\) から、対応するデータを何らかの規則でエンコードした量子状態 \(|x_i \rangle\) を引き出せるようにする装置である。

\[| i \rangle \otimes | 0 \rangle \xrightarrow{qRAM} | i \rangle \otimes | x_i \rangle\]

とくに、メモリアドレスとデータを重ね合わせ状態として引き出せるということは、qRAMのもつべき重要な性質である。すなわちメモリアドレス状態の重ね合わせに対して、qRAMはアドレスとデータがエンタングルした次の状態を与える。

\[\frac{1}{\sqrt{N}}\sum_{i=1}^N | i \rangle \otimes | 0 \rangle \xrightarrow{qRAM} \frac{1}{\sqrt{N}}\sum_i | i \rangle \otimes | x_i \rangle\]

\(N\)はデータの件数である。

ここでの定義では、qRAMは必ずしも量子状態を常に保持する必要がないということに注意されたい。バイナリデータのアドレス達が与えられた時、効率的に上記のような重ね合わせ状態を生成する量子回路が計算され、実際に状態が出力されれば、qRAMとしての役割を果たす。

通常 qRAM はユニタリなプロセスとして実現することが仮定される。 qRAM の仕組みを実現するアーキテクチャにはとくに決まったものはなく、現在も研究途上である。 例えば、[1] などで具体的な実装方法が提案されている。

振幅エンコーディング

前項で学んだように、HHLアルゴリズムおよびそれをベースとする機械学習アルゴリズムでは、qRAM上のデータを状態としてではなく、振幅として利用したい場合がある。そのためには、qRAMから読み出したデータに対して次のような変換を行いたい。

\[\sum_{i=1}^N |i \rangle \otimes |x_i \rangle \quad \to \quad \frac{1}{\sum_i |x_i|^2} \sum_{i=1}^N x_i |i \rangle\]

この変換をユニタリ変換として効率よく実現する方法はPrakashの博士論文において提案された[2]。具体的な実現方法の解説は[3,4]に詳しい。

参考文献

[1] V. Giovannetti, S. Lloyd, and L. Maccone, “Architectures for a quantum random access memory“, Phys. Rev. A 78, 052310 (2008)
[2] Anupam Prakash. “Quantum Algorithms for Linear Algebra and Machine Learning“. PhD thesis, EECS Department, University of California, Berkeley, Dec 2014.
[3] 御手洗光祐, 京大基研量子情報スクール用ノート, https://www2.yukawa.kyoto-u.ac.jp/~qischool2019/mitaraiCTO.pdf
[4] Danial Dervovic et al. , “Quantum linear systems algorithms: a primer“, https://arxiv.org/abs/1802.08227