qRAMの作り方
qRAM(Quantum Random Access Memory)を量子回路上で実装する方法を解説します。 こちらとこちらの論文をベースにエッセンスを解説し、これがあることで解ける問題の幅が広がることを紹介します。
対象とする読者
- 量子プログラミングに興味を持ち始めたばかりのエンジニア
- 量子計算に興味を持ち始めたばかりの高校生・大学生 など
前提とする知識
- 簡単な論理演算(AND, OR, NOT)が分かること
- 基本的な量子ゲート(X, CX, CCX)が分かること
バージョン情報
- Python 3.7.3
- Qiskit 0.23.1
目次
- qRAM(Quantum Random Access Memory)とは
- RAM(Random Access Memory)って何?
- 古典RAMと量子RAM(qRAM)の違い
- qRAMがあると何ができる?
- QRAMを実装するときの考え方
- QRAMの実装例
- まとめ
- 参考
qRAM(Quantum Random Access Memory)とは
定義
右辺に注目してもらえればいいのですが、入力の状態に対してデータがエンタングルして1対1で紐づいているという状態を指します。 つまり、通常のプログラミングでの辞書型のデータ構造に相当しており、あるキー(状態)を用いてデータを取り出して以後の処理で用いることができます。 注意としてはqRAMという名称ですがあくまでデータ構造なので古典コンピュータのRAM(メインメモリ)のようにそういうハードウェアがあるのではなく、量子回路の組み合わせで構成します。
もちろん量子なので入力が重ね合わせ状態なら取り出せるデータも重ね合わせで取り出せます。
今回の記事ではこのqRAMのデータ構造の作り方・量子回路の組み方を解説します。
RAM(Random Access Memory)って何?
WikipediaによるRAMの説明を整理すると下記です。
- コンピュータで使用するメモリ(主記憶装置)の一分類
- 格納されたデータに任意の順序でアクセスできる(ランダムアクセス)メモリ
- 電源が落ちれば記憶内容が消えてしまう短期メモリの意で使われていることが専ら
つまり、普段プログラミングするときに見聞きする「メモリ」です。 プログラムそのものやプログラムが用いるデータなどを実行している間だけメモリ上に展開して、必要な時にあるアドレスに格納されている値を読み取って処理を進めます。
古典RAMと量子RAM(qRAM)の違い
ありません、ほぼ同じです。
強いてあげるなら、前述したようにqRAMはqRAMというハードウェアを指すのではなく、メモリ動作をする状態を指します。 ただ、古典RAMもトランジスタをメモリとして扱えるようにパッケージしたものなので、使うビットが古典ビットor量子ビット、回路が古典回路or量子回路かという違いだけかもしれません。
もちろん重ね合わせ状態を使えるのはqRAMだけです。
qRAMがあると何ができる?
古典コンピュータと同じく、そのプログラムにとって必要なデータをプロセッサのすぐ近くに置いておくことができ、アクセスしやすくなります。 つまり、パフォーマンスがよくなります。
量子コンピュータもプログラムを実行しないときはデータをハードディスクのような古典の補助記憶装置にデータを保存していると思います。 そのデータを使おうとするたびにハードディスクにアクセスしていたら待ち時間のちりが積もって長くなります。 これは古典コンピュータでも同じですが、そのような処理の待ち時間を改善します。 また、計算結果で後々使いたいデータもいちいちハードディスクなどに一時保存して使いたいときに参照するのも時間がかかってしまいます。 すぐ近くにあるのがいいです。
また、このデータ構造があるおかげで実行できるアルゴリズムと解ける問題・アプリケーションがあります。 それが以下です。
qRAMが必要なアプリケーション
探索・検索などの計算量が大きい問題で威力が発揮されるようです。 これらはいずれもID-データというデータ構造をしており、答えとして知りたいものはIDですが計算するのはデータとなっています。 qRAMのデータ構造していると都合がよさそうです。
QRAMを実装するときの考え方
定義で紹介したこちらのエンタングルメントが形成されるように、CXゲート
やMCTゲート
を組み合わせればよいです。
QRAMの実装例
例えば、次のような辞書で古典的なデータがあると仮定し、それを量子回路にエンコードします。
ID | IDを示す状態 | 値 | 値を示す状態 |
---|---|---|---|
0 | |00> | 2 | |0010> |
1 | |01> | 4 | |0100> |
2 | |10> | 6 | |0110> |
3 | |11> | 8 | |1000> |
この表の組み合わせを満たすようにエンタングルメントを形成すればよいです。
inputs = QuantumRegister(2, 'input') data = QuantumRegister(4, 'data') outputs = ClassicalRegister(6, 'output') circuit = QuantumCircuit(inputs, data, outputs) ram = { '00': '0010', '01': '0100', '10': '0110', '11': '1000', } def qram(circuit, ram): for key, val in ram.items(): for idx_input in range(len(inputs)): if key[idx_input] == '0': circuit.x(inputs[idx_input]) for idx_data in range(len(data))[::-1]: if val[idx_data] == '1': circuit.mct(inputs, data[len(data) - (idx_data + 1)]) for idx_input in range(len(inputs)): if key[idx_input] == '0': circuit.x(inputs[idx_input]) circuit.barrier() circuit.h(inputs) circuit.barrier() qram(circuit, ram) circuit.measure(inputs, outputs[:len(inputs)]) circuit.measure(data, outputs[len(inputs):len(inputs) + len(data)]) backend = Aer.get_backend('qasm_simulator') job = execute(circuit, backend=backend) result = job.result() count = result.get_counts() circuit.draw(output='mpl')
ちゃんとエンタングルしているか測定して確認します。
状態を示す0/1の並びの左4桁がデータで右2桁が入力状態です。 上の表の通りにエンタングルしていますね。
QuantumChallenge2020の例
その他のqRAMの応用例としてQuantumChallenge2020のコードを紹介します。