ゼロから学ぶショアのアルゴリズム（第1回）：アルゴリズムの全体フローと量子回路の役割
1. はじめに
近年、誤り耐性量子コンピュータ（FTQC）の実現に向けた研究が進む中で、再び大きな注目を集めているのが「ショアのアルゴリズム（Shor's algorithm）」です。
「量子コンピュータが実用化されるとRSA暗号が解けてしまう」と言われる理由が、このアルゴリズムにあります。
しかし、論文や解説スライドを読んでも、複雑な数式や古典計算（普通のコンピュータの計算）と量子計算が入り混じっており、具体的に「どこが量子回路の役割なのか」が分かりにくく感じることがあります。
そこで本連載では、昔の文献を紐解きながら、ショアのアルゴリズムを実際に量子回路として実装することを目指します。第1回となる今回は、アルゴリズム全体の流れを整理し、量子回路が担当する「核心部分」の構造を明らかにします。
参考資料は、
Shorのアルゴリズム
量子回路の実装はちょっと昔ですが、基本に戻って、
Quantum Networks for Elementary Arithmetic Operations
2. ショアのアルゴリズム：全体の処理フロー
ショアのアルゴリズムは、すべてを量子コンピュータで計算するわけではありません。「古典前処理」「量子位数発見」「古典後処理」の3つのステップを組み合わせることで、高速な素因数分解を実現しています。
素因数分解したい数を
- 【古典前処理】
-
2 N-1 x -
x N \text{GCD}(x, N) - 互いに素（
\text{GCD}=1
- 【量子計算（核心）】
-
x^r \equiv 1 \pmod N r
- 【古典後処理】
- 得られた位数
r x^{r/2} \equiv -1 \pmod N \text{GCD}(x^{r/2} \pm 1, N) - これにより、高確率で
N
この中で、従来のコンピュータでは膨大な時間がかかってしまうのが 「2. 位数（周期）の発見」 です。ここを量子コンピュータにバトンタッチするのがショアのアルゴリズムの本質です。
3. 資料から抽出した「量子位数発見回路」の基本構造
では、この位数発見を行う量子回路はどのような構成になっているのでしょうか。資料に基づくと、回路は大きく2つのレジスタ（量子ビットのグループ）に分かれています。
① 第1レジスタ（制御・精度用レジスタ）
-
役割： 位数
r -
ビット数（
t N -
初期状態： すべての量子ビットにアダマールゲート（H）を適用し、均等な重ね合わせ状態（
|0\rangle + |1\rangle
② 第2レジスタ（標的・計算用レジスタ）
-
役割： モジュロべき乗（
x^j \bmod N -
ビット数：
N \approx \log_2 N -
初期状態： 最初の1ビット目（最下位ビット）だけをXゲートで
|1\rangle |0\rangle |1\rangle
4. 量子回路を構成する3つのステップ
この2つのレジスタに対して、回路は以下の順番でゲート操作を行います。
- 初期化（Initialization）
- 第1レジスタを重ね合わせ状態にし、第2レジスタを
|1\rangle
- 制御付きモジュロべき乗変換（Controlled Modular Exponentiation）
- 第1レジスタの各ビットを制御ビットとして、第2レジスタにユニタリ変換
U_{x,N} |j\rangle|k\rangle \rightarrow |j\rangle|x^j \cdot k \bmod N\rangle - この部分は、ショアのアルゴリズムの中で最も回路規模が大きく、実装が難しい（時間とメモリを消費する）パートです。Vedralらの論文でも、このモジュロ加算器や乗算器をいかに効率よく reversible（可逆）に組むかが議論されています。
- 逆量子フーリエ変換（Inverse QFT）
- モジュロべき乗によって生じた周期的な「位相」を干渉させ、特定の確率にピークを絞り込むために、第1レジスタに対して逆量子フーリエ変換を行います。
この後、第1レジスタを測定することで、ランダムに値が得られます。その値を古典的な「連分数アルゴリズム」にかけることで、目的の位数
5. 次回予告：blueqat SDKで回路を組んでみよう
今回は、ショアのアルゴリズムの全体フローから、量子回路が担当するレジスタの構成までを整理しました。
数式だけを見ると難解ですが、「状態を作って、モジュロ乗算をして、フーリエ変換で引き出す」という回路のステップ自体は非常に綺麗に整理されています。
次回は、この中の「逆量子フーリエ変換（IQFT）」**や、汎用的な位数発見回路を、Pythonの量子計算ライブラリ blueqat SDK を使って実際に1ステップずつ実装・シミュレーションしていきます！お楽しみに！
Discussion