量子コンピューティングとは？
国際特許分類（IPC）［1］には、量子コンピューティングに関連するカテゴリーが含まれており、「G06N 10/00 量子コンピューティング、即ち量子力学的現象に基づく情報処理」というタイトルが付けられています。
コンピュータを量子コンピュータにする量子力学的現象が「量子ビット」です。
量子ビット（キュービットともいう）は、古典ビットの量子類似物です［2］。古典コンピュータでは、情報は0か1の数値を取るビットで暗号化されます。量子ビットは0と1の二つの基底状態を持ちますが、重ね合わせの原理を用いると、量子ビットは二つの基底状態の線形結合状態にもなります。これが量子ビットとビットを区別する、量子重ね合わせの原理なのです。
さらに量子ビットのグループをもつれ状態にすることも可能であり、その場合、各粒子の量子状態を他の粒子と無関係に記述することはできません［3］。量子ビットをもつれさせることができ、その情報が重ね合わせて保持されるという事実は、量子コンピュータが古典コンピュータよりも遥かに高速で一部の問題を解けることを意味しています。
素因数分解問題
量子コンピュータが古典コンピュータよりも速く解ける問題の例として、素因数分解問題が挙げられます。
素因数分解とは、所与の数値Nについて、掛け合わせるとNになる二つの素数PとQを見つけることです。
Nが小さければ、さほど難しくありません。例えば、N＝6の場合、人間であれコンピュータであれ、PとQが2と3であると簡単に特定できるでしょう。しかし、N = 1,034,776,851,837,418,228,051,242,693,253,376,923の素因数が、P = 1,086,027,579,223,696,553とQ = 952,809,000,096,560,291であると特定するのは、ずっと難しくなります［4］。このようにNの数値が大きくなればなるほど、問題は難しくなっていきます。
なぜこの問題が重要な意味を持つのでしょうか？ なぜなら素因数分解問題は、RSA暗号など、オンラインで情報を保護する一部の暗号システムの基盤として使用されているからです。
RSA暗号
RSAは、素因数分解問題を基盤とする、よく使われている暗号化システムです［5］。
アリスという人物が公開鍵と対応する秘密鍵のキーペアを所有しています。アリスは安全性を損なうことなく、別の人物ボブに公開鍵を公然と配布できます。しかし、アリスは秘密鍵を秘密にしておかなくてはなりません。
ボブはアリスの公開鍵を用いてメッセージを暗号化して、暗号文を生成できます。対応する秘密鍵を知っている人たちだけ（この場合はアリスだけ）が、その暗号文を復号化して元のメッセージを入手できるのです。
このように公開鍵はデータを暗号化するために使用され、秘密鍵は暗号化されたデータを復号化するために使用されます。
アリスとボブが相互に送付するメッセージの暗号化と復号化の双方に共有鍵を用いる技術、ワンタイムパッド技術を補完するために、RSAを用いることができます［6］。ワンタイムパッドは、あらゆる計算能力によるあらゆるコンピュータ攻撃に対して安全です。しかし、この安全性は、アリスとボブの間で共有鍵が秘密に配布されることに依存しています。そうでなければ、盗聴者が共有鍵を入手し、これを用いてアリスとボブの間の以後のメッセージを復号化できるでしょう。
ボブはRSAを用いて、アリスに共有鍵を送付できます。それ以降のアリスとボブとのやりとりは、両者が利用できるようになった共有鍵を使用して、ワンタイムパッド技術により行うことができます。
RSAでは、整数Nは公開鍵の一部であり、対応する素数PとQは秘密鍵の一部です。
したがって、ボブからアリスへのメッセージの安全性は、公開鍵を知っている第三者が秘密鍵を特定できないことに依存しています。つまり、数値Nを知っている第三者が素数PとQを特定できない、言い換えれば素因数分解問題を解けないことが、セキュリティの要となっているのです。
古典コンピュータで実行できる、大きな数値の素因数を効率よく見つけるアルゴリズムは、まだ特定されていません（とはいえ、将来このようなアルゴリズムを発見できる可能性がないという意味ではありません）。そのため、RSAのような暗号システムは、古典コンピュータに対して比較的安全であると考えられています。
しかし、量子コンピューティングの発展が、これらの暗号システムに脅威を及ぼす可能性があるのです。
量子コンピュータ v 古典暗号
ショアのアルゴリズム
1994年にピーター・ショアは、量子コンピュータが多項式時間（コンピュータがこの問題を解くための効率的な時間）で整数の素因数を見つけることを可能にするアルゴリズムを開発しました。ショアのアルゴリズムは、量子ビット特有の量子特性、即ち量子の重ね合わせと干渉を利用することで、これを達成します。
素因数分解問題を解く量子コンピュータの能力は、2001年にIBMの研究者たちが7量子ビットの量子コンピュータを用いて数値15を因数分解した際に、実験的に証明されています［7］。
RSAの一般的な鍵のサイズは2048ビットから4096ビットが標準であるため、RSAに用いられる数値に比べれば、明らかに15は遥かに小さい数値です。しかし、十分な量子ビット数の量子コンピュータが、量子ノイズや他の量子デコヒーレンス現象に負けずに動作できれば、ショアのアルゴリズムを用いてRSA暗号を破ることが可能になります。
量子コンピュータの量子ビット数
IBMは2023年12月に、1000量子ビットを超える史上最大の量子コンピュータ、Condorを発表しました［8］。
ある見積りによれば、2048ビットのRSA鍵を因数分解するために量子コンピュータが必要とする量子ビット数は、2000万量子ビットであり、このような量子コンピュータは８時間でこの計算を完了するということです［9］。
したがって、量子コンピュータの規模が大きくなれば、難解な数学問題に基づく暗号への脅威が高まるため、セキュリティのために素因数分解問題に依拠しない代替技術の開発に関心が寄せられています。
一つの代替技術が、火（量子）をもって火（量子）を制する、つまり「量子暗号」の形で潜在的な解決策を提供するために量子現象を利用することであり、これについては今後の記事で考察していきます。
参考資料
［1］国際特許分類（IPC）は、以下で閲覧可能：
https://www.wipo.int/classifications/ipc/en/
[2] What is a qubit? (quantum-inspire.com)
[3] What is Quantum Computing? | IBM
[5] Rivest, R.; Shamir, A.; Adleman, L. (February 1978). Wayback Machine (archive.org) Communications of the ACM. 21(2): 120–126
[6] Lugrin, Thomas (2023), Mulder, Valentin; Mermoud, Alain; Lenders, Vincent; Tellenbach, Bernhard (eds.), One-Time Pad | SpringerLink Trends in Data Protection and Encryption Technologies, Cham: Springer Nature Switzerland, pp. 3–6
[7] Vandersypen, L., Steffen, M., Breyta, G. et al. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance | Nature Nature414, 883–887 (2001)
[8] IBM’s ‘Condor’ quantum computer has more than 1000 qubits | New Scientist
[9] RSA’s demise from quantum attacks is very much exaggerated, expert says | Ars Technica
この記事は一般的な情報提供のみを目的としており、法的助言を構成するものではありません。この記事または他の主題に関して助言が必要な場合は、hlk@hlk-ip.comまたは担当のHLKアドバイザーまでご連絡ください。