最近、X で量子コンピューターに関する誇大宣伝が増えているので、それらについて長い投稿をしようと思いました。 エグゼクティブサマリー: 量子コンピューティングがすぐには来るとは思いません。これは、量子コンピューターが使用できる最も単純な問題である因数分解について、長年にわたって進歩が見られていないからだと思います。量子因数分解の記録は、10年前から15(はい、15、3 x 5!)という数字の前後にあり、最近明らかな進歩は見られていません。 私の推論は以下の通りです。数学やコンピューターサイエンスをあまり知らない人のために詳しく説明しますが、それでも数学恐怖症の人を怖がらせるかもしれません。 いくつかの重要な暗号化アルゴリズムは、従来のコンピューターを使用して十分に大きな数を素因数に因数分解するのに非常に長い時間がかかるという事実に依存しているため、大きな数の因数分解は興味深いものです。 小さな数 (たとえば 21) を手作業で非常に素早く因数分解でき、それを 2 から 3 の順に始まる数字で割ってみると、21 が 3 x 7 であることがすぐにわかります。 ただし、これは、試す必要があるすべての数値のスペースが大きすぎるため、非常に大きな数値には機能しません。長さが約1200桁の10進数を超える数値を因数分解できれば(4桁の数字である1200ではなく、1200桁の数字です!)、人々が関心を持っている多くの暗号システムを解読できますが、通常のコンピューターでそれを十分に迅速に行う方法を誰も知りません。(速いとは、「空のすべての星が燃え尽きる前」を意味します。 数年前、ピーター・ショールは、量子コンピューターを使用して(少なくとも理論的には)非常に迅速に数値を因数分解できることを示しました。私の意見では、ショールのアルゴリズムを使用した因数分解は、量子コンピューティングの最も明白な偽装が難しいベンチマークです。 2016年、15という数字(15桁の数字ではなく、15という数字)が、ショールのアルゴリズムのクリーンで不正なデモンストレーションで初めて(明らかに3 x 5に)因数分解されました。これは小さな数字ですが、始まりでした。(21という数字が、ショールのアルゴリズムの不正なデモンストレーションにも考慮されているかどうかについては、いくつかの議論があります。 しかし、繰り返しになりますが、15は2桁の数字です。暗号化システムを解読できるように、数千桁の数字を分解したいと考えています。 しかし、2016年以降、Shorのアルゴリズムのクリーンなデモンストレーションでは、それ以上の数字は考慮されていません。(ショールのアルゴリズムを使ってより大きな数を因数分解したと主張する人もいますが、そのためには因数をすでに知っていて、答えの事前知識に相当する量子コンピューターをセットアップする必要があるトリックを常に使用してきましたが、それは実際には重要ではありません。*不正されていない*デモンストレーションを探しています。 私たちは、誰かが15よりわずかに大きい数値でも因数分解を実証するのを長い間待っていました。誰かが77(7 x 11)のような数字を因数分解し、次に323(17 x 19)のような数値、そして数千というように、これについて着実な進歩があることを期待したでしょう。しかし、15 という数字 (子供が頭の中で一瞬で 3 と 5 に分解できる) よりも優れたことができるマシンを実証した人は誰もおらず、その記録は非常に長い間保持されています。 したがって、少なくともこの問題については、説明しやすい非常に基本的な問題ですが、量子コンピューティングには着実な進歩はありません。私たちは多くの誇大宣伝を受け、明らかにクリーンなデモンストレーションとは言えないアルゴリズムを実行していると思われる量子コンピューターを誇示する人がたくさんいましたが、因数分解に関しては長い間何も見られませんでした。 量子コンピューティングに真の進歩があったと信じるのは、ショールのアルゴリズムのクリーンで不正なデモンストレーションで、より大きな数字が考慮されるようになったときです。10進数以下の4桁の数字、つまり数千の数字を実行できるようになったとき、私たちは本当に進歩したと信じています。15よりもはるかに大きな2桁の数字を実行できるもののデモンストレーションでさえ歓迎されます。 しかし、それができるマシンは、実際には近い将来にはありません。 現在、暗号を解読するには、*数千桁*の数字を処理できるマシンが必要ですが、まだ3桁の数字(またはほとんどの2桁の数字)さえ見えていません。 したがって、私の個人的なベンチマークでは、これについて少しでも進歩が見られます。323 を因数分解できる量子コンピューターが、同様のサイズの任意の複合数を処理する Shor's Algorithm のクリーンで不正なデモで、私に電話してください。それまでは、少なくとも私にとっては、あまり興味はないと思います。

(ところで、量子コンピューティングは不可能だとか、何かだと思うという印象を与えたくありません。私が言っているのは、私の立場からすると、最近の進歩は明らかではなく、それを使って数値を因数分解するなどの単純な問題を解決するにはまだ遠いです。

ちなみに、これは、Google のような企業が量子コンピューティングの純粋な研究を追求するのが愚かであるという意味でもありません。取り組む価値はあると思います。差し迫った実用化はありません。 また、NSAやその他のそのような組織が、オープンリサーチの世界よりもこの問題に対して大きな進歩を遂げている可能性もありますが、明らかに、それは私が知っている情報ではありません。 最後に、これはポスト量子暗号アルゴリズムの研究が悪い考えであるという意味ではありません。

一番上の元の投稿では、スケーリングの問題がどれほど難しいかについては言及しませんでした。ほとんどの場合、私はスケーリングが実際に起こっていないという事実に集中しました。そして確かに、ある時点で、エラー修正のものが現れ始める可能性が非常に高いです。しかし、深刻な数字へのスケールアップは、その翌日には実現しません。

@defendtheworld とにかく、もう一度、テクノロジーが因数分解 15 から前進するのを見たとき、私は信じ始めるでしょう。そして、はい、それは膨大な量の作業がすでに行われていることを意味しますが、まだ膨大な量の作業が残されていることになります。