みなさん、こんにちは！ショアのアルゴリズム解説シリーズです。
前回は、量子計算に入る前の「初期設定（レジスタの準備）」までを解説しました。今回からは、いよいよショアのアルゴリズムの最難関と呼ばれる「制御付きモジュロべき乗変換」の中身に入っていきます。
この「制御付きモジュロべき乗」は非常に複雑なので、何回かのブログに分けてじっくり解説していきます。今回はその基礎中の基礎となる「普通の足し算（Plain Adder）」について、手書きのノート図解を交えながら分かりやすく解説します！これからのショアのアルゴリズムのブログは表記のバグなどを考慮して、パソコンでの参照をお勧めします。
今回も、blueqat代表の湊先生の連載ブログをベースに、さらに分かりやすく噛み砕いて解説していきます。
- 参考記事（第1回・第2回）:
それでは、解説を始めましょう！
モジュロべき乗へのロードマップ
いきなり「モジュロべき乗」の量子回路を作ることはできません。実は、以下のように一番簡単な計算から順番に積み上げていく階層構造になっています。
- 普通の足し算（Plain Adder） ★今回はココ！
- モジュロ足し算
- モジュロ掛け算
- モジュロべき乗
今回は、すべての土台となる「ステップ1：普通の足し算（Plain Adder）の確認」を行います。
量子回路で足し算を作るために、以下の3種類の量子ゲートを使用します。
- ① Xゲート（ビット反転）
- ② CXゲート（制御NOT）
- ③ CCXゲート（トフォリゲート：2つの制御ビットを持つ）
※この3つの量子ゲートも基礎なので、AIに聞いたりすればすぐわかると思います。
ステップ1：量子ゲートの流れ
- まず、足し算の量子回路を作ります
- 足し算の結果を量子ビットに反映(往路)
- 足し算する際に使った補助量子ビットのゴミを掃除してリセットする(復路)
ステップ2：手計算の筆算と量子コンピュータの比較
まずは、私たちが普段やっている計算を2進数の筆算で確認してみましょう。「10 ＋ 6 ＝ 16」を例にします。
10 は2進数で「1010」、6 は「0110」です。これを筆算で足すと次のようになります。
１１００ ←この筆算のメモを「carry（繰り上がり）」と呼ぶ
１０１０
＋０１１０
ーーーーー
１００００
この一番上にメモした「1100」という繰り上がりの情報（carry）が、量子コンピュータで計算する際に非常に重要な役割を果たします。
量子レジスタの構成と「3n＋1」の法則
先ほどの筆算を、量子ゲートで表すための準備をします。量子ビットを役割ごとに3つの「レジスタ」に分けます。
- レジスタa（元の数）： a3, a2, a1, a0 （今回は 1 0 1 0）
- レジスタb（足す数）： b4, b3, b2, b1, b0 （今回は 0 0 1 1 0）※一番上の b4 は、計算結果が繰り上がって桁が増えた時（16＝10000など）のために用意しておきます。
- レジスタc（carry）： c4, c3, c2, c1 （初期値は 0 0 0 0）
今回は、4ビットの足し算をするために、全部で 13個の量子ビット を使っています。
公式化すると、nビットの足し算をする場合、
n（レジスタa） ＋ (n＋1)（レジスタb） ＋ n（レジスタc） ＝ 3n ＋ 1 個 の量子ビットが必要になります。
ここで重要なポイントがあります。
計算結果は「レジスタb」に表れます。しかし、量子コンピュータの限られたビット数を節約するため、使い終わった「レジスタc」はリセットして、なるべく再利用したいのです。
ステップ3：量子コンピュータで筆算（往路）
いよいよ計算スタートです。まずは繰り上がりを計算していく「往路（Forward Path）」です。
b3 までは、a(i), b(i), c(i) の各ビットを CCXゲート にかけることで、筆算の繰り上がり（carry）が計算できます。
往路の計算が終わると、レジスタの状態は次のようになります。
- レジスタa： 1 0 1 1
- レジスタb： 0 0 1 1 0
- レジスタc： 1 1 0 0
実際の量子回路で表すと下の図のようになります。
赤字で「a0 ＋ b0 ＝ c1」などと書かれているように、順番に繰り上がりを計算して次の桁に渡していきます。
ここで図の右下（オレンジの丸）に注目してください。
「最後の桁だけ違う！」とあるように、一番上の桁上がりを受け取る b4 だけは、少し異なるゲートの組み方（b3, c4を使ったCCXゲート）になります。
ステップ4：答えの反映と「ゴミ掃除」（復路）
往路で計算した結果をレジスタbにしっかり反映（代入）させつつ、用済みになったレジスタcの数値を「0」にリセットする工程に入ります。これを「復路（Backward Path）」または「ゴミ掃除（Uncompute）」と呼びます。
この復路の計算ルールは「XOR（排他的論理和）」です。
ルールはシンプルで、同じ桁の aとbとcを見て、1の数が「奇数個」なら 1、「偶数個」なら 0 を、対応する b に上書きします。
具体的に見ていきましょう。最上桁の b4 は往路ですでに固定されているので、b3 から下に向かって考えます。
- b3 の場合： a3＝1, b3＝0, c3＝1 です。1が2個（偶数個）なので、b3 は 0 になります。
- b2 の場合： 1つ桁を降りたところからゴミ掃除が始まります。a2＝0, b2＝1, c2＝1 より、1が2個（偶数個）なので、b2 ＝ 0 です。
[画像: image_4.png をここに挿入]
b2 が確定すれば、もうその上の繰り上がり情報 c4 は使わないため、量子ゲートを「逆向き（逆順）」に掛けていくことで、安全に 0 にリセット（ゴミ掃除）することができます。
さらに下の桁も同様です。
- b1 の場合： b2と同様に計算して b1＝0 となり、c2が掃除されます。
- b0 の場合： b0＝0 となり、c1が掃除されます。
復路の量子回路図を見てみよう
「XORは2つのCXゲートで表せる」のですが、言葉だけでは「ゴミ掃除で量子ゲートを逆に掛ける」というイメージが湧きにくいと思います。そこで、最後の図を見てください。
赤枠で囲まれた部分が「往路の逆順でゴミ掃除」をしている部分です。往路で作ったもつれ（絡み合い）を、鏡合わせのように逆の手順で解いていくことで、量子状態を壊さずにビットを 0 に戻すことができます。
また、右上のオレンジの丸で囲まれた部分にあるように、復路でも「最初の桁だけ違う！」構成になっている点に注意してください。
まとめ
いかがでしたでしょうか？
今回はショアのアルゴリズムの心臓部であるモジュロべき乗に向けた第一歩、「普通の足し算（Plain Adder）」の仕組みを解説しました。
- 計算には元の数、足す数、繰り上がり（carry）の 3n＋1 個 の量子ビットを使う。
- 往路で CCX ゲートを使って繰り上がりを計算する。
- 復路で XOR のルールに従って結果を代入し、不要になった carry を逆演算でゴミ掃除する。
量子コンピュータは「計算して終わり」ではなく、再利用のために「綺麗に元に戻す（ゴミ掃除）」プロセスが非常に重要だということが分かっていただけたかと思います。
湊先生のブログではこれをblueqat SDK を使用して、コードで表記しています！実行をお勧めします！
次回は、この Plain Adder をベースにして、特定の数で割った余りを求める「モジュロ足し算」へとステップアップします！お楽しみに！