【寄稿】ゼロから学ぶショアのアルゴリズム（第2回）：blueqat SDKで量子加算器を自動生成する

第1回では、ショアのアルゴリズムの全体の流れと、量子回路が受け持つ部分を整理しました。今回から、Python で量子回路を実際に組んでいきます。

最初は、すべての計算の土台になる基本ゲート（X、CX、CCX）の動きを確かめ、そのうえで量子加算器（Plain Adder）を組みます。回路の組み方は Vedral, Barenco, Ekert の論文 Quantum Networks for Elementary Arithmetic Operations（arXiv:quant-ph/9511018）に沿います。

準備

量子回路の記述には blueqat SDK を使います。

pip install git+https://github.com/blueqat/blueqatSDK

この記事のコードは、この方法で入る blueqat 2.1.3 で動かしています。

基本ゲート3つ

ショアのアルゴリズムの計算も、分解すると NOT・XOR・AND という普通の論理演算に行き着きます。量子回路では、これを次の3つのゲートで表します。

X ゲート（NOT）：ビットを反転する
CX ゲート（CNOT、XOR に当たる）：制御ビットが 1 のときだけ、標的ビットを反転する
CCX ゲート（トフォリ、AND に当たる）：2つの制御ビットが両方 1 のときだけ、標的ビットを反転する

from blueqat import Circuit

def measure(circuit):
    """回路を1回だけ実行し、測定結果の文字列を返す（右端が0番目の量子ビット）"""
    result = circuit.m[:].run(shots=1, backend='statevector')
    return result.most_common(1)[0][0]

print("X   : |0> ->", measure(Circuit(1).x[0]))
print("X   : |1> ->", measure(Circuit(1).x[0].x[0]))
print("CX  : 制御0 ->", measure(Circuit(2).cx[0, 1]))
print("CX  : 制御1 ->", measure(Circuit(2).x[0].cx[0, 1]))
print("CCX : 制御は q0 だけ1 ->", measure(Circuit(3).x[0].ccx[0, 1, 2]))
print("CCX : 制御 q0,q1 とも1 ->", measure(Circuit(3).x[0].x[1].ccx[0, 1, 2]))

X   : |0> -> 1
X   : |1> -> 0
CX  : 制御0 -> 00
CX  : 制御1 -> 11
CCX : 制御は q0 だけ1 -> 001
CCX : 制御 q0,q1 とも1 -> 111

測定結果の読み方

blueqat 2.1.3 の測定結果の文字列は、右端が0番目の量子ビットです。上の 001 は「q0 だけが 1」という意味で、制御が片方しか 1 でないので CCX は何もしていません。111 は、両方の制御が 1 だったので q2 が反転した結果です。

並び順は SDK ごとに違い、同じ blueqat でも版によって逆になります（PyPI 版の 2.0.4 は左端が0番目）。自分の環境で x[0] を1回だけ掛けて、どちらの端に 1 が出るかを見るのが確実です。

量子加算器の設計

基本ゲートの次は、論文 Figure 1 の量子加算器です。ショアのアルゴリズムで使う計算は、すべてこの加算器を部品にして組み上がります。

量子加算器の組み立て。n ビットの足し算に 3n+1 量子ビットを使い、往路で繰り上がりを作り、復路でそれを消しながら和を確定する。

量子回路で足し算をすると、途中で繰り上がりの情報が生まれます。これを残したままにすると、その量子ビットが入力と絡み合った（エンタングルした）まま残り、後の段で重ね合わせを干渉させるときに邪魔になります。そこで、足し算を終えたら繰り上がりを 0 に戻す（アンコンピュートする）ところまでを1つの回路にします。

量子ビットの割り当て

n ビットどうしの足し算に、3n + 1 個の量子ビットを使います。

キャリー c（n 個）：0 〜 n−1 番
足す数 a（n 個）：n 〜 2n−1 番
足される数 b（n+1 個）：2n 〜 3n 番。答えはここに入る。最後の 3n 番（論文の b_n）が、最上位の繰り上がりの置き場所

手順

往路（CARRY）：下の桁から順に、CCX で「a_i と b_i（と下からの繰り上がり）から、次の桁の繰り上がり c_{i+1} を作る」。最上位の桁だけは、次の c の代わりに b_n に書く
折り返し：最上位の桁の和を SUM で確定する。その前に、最上位の CARRY が b に掛けた CX を、もう一度 CX を掛けて戻しておく（下の桁では、この役目を CARRY の逆回路が果たす）
復路（CARRY の逆 + SUM）：上の桁から逆向きに、CARRY の逆回路で繰り上がり c を 0 に戻しながら、各桁の和を SUM で b に書く

量子加算器のコード

入力の大きさに合わせてビット数を決め、回路を組み、1回実行して答えを10進数に戻すところまでを関数にします。後の回では、この回路を剰余加算器や乗算器の部品として何度も使います。

from blueqat import Circuit

