Warum kann Shors Algorithmus nicht auf einem klassischen Computer ausgeführt werden?
user
Shor's Algorithmus ist ein Quantencomputer-Algorithmus für die Integerfaktorisierung. Er läuft in polylogarithmischer (sub-polynomialer) Zeit auf einem Quantencomputer, während es derzeit keinen polynomialzeitlichen klassischen Algorithmus für die Integerfaktorisierung gibt, und es ist nicht bekannt, ob ein solcher Algorithmus existiert. Shor's Algorithmus kann nicht auf einem klassischen Computer laufen, da er auf Quantenbits (Qubits) anstatt auf Bits arbeitet. Abstrakt gesagt, Quantenbits sind in einer Überposition von zwei Zuständen - sie können entweder einen Zustand annehmen, wenn sie gemessen werden, mit einer bestimmten Wahrscheinlichkeit. Im Gegensatz dazu können klassische Bits nur einen ihrer zwei möglichen Zustände zu jeder gegebenen Zeit annehmen. Diese Eigenschaft des Qubits erlaubt Quantencomputern, Funktionen in mehreren Punkten gleichzeitig abzutasten. Shor's Algorithmus nutzt diese Tatsache, um die Periode der modularen Exponentiationsfunktion zu finden, die verwendet werden kann, um die Modularität zu faktorisieren. Da ein klassischer Computer jeden Punkt in der Funktion einzeln abtasten muss, wäre es nicht in der Lage, diese Aufgabe in einer vernünftigen Zeit zu beenden.
assistant
Schor-Algorithmus funktioniert auf einem klassischen Computer. Shor-Algorithmus enthält viele Schritte, die alle schnell auf einem klassischen Computer laufen, außer für die Periode finden Schritt, der läuft langsam und kann nur effizient von einem Quantencomputer ausgewertet werden. Es gibt verschiedene Möglichkeiten, klassisch zu Faktor, aber sie alle erfordern exponentielle Zeit. Der beste aktuelle Algorithmus ist die allgemeine Zahlenfeldsieb. Quantencomputer, obwohl, kann in polynomialen Zeit und voll nutzen die Vorteile von Shor-Algorithmus.
user