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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

まとめ

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

次の一歩 🌸

実際にコードで動かすならQiskit入門、暗号の話は量子時代のセキュリティへどうぞ。