量子コンピュータは AP にも基礎理論として出題されるようになりました。原理は深入りせず『何ができるか』を押さえましょう。
砂原 ニコ
量子コンピュータって、結局なに?
鳴海 理央
量子ビット (qubit) を使う計算機です。
古典ビットが 0/1 のどちらかなのに対し、量子ビットは 量子もつれ と重ね合わせで 0 と 1 を同時に取れる、という性質を持ちます。
緒方 ナオミ 先生
量子コンピュータの何が嬉しいかというと、特定の問題、たとえば素因数分解の Shor のアルゴリズムや、データベース検索の Grover のアルゴリズムでは古典より高速なのよ。
暗号理論 に直接影響してくるの。
藤咲 まりあ
えぇっ、じゃあ RSA が破られちゃうんですかぁ?
鳴海 理央
理論的には Shor のアルゴリズムで RSA は破られます。
だから今、耐量子計算機暗号 (PQC) の標準化が進められているところで、NIST が CRYSTALS-Kyber などを標準化しました。
緒方 ナオミ 先生
AP では『量子コンピュータが従来の PC より速く解ける問題は何か』『耐量子暗号への移行が必要な理由』あたりが問われやすいわね。
確認クイズ
量子コンピュータが古典コンピュータより劇的に高速に解けるとされる代表的な問題はどれか。
- 整列 (ソート)
- 素因数分解 (Shor のアルゴリズム)
- 二分探索
- ハッシュ計算
こたえを見る
正解: 2. 素因数分解 (Shor のアルゴリズム)
Shor のアルゴリズムは素因数分解を量子コンピュータ上で多項式時間で解きます。古典コンピュータでは現状最速でも準指数時間が必要。RSA など素因数分解の困難性に基づく暗号を破る可能性があるため、耐量子暗号への移行が議論されています。