改訂版です。 初版から2点を直しました。
- 測定結果の読み取り方。今の blueqat（2.1.3）では、測定結果の文字列の右端が0番目の量子ビットです（第2回で説明しています）
- 条件付きで N を足し戻す部分（ステップ4）の作り方を、論文 Fig.4 どおりに改めました。これで3制御のゲートと補助の量子ビットが要らなくなり、量子ビットは 4n+3 個から 4n+2 個に減りました
はじめに
第2回では通常の量子加算器を作りました。今回はその上に剰余加算 a + b mod N を実装します。
a^j mod N を計算する過程で生じる中間値はすべて [0, N) に収める必要があるので、これがショアのアルゴリズムの中で実際に使われる足し算です。
参考文献は Vedral, Barenco, Ekert, "Quantum Networks for Elementary Arithmetic Operations" (1995) の Fig. 4（論文III.B節）です。
5ステップのアイデア
(a+b) mod N は古典的には簡単です。足して、結果が N 以上ならその分だけ N を引く。
しかし量子コンピュータでは「確認してから分岐する」ことができません。確認には測定が必要で、大事にしたい重ね合わせが壊れてしまうからです。代わりに、確認は量子ビットに記録し、条件分岐は回路の形で表現します。
- 足し算: b ← a + b（第2回の加算器）
- N を引く: b ← b - N（加算器を逆向きに実行）
- 符号を検出: ステップ2で b が負になったら、b レジスタの一番上の余分な量子ビットが 1 になる（借り／あふれのフラグ）。これをフラグ量子ビット t にコピーする
- 条件付きで N を足し戻す: t=1 の場合（a+b < N で、引きすぎた場合）、N を足し戻す。ただし重ね合わせの中で t=1 になっている枝だけに
- 後片付け: t を |0⟩ に戻し、符号検出のステップを取り消す。これで回路全体が、b 以外に何も痕跡を残さない再利用可能な操作になる
前提は 0 ≤ a, b < N です。ステップ1〜2は加算器・減算器をそのまま使います。面白いのはステップ4で、初版ではここを論文と違う形で作っていました。
第2回の部品を再利用する
第2回の carry / carry_inv / sum_gate をそのまま使い、加算器を「レジスタを外から渡して回路だけを返す」add_circuit に組み直します。その逆演算が sub_circuit です。
from blueqat import Circuit
def carry(c, a, b, 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):
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):
circ = Circuit()
circ.cx[a, b]
circ.cx[c, b]
return circ
def add_circuit(c, a, b, n):
"""b := a + b。キャリーレジスタ c を使う。b は n+1 量子ビット。"""
circ = Circuit()
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])
circ.cx[a[n - 1], b[n - 1]]
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
def sub_circuit(c, a, b, n):
"""b := b - a。加算器のゲート列を、まるごと逆順にするだけ。"""
add_circ = add_circuit(c, a, b, n)
reversed_circ = Circuit()
reversed_circ.ops = list(reversed(add_circ.ops))
return reversed_circsub_circuit が「同じゲート列を逆順に実行するだけ」で済むのは、ここで使うゲートが CX と CCX だけで、どちらも自己逆元だからです。個々のゲートを反転させる必要はありません。論文もそう書いています（「an adder whose network is run backwards」）。
ステップ4の作り方
「t=1 のときだけ b ← b + N を実行する」をどう作るか。
初版のやり方（論文とは違う）
素直に考えると、add_circuit(c, N, b, n) の全ゲートを t で制御することになります。CX を制御すれば CCX になって簡単ですが、CCX を制御すると3制御Xが必要で、SDK に直接の対応ゲートがありません。
そこで初版では、補助量子ビット（ancilla）を1つ使い、最初の2制御の AND を CCX で補助ビットに計算し、それを制御に使い、最後に同じ CCX でもう一度戻す、という分解を書きました。これを「罠」として紹介しました。
論文のやり方
ところが論文の該当箇所は、まったく違うことを言っています。
Conditionally on the value of this last qubit |t⟩, N is added back to the second register, leaving it with the value a + b mod N. This is done by either leaving the first register with the value N (in case of overflow), or resetting it to 0 (if there is no overflow) and then using a plain adder.
加算器には手を触れない。 代わりに、足す数を置いている N レジスタのほうを条件付きにする。t=1 なら N のまま、t=0 なら 0 にリセットして、無制御の加算器を通す。
なぜこれで済むのか。0 を足す加算は何もしないからです。加算器そのものは無条件に走らせてよく、入力が 0 なら勝手に恒等変換になってくれる。
「重ね合わせのある枝だけで演算したい」と思ったとき、演算そのものを条件付きにするのではなく、入力を条件付きにして、演算が自明になるようにする。可逆計算ではよく効く発想です。論文はこの手口を、次回の制御乗算器（Fig.5）でもまったく同じ形で使っています。
そして決定的なのは、この作り方だと3制御ゲートが一度も出てこないことです。初版の「罠」は、こちらの実装が招いたものでした。補助量子ビットも要りません。
N レジスタを条件付きに 0 にする
N は回路を組む時点で分かっている古典的な定数なので、どのビットが 1 かは既知です。t を X で挟んだ 0 制御の CNOT を、N の立っているビットに当てるだけです。
def set_to_zero_if(t, N, val_N, n):
"""t=0 のとき N レジスタを 0 にする（t=1 ならそのまま）。自己逆元。"""
circ = Circuit()
circ.x[t]
for j in range(n):
if (val_N >> j) & 1:
circ.cx[t, N[j]]
circ.x[t]
return circX も CX も自己逆元で、しかもターゲットが互いに違うので、この回路をもう一度流せば N が元に戻ります。「かけて、使って、同じものでほどく」— 第2回から出てくるアンコンピュートの、いちばん簡単な形です。
レジスタ構成
剰余加算器全体で 4n+2 量子ビットです（初版は 4n+3 でした）。
c[0..n-1]: キャリーレジスタ（足し算・引き算のステップで共用）a[0..n-1]: 1つ目の加数b[0..n]: 2つ目の加数と結果（n+1 幅。ステップ3では最上位ビットがあふれフラグを兼ねる）N[0..n-1]: 法（定数として読み込む）t: 「N を足し戻す必要があったか」を表すフラグ1個
補助量子ビットの行が消えたのが、今回の改訂です。
剰余加算器の全コード
def build_modulo_adder(input_a, input_b, input_N, n):
"""b := (a + b) mod N。(circuit, b のインデックス) を返す。"""
num_qubits = 4 * n + 2
circ = Circuit(num_qubits)
c = list(range(n))
a = list(range(n, 2 * n))
b = list(range(2 * n, 3 * n + 1))
N = list(range(3 * n + 1, 4 * n + 1))
t = 4 * n + 1
# 入力のエンコード
for i in range(n):
if (input_a >> i) & 1: circ.x[a[i]]
if (input_b >> i) & 1: circ.x[b[i]]
if (input_N >> i) & 1: circ.x[N[i]]
# ステップ1-2: b <- a + b、そして b <- b - N
circ += add_circuit(c, a, b, n)
circ += sub_circuit(c, N, b, n)
# ステップ3: 借り/あふれビットをフラグ t にコピー
circ.cx[b[n], t]
# ステップ4: t=0 なら N レジスタを 0 にして、無制御の加算器を通し、N を戻す
gate = set_to_zero_if(t, N, input_N, n)
circ += gate
circ += add_circuit(c, N, b, n)
circ += gate
# ステップ5: 後片付け。符号検出を取り消して t を |0> に戻す
circ += sub_circuit(c, a, b, n)
circ.x[b[n]]
circ.cx[b[n], t]
circ.x[b[n]]
circ += add_circuit(c, a, b, n)
return circ, bステップ4が3行になりました。初版のように add_circuit の中身を1ゲートずつ走査して書き換える必要はありません。
テスト
実行用の関数です。測定結果は右端が0番目の量子ビットなので、state[total - 1 - q] で読みます。
def run_modulo_adder(val_a, val_b, val_N, n=None):
if n is None:
n = max(val_N, 1).bit_length()
circuit, b = build_modulo_adder(val_a, val_b, val_N, n)
state = circuit.m[:].run(shots=1, backend='statevector').most_common(1)[0][0]
total = circuit.n_qubits
bits = [state[total - 1 - q] for q in b] # bits[0] が最下位ビット
return int("".join(reversed(bits)), 2)
tests = [(7, 6, 11, 4), (14, 13, 15, 4), (3, 5, 9, 4), (0, 0, 7, 3), (5, 5, 6, 3)]
for x, y, N, n in tests:
result = run_modulo_adder(x, y, N, n)
expected = (x + y) % N
print(f"({x}+{y}) mod {N} = {result} (期待値 {expected}, "
f"{'OK' if result == expected else 'MISMATCH'})")(7+6) mod 11 = 2 (期待値 2, OK)
(14+13) mod 15 = 12 (期待値 12, OK)
(3+5) mod 9 = 8 (期待値 8, OK)
(0+0) mod 7 = 0 (期待値 0, OK)
(5+5) mod 6 = 4 (期待値 4, OK)
backend='statevector'を明示しているのがポイントです。blueqat のデフォルトのバックエンドはテンソルネットワークの縮約で動くため、コストが量子ビット数ではなく回路のつながり方で決まります。この種の「量子ビットは少ないが深い」回路とは相性が悪く、次回の乗算器では20量子ビット足らずでメモリを使い切って落ちました。状態ベクトルなら消費メモリは 2^(量子ビット数) で素直に決まります。
境界値も見ておきます。a+b がちょうど N になる場合（答えは 0）、片方が 0 の場合、両方が最大の場合。
(4+3) mod 7 = 0 (期待値 0, OK)
(10+10) mod 11 = 9 (期待値 9, OK)
(0+5) mod 9 = 5 (期待値 5, OK)
(6+6) mod 7 = 5 (期待値 5, OK)
(8+9) mod 10 = 7 (期待値 7, OK)網羅テスト
N = 5, 7, 9 について、a と b を全通り試します。しかも結果の b だけでなく、N レジスタ・フラグ t・キャリーレジスタ c がすべて元に戻っていることも確認します。
作業用のビットが |0⟩ に戻っていないと、そのビットが結果と絡んだまま残り、後段の量子干渉が壊れます。剰余加算器は次回・次々回で何十回も繰り返し使う部品なので、ここは1ケースも落とせません。
def run_and_check(val_a, val_b, val_N, n=None):
if n is None:
n = max(val_N, 1).bit_length()
circuit, b = build_modulo_adder(val_a, val_b, val_N, n)
c = list(range(n)); N = list(range(3 * n + 1, 4 * n + 1)); t = 4 * n + 1
state = circuit.m[:].run(shots=1, backend='statevector').most_common(1)[0][0]
total = circuit.n_qubits
read = lambda qs: int("".join(reversed([state[total - 1 - q] for q in qs])), 2)
clean = read(N) == val_N and int(state[total - 1 - t]) == 0 and read(c) == 0
return read(b), clean
bad = 0
for N in (5, 7, 9):
for a in range(N):
for b in range(N):
result, clean = run_and_check(a, b, N)
if result != (a + b) % N or not clean:
bad += 1
print(f"MISMATCH ({a}+{b})%{N} -> {result}, clean={clean}")
print(f"155ケース中 {bad} 件のミスマッチ")155ケース中 0 件のミスマッチ全通り通りました。
編集部より：当サイトで確かめました
この記事のコードを、blueqat 2.1.3 で確かめました。回路は X・CX・CCX だけでできているので、量子ビットを 0 と 1 のビットとして1ゲートずつ追えば、結果を正確に確かめられます。記事の10ケースと網羅テストの155通りはすべて正解で、N レジスタ・フラグ t・キャリーも元に戻っていました。範囲を広げた N = 2〜33 の全通りでもミスマッチは0件、量子ビット数・ゲート数・最大制御数は下の表のとおりでした。
3つの罠、あらためて
初版では実装中にはまった3点を「罠」として紹介しました。改訂後の評価はこうです。
罠①：逆演算はゲートの順序も反転させる ― これは本物
減算を作るとき、内部の carry を carry_inv に差し替えるだけでは足りません。ゲート列全体を逆順にする必要があります。可逆計算では「回路の逆」とは「各ゲートの逆を、逆順に適用する」ことで、今回は各ゲートが自己逆元なので後半だけが効いてきます。
これは論文どおりで、リスト操作 list(reversed(...)) 一発で書けます。
罠②：多重制御ゲートがない ― これは自分で招いたものだった
CCX をさらに制御する CCCX が blueqat にない、という話です。補助ビットとトフォリ連鎖で代用しました。
これは罠ではなく、こちらの設計ミスでした。 論文どおりステップ4を組めば、3制御ゲートは一度も現れません。回路全体を通してトフォリ（CCX）が最大で、補助ビットも0本です。
「0 を足すのは恒等変換」という当たり前の事実を使うだけで、多重制御の話が丸ごと消える。1995年の論文がなぜこの形になっているのか、実装して初めて分かりました。
罠③：X ゲートの位置 ― これも本物
ステップ5でフラグ t を |0⟩ に戻すところ、
circ.x[b[n]]
circ.cx[b[n], t]
circ.x[b[n]]の X を1つ落とすと、条件が反転して t が消えません。0 制御の CNOT を作るためのもので、論文の図では小さな白丸で描かれている部分です。論文の図は、白丸と黒丸の区別まで読まないといけない。
なお改訂後は、ステップ4の set_to_zero_if でも同じ「X で挟む」パターンが出てきます。慣れると定型句として読めるようになります。
量子ビット数とゲート数
| n | 量子ビット | ゲート数 | 最大制御数 |
|---|---|---|---|
| 3 | 14 | 124 | 2 |
| 4 | 18 | 166 | 2 |
| 8 | 34 | 334 | 2 |
| 16 | 66 | 670 | 2 |
ゲート数は、N のビットがすべて 1 のとき（いちばん多くなる場合）の数で、入力を書き込む X は含めていません。N によっては、ここから最大 2n 個少なくなります。
量子ビット・ゲート数ともに n に線形です。論文が「the number of elementary gates in the plain adder, the modular addition ... scales linearly with n」と書いているとおりになりました。
最大制御数がどこまでいっても 2 のままなのが、改訂の一番の収穫です。
まとめ
- (a+b) mod N は「足す → N を引く → あふれを見る → 条件付きで足し戻す → 後片付け」の5ステップ
- 減算は加算器のゲート列を丸ごと逆順にするだけ
- 条件付きの足し戻しは、加算器を制御するのではなく N レジスタを条件付きに 0 にする。 0 を足す加算は恒等変換なので、加算器は無条件でよい
- おかげでトフォリを超えるゲートも補助量子ビットも不要。4n+2 量子ビットで済む
- 作業用ビットが |0⟩ に戻っているかは、結果の値と同じくらい厳しくテストする
- 現行 blueqat では測定文字列の右端が qubit 0
次回予告
足し算と剰余加算ができたので、次は制御剰余乗算です。定数 a を、量子ビットで制御しながら N を法として掛ける。被乗数をシフトしたコピーを繰り返し剰余加算する、可逆な筆算です。
そこでも「入力を条件付きにして演算を自明にする」という、今回と同じ手口がもう一度出てきます。
寄稿は筆者個人の見解です。編集部の見解ではありません。 この媒体はblueqat株式会社が運営しています。
