ゼロから学ぶショアのアルゴリズム（第2回）：blueqatSDKで量子加算器（Plain Adder）を自動生成する！
皆さんこんにちは！前回はショアのアルゴリズムの全体フローと、その中で「量子回路による計算」がいかに重要な役割を果たしているか、概要を解説しました。
今回からはいよいよ、実際のPython環境を使って量子回路を順番に実装していきます。
まずは旅の第一歩として、すべての計算の基盤となる「基本ゲート（X, CX, CCX）」の動作確認と、次に挑戦する「量子加算器（Plain Adder）」の設計・自動生成までを一気に進めていきましょう！
使用するライブラリは、日本発で非常にシンプルに量子回路が書ける blueqat SDK です。
1. 開発環境の準備
まずはターミナルやJupyter Notebookで、Blueqatをインストールしておきましょう。
pip install git+https://github.com/blueqat/blueqatSDK
準備はこれだけです。さっそくコードを書いていきましょう！
2. すべての基盤となる3つの基本ゲートを実装する
ショアのアルゴリズムのような複雑な計算も、分解していくと「NOT」「XOR」「AND」といった古典コンピュータでもお馴染みの論理演算に行き着きます。量子回路では、これらを以下の3つのゲートで表現します。
- X ゲート（NOT演算）：ビットを反転させる
-
CX ゲート（CNOT / XOR演算）：制御ビットが
1のときだけ、標的ビットを反転させる -
CCX ゲート（Toffoli / AND演算）：2つの制御ビットがともに
1のときだけ、標的ビットを反転させる
これらの挙動を確認するために、以下のPythonスクリプトを実行してみましょう。
from blueqat import Circuit
def print_result(title, circuit):
"""回路を実行して結果を綺麗に表示する補助関数"""
# .m[:] で全量子ビットを測定し、1回だけサンプリングします
result = circuit.m[:].run(shots=1)
# 確定的な回路なので、一番確率の高い状態（1つだけ）を取得
state = list(result.keys())[0]
print(f"{title} -> 出力状態: {state}")
print("=== 1. X ゲート (NOT) ===")
# 初期状態 |0> に X を適用 -> |1> になる
c1 = Circuit().x[0]
print_result("入力 |0>", c1)
# 初期状態 |1>（Xで1にしてから）に、もう一度 X を適用 -> |0> に戻る
c2 = Circuit().x[0].x[0]
print_result("入力 |1>", c2)
print("\n=== 2. CX ゲート (Controlled-NOT) ===")
# 引数は [制御ビット, 標的ビット]
# 入力 |00> (c=0, t=0) -> 制御が0なので変化なし
c_cx1 = Circuit()
c_cx1.cx[0, 1]
print_result("入力 |00>", c_cx1)
# 入力 |10> (c=1, t=0) -> 制御が1なので標的が反転して |11> になる
c_cx2 = Circuit().x[0]
c_cx2.cx[0, 1]
print_result("入力 |10>", c_cx2)
print("\n=== 3. CCX ゲート (Toffoli) ===")
# 引数は [制御ビット1, 制御ビット2, 標的ビット]
# 入力 |100> (c1=1, c2=0, t=0) -> 片方しか1じゃないので変化なし
c_ccx1 = Circuit().x[0]
c_ccx1.ccx[0, 1, 2]
print_result("入力 |100>", c_ccx1)
# 入力 |110> (c1=1, c2=1, t=0) -> 両方1なので標的が反転して |111> になる
c_ccx2 = Circuit().x[0].x[1]
c_ccx2.ccx[0, 1, 2]
print_result("入力 |110> (量子ビットの並び順に注意)", c_ccx2)
実行すると、以下のような結果が出力されます。
=== 1. X ゲート (NOT) ===
入力 |0> -> 出力状態: 1
入力 |1> -> 出力状態: 0
=== 2. CX ゲート (Controlled-NOT) ===
入力 |00> -> 出力状態: 00
入力 |10> -> 出力状態: 11
=== 3. CCX ゲート (Toffoli / Controlled-Controlled-NOT) ===
入力 |100> -> 出力状態: 100
入力 |110> (量子ビットの並び順に注意) -> 出力状態: 111
📝 blueqatSDKの出力の読み方
blueqatSDKで測定した結果（01 や 111 などの文字列）は、「左端が0番目の量子ビット、右にいくにつれて1番目、2番目…」 という順番で表示されます。
CCXゲートの最後の実験で 出力状態: 111 となっていれば、0番目、1番目、2番目のすべてのビットがしっかり 1 になっていることが確認できます。
3. 通常の加算器（Plain Adder）の設計図
基本ゲートの動きが確認できたら、いよいよステップ2「量子加算器（Plain Adder）」の設計に入ります。
Vedralらの論文（9511018v1）の Figure 1 に登場する、もっとも重要なビルディングブロックです。
引用：https://arxiv.org/abs/quant-ph/9511018
量子計算では、計算の途中で発生したゴミデータ（繰り上がりなど）をそのままにしておくと、量子一斉計算（重ね合わせ）の邪魔（デコヒーレンスなど）になってしまいます。そのため、「足し算をした後、繰り上がりのビットをきれいに初期状態（0）に戻す」という特殊なアプローチ（アンコンピュート）が必要になります。
この加算器を作るために、論文（Figure 1）の構造を完全に再現した、次のようなレジスタ（量子ビットの束）を準備します。任意の
使用する量子ビットの構成（インデックスの自動割り当てルール）
-
キャリーレジスタ
c n \rightarrow 0からn - 1番目 -
レジスタ
a n \rightarrow nから2n - 1番目 -
レジスタ
b n + 1 \rightarrow 2nから3n番目 - このレジスタ
b 3n番目のビットが論文に登場する「b_n b
加算のアルゴリズム（流れ）
-
CARRY（繰り上がり）回路：
下位ビットから順番に、CCXゲートを使って「a_i b_i c_{i+1} b_n -
SUM（和の確定）回路：
最上位ビットの手前のSUMを確定させます。 -
UNCOMPUTE（キャリーの消去）とSUMの確定：
今度は上位ビットから逆向きにループを回してゲートを適用していき（アンコンピュート）、途中で使ったキャリーレジスタc 0にリセットしながら、各桁の足し算結果（XOR）を確定させていきます。
4. 完全自動・カプセル化された量子加算器の全コード
ショアのアルゴリズムで大きな数を扱うためには、何十ビットもの回路が必要になります。それを手動で1ビットずつ書くわけにはいかないので、今回は「入力された数値から必要なビット数を自動計算し、回路の自動生成、実行、結果の10進数への復元まで」をワンストップで行う関数として実装しました。
Pythonの .bit_length() を用いて、入力された値（n_bits を自動で割り出します。
from blueqat import Circuit
def carry(c, a, b, c_next):
"""CARRY回路: 繰り上がりを計算する"""
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回路: その桁の足し算結果(XOR)を確定させてbに書き込む"""
circ = Circuit()
circ.cx[a, b]
circ.cx[c, b]
return circ
def build_general_adder(input_a, input_b, n):
"""
任意のnビットの足し算を行う回路を自動生成するコア関数
"""
num_qubits = 3 * n + 1
circ = Circuit(num_qubits)
# 論文(Figure 1)通りのインデックスの自動割り当て
c = [i for i in range(n)] # 0 〜 n-1
a = [i for i in range(n, 2*n)] # n 〜 2n-1
b = [i for i in range(2*n, 3*n + 1)] # 2n 〜 3n (最後のb[n]がb_n)
# 入力値を量子ビットにエンコード
for i in range(n):
if (input_a >> i) & 1: circ.x[a[i]]
if (input_b >> i) & 1: circ.x[b[i]]
# 【往路】CARRYをループで下位から順に適用
for i in range(n - 1):
circ += carry(c[i], a[i], b[i], c[i+1])
# 最上位のCARRYだけは、次のcではなく、bの末尾(b_n)に接続する
circ += carry(c[n-1], a[n-1], b[n-1], b[n])
# 【中間】最上位の手前のSUMを確定
circ.cx[a[n-1], b[n-1]]
circ += sum_gate(c[n-1], a[n-1], b[n-1])
# 【復路】アンコンピュートとSUMの確定を逆順にループ
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 run_quantum_adder(val_a, val_b):
"""
2つの10進数を入力として受け取り、
自動で最適なビット数の量子回路を組んで実行し、
計算結果（10進数）と内部の量子状態文字列をまとめて返す最外殻関数
"""
# 1. 入力値の大きい方に合わせて、必要なビット数(n_bits)を自動算出
n_bits = max(val_a, val_b).bit_length()
# 2. 回路を自動ビルド
circuit, b_indices = build_general_adder(val_a, val_b, n_bits)
# 3. 計算（サンプリング）を1回だけ実行
result = circuit.m[:].run(shots=1)
state = list(result.keys())[0]
# 4. レジスタbのインデックスから結果の2進数文字列を抽出
bin_result = ""
for idx in reversed(b_indices):
bin_result += state[idx]
# 5. 10進数に変換
ans_decimal = int(bin_result, 2)
return {
"answer": ans_decimal,
"binary": bin_result,
"n_bits": n_bits,
"total_state": state
}
# --- 非常にシンプルになった実験パート ---
a_in = 10
b_in = 6
# 関数を1回呼び出すだけで、すべてが完了します！
res = run_quantum_adder(a_in, b_in)
print(f"入力値: a = {a_in}, b = {b_in}")
print(f"自動算出された必要ビット数 (n_bits): {res['n_bits']}")
print(f"総量子ビット数 (3n + 1): {3 * res['n_bits'] + 1}")
print(f"全量子ビットの測定結果: {res['total_state']}")
print("-" * 50)
print(f"論文のレジスタb（出力）の2進数: {res['binary']}")
print(f"10進数に変換した答え: {res['answer']}")
5. 実行結果と2つの魔法
このコードを実行すると、以下のような美しい結果が得られます。
入力値: a = 10, b = 6
自動算出された必要ビット数 (n_bits): 4
総量子ビット数 (3n + 1): 13
全量子ビットの測定結果: 0000010100001
--------------------------------------------------
論文のレジスタb（出力）の2進数: 10000
10進数に変換した答え: 16
見事に 10 + 6 = 16 （2進数で 10000）が、全自動生成された13量子ビットの回路によって正しく計算できていますね！
ここで注目すべき、量子ならではの面白いポイントを2つ解説します。
① なぜ shots=1 で大丈夫なの？
一般的な量子アルゴリズム（量子重ね合わせ状態を作るもの）では、答えが確率的に得られるため、何千回も計算を繰り返して統計（ヒストグラム）を取る必要があります。
しかし、今回の加算器回路で使っているのは X, CX, CCX という「状態を反転させるだけのゲート（古典的な論理ゲートと等価なもの）」だけです。最初から最後まで状態が1つに確定しているため、計算（測定）はたったの1回（shots=1）で100%正しい答えが出力されます。
② アンコンピュートによるクリーンアップ
全量子ビットの測定結果の左側、つまりキャリーレジスタ 0000 に戻っている 点に注目してください。
計算の途中、繰り上がりデータを保持するためにキャリービットは一時的に 1 に変化します。しかし、そのまま放置すると、これらの量子ビットは入力データと「もつれ（エンタングル）」した状態のゴミデータになってしまい、後段の計算で量子重ね合わせを正しく干渉させることができなくなります。
そこで、最上位の計算が終わったあとに carry_inv（逆演算）をループで逆順に適用 しています。これにより、驚くべきことに「計算の結果を保ちながら、途中のゴミデータだけを綺麗に消去（初期化）する」という芸当を達成しているのです。これが量子計算における「アンコンピュート（Uncompute）」の真髄です。（もっとも最近は途中測定リセットを使えばいい気もしますが）
💡 量子回路を「関数」にカプセル化するメリット
今回、入力から実行・解析までを run_quantum_adder という1つの関数に閉じ込めました。このようにカプセル化（ブラックボックス化）しておくことで、私たちは「内部で何番目の量子ビットがどう使われているか」を毎回意識する必要がなくなります。
この設計は、次のステップである「剰余加算器（Modulo N Adder）」や、さらに先の「剰余乗算器」を組み立てる際に、この加算器回路を1つの大きなコンポーネント（部品）として再利用するために非常に重要なアプローチとなります。
追記、質問があったのでここでも書いておきます。回路の一番下に謎のCXゲートが一つありますが、これは最後の桁だけ次のキャリーがないので手作業でa+bを実行して解を求めている操作になります。ほかは手順通りでできますが、最上位だけは次のキャリーがないので。
次回予告
これで、ショアのアルゴリズムを構成する最も基本かつ最も汎用的な加算器が完成しました。
この通常の加算器の素晴らしいところは、ゲートをすべて逆順に並べるだけで「減算器（引き算器）」に早変わりする点です。
次回は、この加算と減算を巧みに組み合わせ、設定した数
Discussion