ショアのアルゴリズムをQiskitで実装｜位数発見でN=15を素因数分解する

量子アルゴリズム入門で「ショアは素因数分解を高速化し、現在の暗号を脅かす」と紹介しました。この記事はその実装版。似た名前の「ショア符号」は誤り訂正の話でまったくの別物なので要注意——今回扱うのは素因数分解のアルゴリズムそのものです。Qiskitで実際に回路を組み、N=15を素因数分解するところまで手を動かします¹。

ショアのアルゴリズムは何をしているのか

素因数分解 N = p × q を直接解くのではなく、**位数発見（order finding）**という数論の問題に置き換えて、その部分だけを量子コンピュータに解かせます²。

量子コンピュータが担当するのは②だけです。①③④はすべて古典コンピュータの仕事という点が、初めて見ると意外なポイントです。

準備

pip install qiskit qiskit-aer numpy

① 古典の下ごしらえ：aを選ぶ

import math
import random

N = 15

def pick_a(N):
    a = random.randint(2, N - 1)
    g = math.gcd(a, N)
    if g != 1:
        print(f"a={a} はNと公約数{g}を持つ→運良く量子計算なしで素因数が見つかった！")
        return None
    return a

面白いことに、選んだ a がたまたま N と公約数を持てば、その時点で素因数の1つが見つかってしまいます（量子計算すら不要）。今回はこの「運の良いケース」を避けて、a=7（gcd(7, 15)=1）で位数発見の本編に進みます。

② 位数を求める量子回路

かけ算 |y⟩ → |a·y mod N⟩ を実装するユニタリ U を作り、これに**量子位相推定（QPE）**をかけます³。今回は置換行列を直接組み立てる、素直で見通しの良いやり方にします。

import numpy as np
from qiskit.circuit.library import UnitaryGate

def build_controlled_U(a_power, N=15, n_qubits=4):
    """|y> -> |a_power * y mod N> を実現する制御ユニタリを作る"""
    dim = 2 ** n_qubits
    perm = np.zeros((dim, dim))
    for y in range(dim):
        if y < N:
            perm[(a_power * y) % N, y] = 1
        else:
            perm[y, y] = 1  # N以上の未使用の状態はそのまま(ユニタリ性を保つため)
    gate = UnitaryGate(perm, label=f"×{a_power} mod {N}")
    return gate.control()

ここに一工夫あります。QPEでは U、U²、U⁴、U⁸……と2のべき乗回だけ繰り返し適用する必要がありますが、「かけ算をk回繰り返す」ことは「aᵏ mod N を1回かける」ことと数学的に同じです⁴。そこで U を物理的に2ⁱ回繰り返す代わりに、pow(a, 2**j, N)（高速な繰り返し二乗法）で指数を先に計算し、その置換を直接組み立てます。

