「量子コンピュータが実用化されると RSA 暗号が解ける」と言われる理由が、ショアのアルゴリズム（Shor's algorithm）です。ただ、論文や解説を読むと、古典計算（普通のコンピュータの計算）と量子計算が入り混じっていて、どこが量子回路の仕事なのかが見えにくくなりがちです。
この連載では、1995 年の論文をたどりながら、ショアのアルゴリズムを実際に量子回路として組み上げていきます。第1回は、アルゴリズム全体の流れと、量子回路が受け持つ部分の構造を整理します。
参考資料：
- Shorのアルゴリズム（スライド）
- Vedral, Barenco, Ekert, Quantum Networks for Elementary Arithmetic Operations（量子回路の組み方はこの論文に沿います）
全体の流れ：量子が受け持つのは真ん中だけ
ショアのアルゴリズムは、すべてを量子コンピュータで計算するわけではありません。「古典の前処理」「量子による位数の発見」「古典の後処理」の3段階でできています。
素因数分解したい数を N とします。
① 古典の前処理
- 2 から N−1 のあいだから整数 x をランダムに選ぶ
- x と N の最大公約数 gcd(x, N) を計算する。1 でなければ、それが N の約数なので終わり
- gcd(x, N) = 1（互いに素）なら、②へ進む
② 量子による位数の発見
- x を r 乗して N で割った余りが 1 になる、最小の正の整数 r を求める。この r を位数（周期）と呼ぶ
③ 古典の後処理
- r が偶数で、かつ x^(r/2) mod N が −1（つまり N−1）でなければ、gcd(x^(r/2) ± 1, N) を計算する
- これで、高い確率で N の自明でない約数が得られる
普通のコンピュータで時間がかかりすぎるのは②です。ここを量子コンピュータに任せる、というのがショアのアルゴリズムの要点です。
位数を見つける量子回路の構成
位数を見つける回路は、2つのレジスタ（量子ビットのまとまり）でできています。
第1レジスタ（制御・読み出し用）
- 役割： 位数 r の情報を位相として受け取り、最後に測定して取り出す
- 量子ビット数： N のビット数の2倍より少し多めにとる。多いほど、r を読み取る精度が上がる
- 初期状態： すべての量子ビットにアダマールゲート（H）を掛け、0 と 1 が同じ重みで重なった状態にしておく
第2レジスタ（計算用）
- 役割： x^j mod N の計算結果を入れる
- 量子ビット数： N を表せるだけ（およそ log₂N）
- 初期状態： 最下位の量子ビットだけ X ゲートで 1 にし、レジスタ全体として |1⟩ にしておく
回路の3つの操作
1. 初期化
第1レジスタを重ね合わせ状態に、第2レジスタを |1⟩ にします。
2. 制御付きべき剰余（Controlled Modular Exponentiation）
第1レジスタの各量子ビットを制御にして、第2レジスタに掛け算を施します。状態 |j⟩|k⟩ を |j⟩|x^j · k mod N⟩ に移す操作です。
ショアのアルゴリズムの中で、いちばん回路が大きく、組むのが難しい部分です。Vedral らの論文は、この掛け算を足し算・剰余の足し算・剰余の掛け算という部品に分け、どれも可逆な（逆向きにたどれる）回路として組む方法を示しています。この連載の中心もここです。
3. 逆量子フーリエ変換（Inverse QFT）
べき剰余によって第1レジスタに乗った周期的な位相を干渉させ、測定したときに出やすい値を位数 r に対応するところへ集めます。
最後に第1レジスタを測定すると、s/r（s はある整数）に近い値が得られます。これを古典の連分数展開にかけて、位数 r を取り出します。
次回：量子加算器を組む
今回は、全体の流れと、量子回路が受け持つレジスタの構成を整理しました。回路の手順そのものは「重ね合わせを作る → べき剰余を掛ける → フーリエ変換で読み出す」の3つです。
次回からは Python の量子計算ライブラリ blueqat SDK を使って、いちばん大きな部品であるべき剰余を、その土台の量子加算器から順に実装していきます。
寄稿は筆者個人の見解です。編集部の見解ではありません。 この媒体はblueqat株式会社が運営しています。
