連載「量子ノート」第16回（非技術者でも理解できる量子技術）
量子コンピュータは、今のコンピュータの計算をそのまま速くする機械なのでしょうか？実は、量子の性質を生かす専用の手順「量子アルゴリズム」が必要で、大きく速くなる問題も限られています。
- 量子コンピュータには、重ね合わせや干渉を生かす専用の手順が必要です。
- ショアのアルゴリズムは、繰り返しの周期を見つけて素因数分解を効率化します。
- グローバーのアルゴリズムは、探索の判定回数を件数の平方根程度に減らします。
- 大きく速くなるのは、量子の性質を生かせる一部の問題に限られます。
執筆：弁護士・弁理士 内田誠（iCraft法律事務所）／執筆時点：令和8年9月
計算の「手順」が違う
アルゴリズムとは、問題を解くための手順のことです。料理のレシピのように、どの順番で何をすれば答えにたどり着けるかを定めたものです。
量子コンピュータは、従来のコンピュータのレシピをそのまま速く実行する機械ではありません。重ね合わせや干渉といった量子の性質を生かせる、専用の手順が必要になります。これを「量子アルゴリズム」といいます。有名なものが二つあります。
ショアのアルゴリズム
1994年、アメリカのショアは、大きな数を素因数分解する量子アルゴリズムを発表しました。
その鍵は「繰り返しの周期」を見つけることにあります。例えば15を素因数分解するとき、7を何回も掛けて15で割った余りを調べると、7、4、13、1、7、4……と4つごとに同じ並びが繰り返されます。周期が4と分かれば、7を2乗した49の前後の数である48と50に注目し、それぞれと15の最大公約数を求めると、3と5という答えが得られます。
数が大きくなると、この周期を見つけるのが従来のコンピュータでは極めて難しくなります。量子コンピュータは、干渉を使って周期を効率よく見つけることができます。素因数分解の難しさは、インターネットで広く使われている暗号の安全性の土台になっているため、ショアのアルゴリズムは大きな注目を集めました。
ただし、実際の量子コンピュータで行われたショアのアルゴリズムの実験は、15や21といった小さな数を対象にしたものが代表的です。答えが分かっている数に合わせて回路を大幅に簡略化したものも少なくありません。暗号に使われる大きな数を分解するのに必要な規模とは、大きな開きがあります。
グローバーのアルゴリズム
1996年には、グローバーが「探し物」を速くする量子アルゴリズムを発表しました。
索引などの手がかりがなく、一つずつ条件に合うかを調べることでしか探せない100万件のデータから、条件に合う1件を探すとします。従来の方法では、平均して50万回ほどの確認が必要です。
条件に合うかどうかの判定を量子コンピュータの上で行える場合を考えます。グローバーのアルゴリズムを使うと、判定の回数をデータの件数の平方根、つまり1000回程度に減らせます。ただし、データを量子コンピュータで扱える形に準備する手間や、1回の判定にかかる時間は別に考える必要があります。
この方法は暗号にも影響します。暗号の鍵を総当たりで探す作業も、理論上は速くなるからです。
「共通鍵暗号」とは、送る側と受け取る側が同じ鍵を使う暗号をいいます。日本政府の報告書では、共通鍵暗号について、現在主に使われている128ビット相当の鍵から、より強度の高い鍵への変更を検討する必要があるとしています。実際の脅威の大きさは、必要な量子コンピュータの規模や計算時間にも左右されます。
万能ではない
量子アルゴリズムで大きく速くなるのは、素因数分解や探索、分子のシミュレーションなど、量子の性質をうまく生かせる問題に限られます。どの問題に向いていて、どの問題には向かないのかを見極めることが、量子コンピュータを正しく理解する第一歩です。
よくある質問
- ショアのアルゴリズムで、今すぐ暗号が破られるのですか？
-
実際の実験は15や21といった小さな数を対象にしたものが代表的で、回路を大幅に簡略化したものも少なくありません。暗号に使われる大きな数を分解するのに必要な規模とは、大きな開きがあります。
- グローバーのアルゴリズムは暗号にどう影響しますか？
-
暗号の鍵を総当たりで探す作業も理論上は速くなります。そのため日本政府の報告書では、共通鍵暗号について、128ビット相当の鍵からより強度の高い鍵への変更を検討する必要があるとしています。
- 量子コンピュータはどんな問題でも速く解けるのですか？
-
いいえ。大きく速くなるのは、素因数分解や探索、分子のシミュレーションなど、量子の性質をうまく生かせる問題に限られます。
まとめ
- 量子コンピュータには、重ね合わせや干渉を生かす専用の手順が必要です。
- ショアのアルゴリズムは、繰り返しの周期を見つけて素因数分解を効率化します。
- グローバーのアルゴリズムは、探索の判定回数を件数の平方根程度に減らします。
- 大きく速くなるのは、量子の性質を生かせる一部の問題に限られます。
量子技術に関わる共同研究開発契約・ライセンス契約、特許による技術の保護、外為法規制対応など、具体的な事案については弁護士にご相談ください。iCraft法律事務所でもご相談をお受けしています。
連載「量子ノート」
- 前の記事：第15回 量子アニーリングとは？組合せ最適化を量子のゆらぎで解く仕組み
- 次の記事：第17回 NISQとは？雑音が多い今の量子コンピュータの現在地をやさしく解説
- 連載の一覧：量子ノート（非技術者でも理解できる量子技術）
本記事は、量子技術に関わる業務に携わっている弁護士である筆者が、大学時代の教科書や論文などを読み直し、自分なりの理解をまとめたものです。量子技術の専門家の方からご覧になると、不正確な点があるかもしれませんが、その点はどうかご容赦ください。
更新履歴：令和8年10月 公開（noteで公開した連載を改訂して掲載）
