量子アルゴリズム入門｜ショアとグローバーは何がすごいのか

量子コンピュータが「速い」と言われるのは、ハードウェアだけの話ではありません。量子ならではの解き方＝量子アルゴリズムがあってこそ。その代表格2つを、数式なしで紹介します。

大前提: なんでも速くなるわけではない

まず釘を刺しておきます。量子アルゴリズムが古典を上回るのは、問題の構造が量子に合っているときだけです。「量子コンピュータに載せれば何でも速くなる」わけではありません。

ショアのアルゴリズム: 暗号を脅かす

大きな数を素因数分解する（例: 15 = 3 × 5 を、けた数の多い数で行う）アルゴリズムです。

なぜ重要かというと、現在のインターネット暗号（RSA）の安全性は「大きな数の素因数分解は事実上不可能」という前提に立っているからです。古典コンピュータでは数千年かかる分解を、十分大きな量子コンピュータなら現実的な時間で解けてしまう可能性があります。

グローバーのアルゴリズム: 探索を速く

大量のデータから目的の1件を探すアルゴリズムです。

電話帳から名前だけを頼りに番号を探すような「しらみつぶし探索」を考えます。古典では平均で全体の半分を調べる必要がありますが、グローバーはおおよそ平方根の回数で見つけられます。

• 100万件の探索 → 古典は平均50万回、グローバーは約1,000回
• けた違いですが、ショアほど劇的（指数的）ではなく「二次高速化」です

最適化やデータベース検索など応用範囲が広いのが魅力です。

実用寄りのアルゴリズムたち

ショアやグローバーは「完成した大規模量子コンピュータ」が前提ですが、NISQ期の今でも使える現実的なアルゴリズムも研究されています。

• VQE — 分子のエネルギーを求める。創薬・材料で期待
• QAOA — 組合せ最適化を近似的に解く。物流・金融で期待

これらは「量子と古典を組み合わせて動かす」ハイブリッド型で、今すぐ試せるのが特徴です。

まとめ

• 量子アルゴリズムが速いのは「問題が量子に合うとき」だけ
• ショア＝素因数分解を高速化。現在の暗号を脅かすため耐量子暗号へ移行中
• グローバー＝探索を二次高速化。応用範囲が広い
• NISQ期の今はVQE・QAOAなどハイブリッド型が現実的

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

量子アルゴリズムの「速さ」は計算量クラスの言葉で整理されます。ショアの素因数分解は古典の最良既知アルゴリズム（数体ふるい法、準指数時間）に対し多項式時間を与える指数的高速化で¹、これが現行のRSA暗号を脅かします。一方グローバーの探索は二次高速化にとどまり、これは探索問題の下限（Ω(√N)）から最適であることが証明されています²。「量子は何でも指数的に速い」わけではなく、問題の代数的構造（隠れた周期性など）を突けるときに大きな加速が出る、というのが要点です³。

次の一歩 🌸

実際にコードで動かすなら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. Bennett, Bernstein, Brassard, Vazirani (1997) が探索の下限 Ω(√N) を示し、グローバーがオーダー最適であることが分かった。二次高速化なので、指数加速のショアとは質的に異なる。 ↩

3. 量子多項式時間で解けるクラスは BQP と呼ばれる。BQP と古典の P・NP の正確な関係は未解決だが、素因数分解のように「NP に属するが NP完全とは思われない」構造的な問題で量子の優位が期待されている。 ↩