みなさん、こんにちは！ショアのアルゴリズム解説シリーズの第2回です。
前回は、ショアのアルゴリズム全体の流れを掴むために、「N ＝ 15」の素因数分解を手計算で行いました。覚えているでしょうか？
今回からは、いよいよ「一番の難所である『周期 r』を、量子コンピュータを使ってどうやって見つけるのか」という具体的な仕組みに踏み込んでいきます！
今回も、blueqat代表の湊先生の連載ブログをベースに、さらに分かりやすく噛み砕いて解説していきます。
- 参考記事（第1回・第2回）: * ショアのアルゴリズムを量子ゲートで解く(1)
それでは、解説を始めましょう！
量子ゲートで解くためのステップ
ショアのアルゴリズムの基本的なステップは以下のように古典コンピュータと量子コンピュータの役割分担で解きます。前回の「手計算」と同じ問題を、量子ゲートを使って解いていきます。
- ステップ1： 古典コンピュータ（普通のコンピュータ）で適当な数を選ぶ
- ステップ2： 「xのr乗 ≡ 1 (mod N)」を満たす周期 r を量子コンピュータで解く
- ステップ3：古典コンピュータ（普通のコンピュータ）で因数分解して、素因数分解する
前回のブログでお話しした通り、この「ステップ2」こそが、スーパーコンピュータでも何億年もかかってしまう超難所です。今回は、このステップ2を量子コンピュータ上で実行するための「準備（初期状態の作り方）」を見ていきましょう。
2つの役割：「第1レジスタ」と「第2レジスタ」
量子コンピュータで計算を行う際、複数の量子ビットをまとめたグループを「レジスタ」と呼びます。ショアのアルゴリズムでは、役割の異なる2つのレジスタを用意します。
1. 第1レジスタ（量子ビット：乗数を表す）
こちらは、数式における「何乗するか（乗数）」を格納するためのレジスタです。
必要な量子ビット数（m個）は、元の数 N に対して 「2^m ≧ N^2」 を満たす必要があります。
今回は N ＝ 15 を選んでいるので、15の2乗は 225 です。
「2の8乗 ＝ 256」となり、225以上になるため、今回は m ＝ 8個 の量子ビットを用意します。
2. 第2レジスタ（補助ビット：余りを表す）
こちらは、「N で割った余り」を格納するためのレジスタです。
必要な量子ビット数（n個）は、余りの最大値が N 未満になるため、 「2^n ≧ N」 を満たす必要があります。
今回は N ＝ 15 なので、「2の4乗 ＝ 16」となり、15以上を満たします。したがって、こちらは n ＝ 4個 の量子ビットを用意します。
計12個の量子ビットを使って、計算の準備を整えます。
計算を始める前の「初期設定」
レジスタを用意したら、次は量子ゲートを使って、計算を始めるための初期状態を作ります。
① 第1レジスタに「Hゲート（アダマールゲート）」をかける
初期状態の「0」に対してHゲートをかけることで、量子特有の「重ね合わせ状態」を作ります。
今回は8個の量子ビットすべてにHゲートをかけるため、0から255までの「256通りの乗数」がすべて同時に重なり合った状態が作られます。この並列性が、超高速計算の鍵になります。
② 第2レジスタに「Xゲート（NOTゲート）」をかける
第2レジスタの1番最後の量子ビットにだけ、状態を反転させるXゲートをかけます。
これによって、第2レジスタの状態は 「|0001>（つまり 1）」 になります。これは、まだ何も掛け算をしていない状態の「余りは 1」であることを表しています。
※HゲートやXゲートは基本操作なので、AIに聞いたり、他のブログを参照して下さい。基本的にはなるべく簡潔に説明していくので、調べれればすぐ理解できると思います。また、|0001>などはブラベクトルといい、ベクトルです。ベクトルは高校数学の数Bで出てきますが、量子物理学では行列の一環として扱うので、AIに聞いて下さい。基礎的な内容なのですぐ理解できると思います。
次回へのアプローチ
ここまでの準備（初期化）ができたら、いよいよ本格的な量子計算のメイン処理へと進みます。その後に続くステップがこちらです。
- 制御付きモジュロべき乗変換
- 逆量子フーリエ変換（IQFT）
実は、この最後の2つのステップがめちゃくちゃ難しい（ショアのアルゴリズムの最難関）と言われています。
ですので、一気に進まずに、次のブログから一つひとつ順を追って、どこよりも分かりやすく解説していきたいと思います(もちろん湊先生のブログ次第ですが)。
今回はここまでです。次回の解説もぜひお楽しみに！