human
Shorのアルゴリズムをクラシックコンピューターで実行できないのはなぜですか？
gpt
Shorのアルゴリズムは、整数因数分解のための量子コンピューターアルゴリズムです。量子コンピューターではポリロガリズム（サブポリノミアル）時間で実行されますが、現在は整数因数分解のための多項式時間の古典的アルゴリズムは既知ではなく、そのようなアルゴリズムが存在するかどうかは不明です。

Shorのアルゴリズムは、ビットではなく量子ビット（Qubits）で動作するため、古典的なコンピューターで実行できません。抽象的には、量子ビットは2つの状態の重ね合わせにあると言われています - 測定時に特定の確率でどちらの状態を想定できます。対照的に、古典的なビットは、いつでも可能な2つの状態の1つを想定することができます。

このqubitのこのプロパティにより、量子コンピューターは複数のポイントで機能を同時にサンプリングできます。Shorのアルゴリズムは、この事実を使用して、モジュラー指数関数の期間を見つけます。クラシックコンピューターは関数の各ポイントを個別にサンプリングする必要があるため、このタスクを合理的な時間で完了することはできません。
human
Schorのアルゴリズムは、古典的なコンピューターで動作します。Shorのアルゴリズムには多くのステップが含まれています。これらはすべて、ゆっくりと実行され、量子コンピューターでのみ効率的に評価できる期間検索ステップを除いて、古典的なコンピューターで迅速に実行されます。古典的に考慮するにはさまざまな方法がありますが、それらはすべて指数関数的な時間を必要とします。最良の電流アルゴリズムは、一般番号フィールドシーブです。ただし、量子コンピューターは多項式時間を考慮し、Shorのアルゴリズムから利点を完全に利用できます。