みなさん、こんにちは！ショアのアルゴリズム解説シリーズです。
前回は、モジュロべき乗に向けた第一歩として「普通の足し算（Plain Adder）」の仕組みを完成させましたね 。今回は、それをさらに進化させた「モジュロ足し算（別名：剰余加算器 / Adder modulo N）」を作っていきます 。
モジュロ足し算の最大の壁は、一言でいうと「『if文（条件分岐）』を量子回路でどうやって表すか」という点にあります 。 今回も、じっくり丁寧に解説していくので、ぜひついてきてくださいね！
今回も湊先生の非常にわかりやすい記事をさらにわかりやすく分解してみました。
以下のリンクから今回参照した湊先生のブログにアクセスできます:
https://zenn.dev/yuichirominato/articles/71b1410a8c7a44
そもそもモジュロ足し算とは？
今回私たちが作りたいのは、次のような計算ができる回路です。
- a ＋ b (mod N)
これは、「aとbを足した結果を、Nで割った余り」を求める計算です。 例えば、N ＝ 11、a ＝ 7、b ＝ 6 の場合、7 ＋ 6 ＝ 13 となり、11で割った余りである 「2」 を出力しなければなりません 。
普通のコンピュータ（古典コンピュータ）でプログラムを書くなら、とても簡単です。
- まず、普通に足し算をする（ans ＝ a ＋ b）
- もし（if）、答えが N 以上だったら（if ans ≧ N:）
- 答えから N を引く（ans ＝ ans － N）
- 答えを出力する（return ans）
しかし、量子コンピュータは「複数の状態が同時に重なり合っている（重ね合わせ）」ため、途中で「Nより大きいか？」をチェックして処理を分岐させるのが非常に困難です 。
そこで量子コンピュータでは、「とりあえずNを引いてみて、間違っていたら後で足し直す」という、少し力技のような面白いアプローチを使います！
必要な量子ビット数（レジスタ）の確認
前回の「普通の足し算（Plain Adder）」では、レジスタa（nビット）、レジスタb（n＋1ビット）、レジスタc（nビット）の合計「3n ＋ 1 ビット」を使いました 。
今回のモジュロ足し算では、さらに以下のレジスタが追加されます。
- 定数 N を表す 「レジスタN」 （nビット）
- 条件分岐の要となる 「フラグt」 （1ビット）
- 複雑なゲートを動かすための補助ビット 「ancilla」 （1ビット）
これらをすべて合わせると、モジュロ足し算に必要な量子ビット数は 「4n ＋ 3 ビット」 となります 。それでは、具体的な5つのステップを見ていきましょう。
ステップ1：まずは普通に足し算をする
最初はシンプルです。前回の「Plain Adder」の回路をそのまま使い、レジスタa、レジスタb、レジスタcを使って 「a ＋ b」 を計算し、その結果をレジスタbに格納します 。
ステップ2：とりあえず「N」を引いてみる（減算器）
次に、答えがマイナスになっても構わないので、とりあえずレジスタbから定数Nを引きます。つまり 「b － N」 の計算です 。
足し算の回路があるなら、引き算の回路（減算器）も作れるはずですよね。実は、量子回路の素晴らしい性質を利用すると、減算器は加算器の裏返しで作ることができます。
- 減算器の往路 ＝ 加算器の復路の逆順
- 減算器の復路 ＝ 加算器の往路の逆順
※回路図では、前回の「a」の役割が「N」に置き換わっているだけです 。また、ブロックの順番も逆順になります 。
ステップ3：符号をチェックして「フラグt」に記録する
ステップ2で N を引いた結果は、以下の2つのパターンのどちらかになります 。
- ① もともと a ＋ b ≧ N だった場合： Nを引いても「a ＋ b － N ≧ 0」となり、マイナスになりません 。このとき、レジスタbの最上位の桁（b[n]）は 「0」 になります 。
- ② もともと a ＋ b ＜ N だった場合（引きすぎた場合）： Nを引くとマイナスになってしまいます 。このとき、レジスタbの最上位の桁（b[n]）は 「1」 になります 。
つまり、最上位の桁である b[n] が「0」か「1」かを確認すれば、Nを引くべきだったかどうかが分かるというわけです 。
しかし、b[n] は計算結果の一部としてそのまま使う大事な値なので、直接操作してぐちゃぐちゃにしてはいけません 。そこで、CXゲート（制御NOTゲート）を使って、b[n] の情報を「フラグt」にコピーします 。 これで、フラグt が「if文」の役割を果たしてくれます！
ステップ4：引きすぎた場合だけ「N」を足し戻す
フラグt が「1（引きすぎた）」のときだけ、引いてしまった N を足し戻して「a ＋ b」に戻したいですよね 。
これを量子回路で実現するには、足し算の量子回路のすべてのゲートに、「tが1のときだけ発動する」という条件を追加します 。
- a0 と b0 の CXゲート は、t を追加して CCXゲート（t, a0, b0） に進化します 。
- a0, b0, c1 の CCXゲート は、t を追加して CCCXゲート（t, a0, b0, c1） に進化します 。
「CCCXゲートなんてあるの？」と思うかもしれませんが、これは「ancilla（補助ビット）」を使うことで、以下のように通常のCCXゲートを組み合わせて作ることができます 。
- t と a0 で CCXゲートをかけ、結果を ancilla に。
- その ancilla と b0 で CCXゲートをかけ、c1 に。
- 再び t と a0 で CCXゲートをかけ、ancilla を元に戻す（ゴミ掃除）。
このステップを踏むことで、引きすぎた状態から N が足し戻され、「a ＋ b － N ＋ N ＝ a ＋ b」という正しい状態に修復されます 。
ステップ5：フラグt の「ゴミ掃除」
これで計算自体は完璧なのですが、量子コンピュータ特有の厄介な問題が残っています。前回の「carry」と同様に、使った「フラグt」をきれいに「0」に戻す（ゴミ掃除する）必要があるのです 。
しかし、ステップ4でレジスタbの中身をいじってしまったため、単純にステップ3の逆（CXゲートをもう一度かける）をやっても、t は元に戻りません 。
そこで、天才的なトリックを使います。
トリックの全貌
① まず、レジスタb から「a」を引く（b ＝ b － a） わざと「a」を引くことで、ステップ3の直前と似た状況を作り出します 。
- t ＝ 0 だった場合： ステップ4で何も足されていないので、現在の b は「a ＋ b － N」。そこから a を引くので「b － N」になります 。
- t ＝ 1 だった場合： ステップ4で N が足し戻され、現在の b は「a ＋ b」。そこから a を引くので「b」になります 。
※補足：重要なのは「aを引くことで最上位ビットの状況がステップ3の逆転になる」ということです。具体的には、t=0のときは b[n]=0、t=1のときは b[n]=1 という、ステップ3の判定時と全く同じ状態が、レジスタbの最上位桁に復元されます 。
② フラグt をリセットする これで b[n] の状態が元に戻ったので、安心して逆演算ができます 。 ステップ3と同じように、b[n] を制御ビットとして t に CXゲート をかけることで、t は無事に「0」にリセットされます！
③ 最後に「a」を足し直して元に戻す
- t ＝ 0 のルート：一時的に「b － N」になっていたので、a を足して本来の「a ＋ b － N」に戻ります 。
- t ＝ 1 のルート：一時的に「b」になっていたので、a を足して本来の「a ＋ b」に戻ります 。
全体の流れのおさらい
ステップ5のゴミ掃除の流れをまとめると、以下の3ステップになります 。
- a を引く
- b[n] と t で CXゲート をかける（t のリセット）
- a を足す
まとめ
いかがでしたでしょうか？モジュロ足し算の仕組みは非常に複雑ですが、以下のポイントを押さえておけば大丈夫です。
- 古典コンピュータの「if文」の代わりに、「とりあえず引いて、ダメなら足し戻す」という手法を使う。
- その判定結果を保存するために「フラグt」を使う。
- 最後にフラグtを安全にゴミ掃除するために、「aを引いてから元に戻す」という工夫をする。
次回は、このモジュロ足し算をさらに繰り返して実現する「モジュロ掛け算」について解説していきます。ショアのアルゴリズム完成まであと少しです！お楽しみに！