def qft_dagger(n):
    """逆量子フーリエ変換（QFTの記事参照）"""
    qc = QuantumCircuit(n, name="QFT†")
    for qubit in range(n // 2):
        qc.swap(qubit, n - qubit - 1)
    for j in range(n):
        for m in range(j):
            qc.cp(-np.pi / float(2 ** (j - m)), m, j)
        qc.h(j)
    return qc

回路全体を組み立てます。

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

n_count = 3   # 精度レジスタ(位数r=4なら3ビットで十分)
N, a = 15, 7

qc = QuantumCircuit(n_count + 4, n_count)
qc.h(range(n_count))     # 精度レジスタを重ね合わせに
qc.x(n_count)            # 標的レジスタを|1>に初期化

for j in range(n_count):
    exponent = pow(a, 2 ** j, N)
    U = build_controlled_U(exponent, N)
    qc.append(U, [j] + list(range(n_count, n_count + 4)))

qc.append(qft_dagger(n_count), range(n_count))
qc.measure(range(n_count), range(n_count))

result = AerSimulator().run(qc, shots=2000).result()
counts = result.get_counts()
print(counts)

{'000': 498, '010': 512, '100': 486, '110': 504}

n_count=3 ビットなので、8通り中4通り（000, 010, 100, 110）にほぼ均等（各25%）に分かれました。これは位数 r=4 のとき理論的に現れる位相 k/4（k=0,1,2,3）を8ビットの分解能で表した値です。

③④ 古典の後処理：位数を復元し、因数を取り出す

from fractions import Fraction

measured = "010"   # 例として1つの測定値を取り出す
phase = int(measured, 2) / (2 ** n_count)
frac = Fraction(phase).limit_denominator(N)
r = frac.denominator
print(f"測定値 {measured} → 位相 {phase} → 周期候補 r={r}")

if r % 2 == 0 and pow(a, r // 2, N) != N - 1:
    guesses = [math.gcd(pow(a, r // 2, N) - 1, N),
               math.gcd(pow(a, r // 2, N) + 1, N)]
    print("素因数の候補:", guesses)

測定値 010 → 位相 0.25 → 周期候補 r=4
素因数の候補: [3, 5]

15 = 3 × 5 が、量子回路の測定結果とgcdだけから求まりました。ただし測定値が 000 の場合は r=1（自明な結果）になり、100 の場合は r の候補が2（偶数だが a^(r/2) mod N が N-1 になり失敗）になるなど、1回の実行で必ず成功するわけではありません。理論上の成功確率はおよそ50%以上とされており⁵、失敗したら a を変えて（または同じ a で）やり直すのが実際の使い方です。

なぜ位数発見で素因数分解できるのか

r が偶数で a^(r/2) ≢ -1 (mod N) のとき、N は (a^(r/2)-1)(a^(r/2)+1) を割り切りますが、そのどちらか片方だけでは割り切れません⁶。つまり N の素因数は、この2つの数と N それぞれの最大公約数の中に分散して隠れています。gcdという古典コンピュータが一瞬で計算できる操作だけで、隠れていた素因数を取り出せるというのが、この手続きの美しいところです。

まとめ

• ショアのアルゴリズムは素因数分解を「位数発見」に還元し、その部分だけを量子回路（QPEの応用）で解く
• 位数rが求まれば、gcd(a^(r/2)±1, N)という古典計算だけで素因数が取れる
• 1回の実行で必ず成功するわけではなく、確率的に何度か試行が必要
• 実機での実証は2001年のN=15（NMR）以来続いているが、多くは事前に答えを知った上での簡略回路
• 2025年の資源見積もりの大幅な改善や2026年の論理量子ビットでの実証など、じわじわと現実に近づいている

もう少し詳しく（背景と理論）

ショアのアルゴリズムが古典に対して指数的な高速化を実現できる理由は、素因数分解が**隠れ部分群問題（Hidden Subgroup Problem）**という、量子フーリエ変換と相性の良い数学的構造を持つためです⁸。古典コンピュータで数論的変換（離散フーリエ変換）を行うにはO(N log N)回の演算が必要ですが、量子フーリエ変換はO(n²)個のゲート（nは量子ビット数、N=2ⁿ）で実現できます。ただし量子状態の振幅を直接読み出すことはできないため、この高速な変換を「周期発見」という具体的な問題にうまく落とし込んだ点がショアの功績です¹。同じ隠れ部分群問題の枠組みは離散対数問題（楕円曲線暗号を含む）にも応用でき、量子時代のセキュリティで触れた「耐量子暗号への移行」が急がれる理由の根底にあります。

次の一歩 🌸

アルゴリズムの全体像は量子アルゴリズム入門、部品となる変換は量子フーリエ変換をQiskitで実装・量子位相推定をQiskitで実装、暗号への影響は量子時代のセキュリティへどうぞ。誤り訂正の「ショア符号」は名前が似ているだけの別物です→ショア符号をQiskitで実装。

Footnotes

1. Shor, P. W. (1994/1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer." SIAM J. Comput., 26(5), 1484–1509. 量子フーリエ変換による周期発見を核とする素因数分解アルゴリズムを提案。 ↩ ↩²

2. 素因数分解は「aのNを法とする位数r（aʳ≡1 mod Nとなる最小の正整数）を求める」問題に古典的に還元できる。この還元自体は量子力学を必要としない、純粋な数論の議論。 ↩

3. 位数発見は、ユニタリU|y⟩=|ay mod N⟩の固有値（位相）を量子位相推定（QPE）で読み取る問題として定式化できる。Uの固有値はe^(2πik/r)(k=0,...,r-1)の形を取り、位相からrが復元できる。 ↩

4. Uを|y⟩→|ay mod N⟩と定義すると、Uをk回適用したUᵏは|y⟩→|a^k・y mod N⟩に等しい。すなわちUᵏは「aᵏ mod Nを1回かける」操作と数学的に同一の置換になる。 ↩

5. 位数rが偶数かつa^(r/2)≢-1 (mod N)となる確率は、Nが2つの奇素数の積である場合、選んだaについて少なくとも1/2以上であることが理論的に示されている。 ↩

6. a^r≡1 (mod N)よりNはa^r-1=(a^(r/2)-1)(a^(r/2)+1)を割り切る。a^(r/2)≢±1 (mod N)であれば、Nはこの2つの因子のどちらか片方だけを割り切ることはできず、Nの素因数は2つの因子に分散して隠れているため、gcdで取り出せる。 ↩

7. 小規模な実機実証の多くは、あらかじめ既知の位数を前提に回路のゲート数を大幅に削減した「コンパイル済み」回路を使っており、任意のNに対して汎用的に動作する回路の実証とは区別する必要がある、という指摘が学術コミュニティでたびたびなされている。 ↩

8. Jozsa, R. (2001). "Quantum factoring, discrete logarithms, and the hidden subgroup problem." Computing in Science & Engineering, 3(2), 34–43. 素因数分解と離散対数問題を統一的な「隠れ部分群問題」として整理した解説。 ↩