ショアのアルゴリズムとは？

定義：1994年、MITの数学教授であるピーター・ショアは、古典的なコンピュータよりもはるかに効率的に大きな数の素因数を生成するための量子アルゴリズムを考案しました。ショアのアルゴリズムは、整数の素因数を多項式時間で解くことができる量子コンピュータのアルゴリズムです。これにより、O(logN ^3)時間とO(logN)空間の素数を因数分解することができます。

ショアのアルゴリズムについて

素因数を見つけることは、何世紀にもわたって困難な問題でした。因数分解問題は、コンピュータサイエンスにおける未解決問題の一つです。51の素因数を見つけるには数秒かかるかもしれませんが、100桁の数の素因数を見つけるには、複数の従来のコンピュータを並列に使用して因数分解するのに数年かかるかもしれません。

クレジットカードや同様の金融取引のセキュリティに使用される多くの暗号化アルゴリズムは、この「フ因数分解問題」を利用することで利益を得ています。この因数分解の問題が解決できれば、RSAのような暗号化アルゴリズムの解読も可能だと考えられているのです。1台の量子コンピュータでショアのアルゴリズムを実行することで、この問題を簡単に解決することができます。

ショアのアルゴリズムは、大きな量子ビットの集合を持つコンピュータでのみ動作します。さまざまな量子システムにおいて、ショアのアルゴリズムの実装が試みられていますが、数個の量子ビットで実装できるまでに至ったものはありません。ショールのアルゴリズムは、現在知られている量子コンピュータのアルゴリズムの中で、最も難易度が高いもののひとつであると言われています。このアルゴリズムは、量子コンピュータで実現することができます。

多くの暗号化方式は、大きな数の因数分解は多項式時間では不可能であることを前提としています。それが可能であれば、RSAのような暗号化アルゴリズムが解読されていたかもしれません。そのため、ポスト量子暗号や量子ハッキングといった新しい概念が台頭してきています。

ショアのアルゴリズムは、1024ビットの数値を因数分解するために10243の演算を必要とします。しかし、100MIPSで動作する量子コンピュータでは、1024ビットの数値を数秒で因数分解することができます。単一のエンタングル状態を達成するには、それぞれサイズ2048量子ビットと1024量子ビットの2つのレジスタを使用して、一貫して動作させることで実現します。

ショアのアルゴリズムにおける問題点

ショアのアルゴリズムは、古典的なコンピュータでは最良の方法ではありません。二次ふるい法、レンストラ楕円曲線分解、一般数体篩法などのアルゴリズムは、従来の機械ではこの問題に対してより優れたパフォーマンスを発揮します。
ショアのアルゴリズムの驚くほど高速なパフォーマンスにもかかわらず、ショアのアルゴリズムを用いた量子コンピュータによる最大の因数分解は21です。