def carry(c, a, b, c_next):
    """CARRY: この桁の繰り上がりを c_next に作る"""
    circ = Circuit()
    circ.ccx[a, b, c_next]
    circ.cx[a, b]
    circ.ccx[c, b, c_next]
    return circ

def carry_inv(c, a, b, c_next):
    """CARRY の逆（ゲートを逆順に並べたもの）。繰り上がりを消す"""
    circ = Circuit()
    circ.ccx[c, b, c_next]
    circ.cx[a, b]
    circ.ccx[a, b, c_next]
    return circ

def sum_gate(c, a, b):
    """SUM: この桁の和 a XOR b XOR c を b に書く"""
    circ = Circuit()
    circ.cx[a, b]
    circ.cx[c, b]
    return circ

def build_adder(val_a, val_b, n):
    """b := a + b を計算する回路を組む。(回路, b の量子ビット番号) を返す"""
    circ = Circuit(3 * n + 1)
    c = list(range(n))                  # キャリー      0 .. n-1
    a = list(range(n, 2 * n))           # 足す数 a      n .. 2n-1
    b = list(range(2 * n, 3 * n + 1))   # 足される数 b  2n .. 3n（b[n] が最上位の繰り上がり）

    for i in range(n):                  # 入力を書き込む
        if (val_a >> i) & 1: circ.x[a[i]]
        if (val_b >> i) & 1: circ.x[b[i]]

    for i in range(n - 1):              # 往路: 下の桁から繰り上がりを作る
        circ += carry(c[i], a[i], b[i], c[i + 1])
    circ += carry(c[n - 1], a[n - 1], b[n - 1], b[n])   # 最上位の繰り上がりは b[n] へ

    circ.cx[a[n - 1], b[n - 1]]         # 最上位の CARRY が b に掛けた CX を戻す
    circ += sum_gate(c[n - 1], a[n - 1], b[n - 1])

    for i in range(n - 2, -1, -1):      # 復路: 繰り上がりを消しながら和を確定
        circ += carry_inv(c[i], a[i], b[i], c[i + 1])
        circ += sum_gate(c[i], a[i], b[i])
    return circ, b

def add(val_a, val_b):
    n = max(val_a, val_b, 1).bit_length()          # 0 を入れてもレジスタが空にならないように
    circ, b = build_adder(val_a, val_b, n)
    state = circ.m[:].run(shots=1, backend='statevector').most_common(1)[0][0]
    total = circ.n_qubits
    bits = [state[total - 1 - q] for q in b]       # 右端が0番目の量子ビット
    return int("".join(reversed(bits)), 2), state, n

answer, state, n = add(10, 6)
print(f"a = 10, b = 6, n = {n}, 量子ビット数 = {3 * n + 1}")
print(f"測定結果（右端が0番目）: {state}")
print(f"答え: {answer}")

for x, y in [(1, 1), (3, 5), (7, 9), (15, 15), (0, 0)]:
    print(f"{x} + {y} = {add(x, y)[0]}")

a = 10, b = 6, n = 4, 量子ビット数 = 13
測定結果（右端が0番目）: 1000010100000
答え: 16
1 + 1 = 2
3 + 5 = 8
7 + 9 = 16
15 + 15 = 30
0 + 0 = 0

10 + 6 = 16（2進数で 10000）が、13 量子ビットの回路で正しく計算できました。

結果から読み取れる2つのこと

shots=1 で足りる理由

多くの量子アルゴリズムは答えが確率的に出るので、何千回も実行して分布をとります。ところが、この加算器に使っているのは X、CX、CCX だけです。どれも「0 と 1 を入れ替える」だけのゲートで、古典の論理回路と同じように、入力が決まれば出力も1つに決まります。そのため、1回の測定で答えが確定します。

繰り上がりがきれいに消えている

測定結果 1000010100000 を右端（0番目）から読むと、最初の4文字（キャリー c の4個）はすべて 0 です。計算の途中では繰り上がりで 1 になっていたはずのビットが、元の 0 に戻っています。

これが、復路で CARRY の逆回路を上の桁から順に掛けた効果です。答えだけを b に残し、途中で使ったビットは入力と絡み合わない状態に戻す。この「使ったら元に戻す」（アンコンピュート）は、後の回で重ね合わせのまま計算するときに欠かせません。

念のため、ビット数 n = 1〜6 のすべての組み合わせ（5,460 通り）で、答えが正しいことと、キャリーが 0 に戻ることを確かめています。

次回：剰余加算器

この加算器は、ゲートをすべて逆順に並べるだけで減算器になります。使っている X、CX、CCX がどれも、2回掛けると元に戻るゲートだからです。

次回は、足し算と引き算を組み合わせて「N 以上になったら N を引く」剰余加算器（Adder modulo N）を作ります。量子回路で「もし〜なら」をどう書くかが、次の題材です。

寄稿は筆者個人の見解です。編集部の見解ではありません。この媒体はblueqat株式会社が運営しています。