Ich bin ein junger Informatiker und werde gebeten, eine Arbeit zu schreiben, die eine ganzzahlige Faktorisierung beinhaltet. Daher muss ich mich mit Shors Algorithmus auf Quantencomputern befassen.
Für die anderen Algorithmen konnte ich spezifische Gleichungen finden, um die Anzahl der Anweisungen des Algorithmus für eine bestimmte Eingabegröße zu berechnen (aus denen ich die Zeit berechnen konnte, die für die Berechnung auf einer Maschine mit einer bestimmten Geschwindigkeit erforderlich ist). Für Shors Algorithmus kann ich jedoch höchstens seine Komplexität finden : O( (log N)^3 )
.
Gibt es eine Möglichkeit, die Geschwindigkeit / tatsächliche Komplexität anhand der Big-O-Notation zu ermitteln? Wenn nicht, gibt es jemanden, der mir sagen kann, was ich will oder wie ich es finde?
quelle
Was Sie verlangen, gibt es aus guten Gründen nicht.
Heute gibt es keinen Computer, der Shors Algorithmus ausführen kann. Um Shors Algorithmus auszuführen, benötigen Sie einen Quantencomputer, der noch nicht existiert. Daher sollten Sie keine genauen Schätzungen der Geschwindigkeit oder Laufzeit erwarten, da dies von den Details des Computers abhängt, auf dem der Algorithmus ausgeführt wird - und wir können diese Details möglicherweise erst kennen, wenn wir erfolgreich eine erstellt haben .
quelle