NVIDIA CUDA-Q チュートリアル＆H100ベンチマーク１： Bernstein-Vazirani (BV) アルゴリズム

今回からCUDA-Qを使ってもらうようにアルゴリズムの概要を説明します。
より具体的な方法については原文を読んでください。

インストール方法は極めて簡単です。

pip install cudaq

では、早速見てみましょう。

Bernstein-Vazirani アルゴリズムの概要

BVアルゴリズムは、「ある秘密のビット列 s を1回の関数呼び出し（クエリ）で見つける」量子アルゴリズムです。

問題設定

関数 $f(x)$ は利用できますが、中身はブラックボックスです。
この関数は、秘密のビット列 s によって以下のように定義されています：

f(x) = s \cdot x mod 2

sとxはビットの内積を表します。たとえば、 $s = 101$ 、 $x = 110$ のとき、 $f(x) = 1*1 + 0*1 + 1*0 = 1$

ゴール

この関数を使って、秘密のビット列 s を見つけることです。

従来型コンピュータの方法

例： $n = 3$ の場合
秘密のビット列 $s = s₀s₁s₂$ を求めたい。

ステップ

関数 $f(x) = s \cdot x mod 2$ に対して、次のような $x$ を使って問い合わせます：

$x = 100 \to f(100) = s₀$

$x = 010 \to f(010) = s₁$

$x = 001 \to f(001) = s₂$

→ それぞれのビットを直接取り出せるため、3回のクエリで $s$ を特定できます。

量子アルゴリズム（Bernstein-Vazirani アルゴリズム）

量子アルゴリズムでは、1回の関数呼び出しだけで s を取得できます。
重ね合わせ・干渉・位相キックバックという量子特有の性質を活用します。

この関数を導入した量子回路をオラクルと呼びますが、開発者は隠された数字sを使って量子回路を作り、ユーザーはそれを使ってsを推定できます。自分もちょっと疑問だったのですが、量子回路の中にsを知っている回路が含まれていますが、これはOKのようです。

基本的にはf(x) = sx mod2 を計算したくて、見えない回路の中できちんと入力xに対応したsを導入した回路を作った上で、使ってもらうようです。

上記回路は従来型のコンピュータで入力xがビット列になっているため、量子コンピュータのように重ね合わせが使えないので問い合わせ回数が増えるという原理になっています。

BVアルゴリズムはxの入力に対応する量子ビットと位相キックバックと呼ばれるアルゴリズムを反映させるための補助量子ビットを利用します。入力はHゲートを利用して重ね合わせ状態に。補助量子ビットも|1>状態に反転させてからHゲートを適用して重ね合わせ状態にします。

オラクルの作り方は任意ですが、今回はsを知った上で、sが1のときに補助量子ビットとの間にCXゲートをかける位相キックバック回路を利用して位相を反転させます。

最後にHゲートを適用してビットに戻して測定をすることで、xとsと位相キックバックを利用してsをビットとして表現できます。ポイントは補助量子ビットは1つですが、位相キックバックを利用すると一つのターゲットビットに対して複数の制御ゲートに位相反転の効果をもたらすことができます。

詳しい数式類は元のCUDA-Qのチュートリアルをご覧ください。

CUDA-Qのコード

チュートリアルのコードを見てみます。

import cudaq
from typing import List

cudaq.set_target('qpp-cpu')
#cudaq.set_target('nvidia')  # GPU backend which enables scaling to large problem sizes

まずこちらはライブラリのインポートとマシンの設定です。CPUが設定されていますが、NVIDIA GPUを搭載した環境では、nvidiaを指定することでGPUモードに切り替わります。

qubit_count = 5  # Set to around 30 qubits if you have GPU access

secret_string = [1, 1, 0, 1,
                 0]  # Change the secret string to whatever you prefer

assert qubit_count == len(secret_string)

次に量子ビット数を決めて、秘密のsを決めます。

@cudaq.kernel
def oracle(register: cudaq.qview, auxiliary_qubit: cudaq.qubit,
           secret_string: List[int]):

    for index, bit in enumerate(secret_string):
        if bit == 1:
            x.ctrl(register[index], auxiliary_qubit)

次にオラクルを作ります。今回はsを知っていることを前提として入力xに対してsのビットが1の場合にCXゲートを入力xのビット列に対してかける操作を作っています。

@cudaq.kernel
def bernstein_vazirani(secret_string: List[int]):

    qubits = cudaq.qvector(len(secret_string))  # register of size n
    auxiliary_qubit = cudaq.qubit()  # auxiliary qubit

    # Prepare the auxillary qubit.
    x(auxiliary_qubit)
    h(auxiliary_qubit)

    # Place the rest of the register in a superposition state.
    h(qubits)

    # Query the oracle.
    oracle(qubits, auxiliary_qubit, secret_string)

    # Apply another set of Hadamards to the register.
    h(qubits)

    mz(qubits)  # measures only the main register


print(cudaq.draw(bernstein_vazirani, secret_string))
result = cudaq.sample(bernstein_vazirani, secret_string)

print(f"secret bitstring = {secret_string}")
print(f"measured state = {result.most_probable()}")
print(
    f"Were we successful? {''.join([str(i) for i in secret_string]) == result.most_probable()}"
)

最後に実行コードです。補助量子ビットを用意してXゲートで1にしておきながら、Hゲートで全部を重ね合わせ状態にします。
最後に再度Hゲートをかけて測定を実行しています。

上記コードでは量子回路の描画、正解のs、測定された結果、正しいかどうかが示されています。

ベンチマーク

実際にこちらのコードを利用してsを推定するBVアルゴリズムをCPUとGPUで比較しました。

CPU: EPYC 9654 96コア
GPU: NVIDIA H100 SXM 80G

です。性能は十分です。

計算結果です。CPUは早い段階で計算に時間がかかります。GPUは30量子ビット以上でようやく計算時間が増えましたが桁違いの結果となりました。