科学しよう

量子計算のプログラミングの解説をメインに、データサイエンス・機械学習について勉強したことをご紹介します

MENU

qRAMの作り方

qRAM(Quantum Random Access Memory)を量子回路上で実装する方法を解説します。 こちらこちらの論文をベースにエッセンスを解説し、これがあることで解ける問題の幅が広がることを紹介します。

対象とする読者

  • 量子プログラミングに興味を持ち始めたばかりのエンジニア
  • 量子計算に興味を持ち始めたばかりの高校生・大学生 など

前提とする知識

  • 簡単な論理演算(AND, OR, NOT)が分かること
  • 基本的な量子ゲート(X, CX, CCX)が分かること

バージョン情報

目次

qRAM(Quantum Random Access Memory)とは

定義

\displaystyle{
\sum_j{\psi _j | j \gt_a} \overset{\mathrm{qRAM}}{\longrightarrow} \sum_j{\psi _j | j \gt_a} | D_j \gt_d
}

右辺に注目してもらえればいいのですが、入力の状態 | j \gt_aに対してデータ | D \gt_dエンタングルして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')

f:id:sakumadaisuke32:20210505180437p:plain
図1. qRAM動作確認回路. barrier()で仕切られた枠毎に入力状態はそれぞれ左から|00>, |01>, |10>, |11>を示します.(0, 1の数式上の表記と回路上の位置は順序逆であることに注意してください.)

ちゃんとエンタングルしているか測定して確認します。

f:id:sakumadaisuke32:20210505180956p:plain
図2. 図1の回路の測定結果

状態を示す0/1の並びの左4桁がデータで右2桁が入力状態です。 上の表の通りにエンタングルしていますね。

QuantumChallenge2020の例

その他のqRAMの応用例としてQuantumChallenge2020のコードを紹介します。

まとめ

  • qRAMはIDとデータという辞書型のデータ構造
  • 辞書を満たすようにエンタングルメントを形成すれば作れる
  • 探索・検索系のアルゴリズムで重要

参考


量子コンピューティング 基本アルゴリズムから量子機械学習まで [ 情報処理学会出版委員会 ]


コンピュータアーキテクチャ技術入門 ーー高速化の追求×消費電力の壁【電子書籍】[ Hisa Ando ]