NVIDIA CUDA-Q チュートリアル＆H100ベンチマーク５： Deutschのアルゴリズム

Deutschのアルゴリズムは、ある特定のタイプの関数に対して、量子計算が古典計算より効率的であることを示す最初のアルゴリズムです。今回はCUDA-Qのチュートリアルをベースに見てみます。

問題設定

対象の関数 f:{0,1}→{0,1} は、次のどちらか：

定数関数（constant）：入力に関係なく常に同じ出力（f(0) = f(1)）
バランス関数（balanced）：出力が0と1で分かれる（f(0) ≠ f(1)）

古典的な解法

必ず f(0) と f(1) の2回評価が必要。

例：

f(0) = 0、f(1) = 0 → 定数関数
f(0) = 0、f(1) = 1 → バランス関数

量子アルゴリズム（Deutschのアルゴリズム）

量子ビットの重ね合わせと干渉を利用。関数評価はたったの1回で、定数かバランスかを判断可能。
古典の部分を飛ばして、CUDA-Qの部分を見てみます。
詳しい実装や数式は原文をみてくださいませ。

まずはツール読み込み。今回はあまり大した量子回路ではないので、GPUで固定しています。

import cudaq
import numpy as np
from typing import List

cudaq.set_target("nvidia")

次に関数を入れます。f(0)とf(1)の値を出力して準備します。あとで、00と11の場合も計算します。

fx = [0, 1]

量子回路の実装です。

# Let us now code up the circuit shown above following the state Psi after each step.

qubit_count = 2


@cudaq.kernel
def kernel(fx: List[int]):
    qubit_0 = cudaq.qubit()
    qubit_1 = cudaq.qubit()

    # Psi 0
    x(qubit_1)

    # Psi 1
    h(qubit_0)
    h(qubit_1)

    # Psi 2 - oracle
    if fx[0] == 1:
        x.ctrl(qubit_0, qubit_1)
        x(qubit_1)

    if fx[1] == 1:
        x.ctrl(qubit_0, qubit_1)

    # Psi 3
    h(qubit_0)

    # Measure the qubit to yield if the function is constant or balanced.
    mz(qubit_0)


print(cudaq.draw(kernel, fx))

result = cudaq.sample(kernel, fx, shots_count=1)

if np.array(result)[0] == '0':
    print('f(x) is a constant function')
elif np.array(result)[0] == '1':
    print('f(x) is a balanced function')