Ist die in der Informatik übliche Verwendung des Ignorierens von Konstanten nützlich, wenn klassisches Computing mit Quantencomputing verglichen wird?

Daniel Sank erwähnte in einem Kommentar , dass die konstante Beschleunigung von bei einem Problem, das einen polynomialen Zeitalgorithmus zulässt, mager ist$10^8$

Die Komplexitätstheorie ist viel zu besessen von unendlichen Größenbeschränkungen. Im wirklichen Leben kommt es darauf an, wie schnell Sie die Antwort auf Ihr Problem erhalten.

In der Informatik ist es üblich, Konstanten in Algorithmen zu ignorieren, und insgesamt hat sich herausgestellt, dass dies recht gut funktioniert. (Ich meine, es gibt gute und praktische Algorithmen. Ich hoffe, Sie werden mir (theoretische) Algorithmen gewähren, an denen Forscher eine ziemlich große Hand hatten!)

Aber ich verstehe, dass dies eine etwas andere Situation ist, als wir es jetzt sind:

1. Es werden nicht zwei Algorithmen verglichen, die auf demselben Computer ausgeführt werden, sondern zwei (geringfügig) unterschiedliche Algorithmen auf zwei sehr unterschiedlichen Computern.
2. Wir arbeiten jetzt mit Quantencomputern , für die herkömmliche Leistungsmessungen möglicherweise nicht ausreichen.

Insbesondere sind die Methoden der Algorithmusanalyse lediglich Methoden . Ich denke, radikal neue Berechnungsmethoden erfordern eine kritische Überprüfung unserer aktuellen Leistungsbewertungsmethoden!

Meine Frage lautet also:

Wenn man die Leistung von Algorithmen auf einem Quantencomputer mit der Leistung von Algorithmen auf einem klassischen Computer vergleicht, ist es dann eine gute Praxis, Konstanten zu ignorieren?

Die in der Informatik übliche Verwendung des Ignorierens von Konstanten ist nur nützlich, wenn die Leistungsunterschiede verschiedener Arten von Hardwarearchitekturen oder Software mit ein wenig Massieren ignoriert werden können. Aber auch bei der klassischen Berechnung ist es wichtig, die Auswirkungen der Architektur (Caching-Verhalten, Festplattennutzung) zu kennen, wenn Sie schwierige oder große Probleme lösen möchten.

Das Ignorieren von Konstanten ist keine Praxis, die aus Sicht der Implementierung motiviert ist (im Sinne einer kontinuierlichen Bestätigung). Es beruht hauptsächlich auf dem Interesse an einem Ansatz zur Erforschung von Algorithmen, der sich in der Komposition gut verhält und einfache Charakterisierungen in einer Art und Weise zulässt, die der reinen Mathematik nahe kommt. Die Beschleunigungssätze für Turing Machines bedeuteten, dass keine vernünftige Definition versuchen konnte, die Komplexität von Problemen zu genau zu bestimmen, um zu einer vernünftigen Theorie zu gelangen. und außerdem waren im Kampf um gute Algorithmen für schwierige Probleme die konstanten Faktoren nicht der mathematisch interessante Teil ...

Dieser abstraktere Ansatz zur Erforschung von Algorithmen war und ist größtenteils fruchtbar. Jetzt sind wir jedoch mit einer Situation konfrontiert, in der wir zwei Berechnungsmodelle haben

• Man befindet sich in einem fortgeschrittenen Stadium der technologischen Reife (klassische Berechnung); und
• Einer befindet sich in einem sehr unreifen Zustand, versucht jedoch, ein theoretisches Modell zu realisieren, das zu signifikanten asymptotischen Verbesserungen führen kann (Quantenberechnung).

In diesem Fall können wir fragen, ob es überhaupt Sinn macht, den asymptotischen Nutzen mit oder ohne sorgfältige Berücksichtigung der konstanten Faktoren zu berücksichtigen. Wegen des zusätzlichen Aufwands, der erforderlich sein kann, um eine skalierbare Quantenberechnung durchzuführen, können nicht nur Skalarfaktoren, sondern auch polynomielle "Beschleunigungen" der theoretischen Leistung verworfen werden, wenn der gesamte Aufwand bei der Realisierung eines Quantenalgorithmus berücksichtigt wird.

In diesen frühen Tagen kann es auch signifikante Leistungsunterschiede zu verschiedenen Ansätzen der Quantenarchitektur geben. Dies könnte die Wahl der Architektur als wichtig (wenn nicht sogar wichtiger) für die Leistungsfähigkeit eines Algorithmus als die asymptotische Analyse erweisen - so wie es für Sie von großer Bedeutung ist, ob Sie Ihre konventionelle Berechnung auf einer von Neumann-Maschine oder in einem stark verteilten Netzwerk durchführen mit erheblichen Latenzen.

Das eigentlich Wichtige für die praktische Berechnung sind - und waren es schon immer - nicht nur Algorithmen, sondern auch Implementierungen von Algorithmen : ein Algorithmus, der auf eine bestimmte Art und Weise auf einer bestimmten Architektur realisiert wird. Die gängige Praxis der asymptotischen Analyse, bei der konstante Faktoren ignoriert werden, ermöglicht es uns, die systematischen, mathematischen Gründe für Leistungsunterschiede bei Algorithmen zu berücksichtigen. Sie ist praktisch motiviert, wenn die architektonischen Unterschiede nicht so groß sind, dass sie die praktische Leistung dominieren .

In Bezug auf Quantentechnologien sind wir nicht in der glücklichen Situation, konstante Faktoren in jedem praktischen Kontext sicher zu beschönigen. Aber vielleicht werden wir es eines Tages schaffen. Dies ist das lange Spiel der Quanteninformationstechnologien - bis jetzt fast das einzige Spiel, das akademische Informatiker jemals gespielt haben, was die Quanteninformationstechnologie betrifft. Wenn wir den Tag vorwegnehmen, an dem die Quantentechnologie Fuß fasst, ist es gut, die asymptotische Analyse als eine Untersuchungsrichtung für die Leistung von Quantenalgorithmen fortzusetzen .

$O\left(f\left[N\right]\right)$$N$

$10^{10}$

$\approx300$

Sie können die konstanten Faktoren nicht ignorieren, wenn Sie die Quantenberechnung mit der klassischen Berechnung vergleichen. Sie sind zu groß.

Hier ist zum Beispiel ein Bild von einigen Folien, die ich letztes Jahr vorgestellt habe:

Die Dinge auf dem Grund sind magische Staatsfabriken. Sie haben eine Stellfläche von 150.000 physischen Qubits. Da das UND-Gatter für 0,6 Millisekunden 150 K-Qubits verwendet, nehmen wir an, dass das Raum-Zeit-Volumen eines UND-Gatters in der Größenordnung von 90 Qubit-Sekunden liegt.

Eines der Ziele meiner Mitarbeiter ist es, 1 CPU pro 100 Qubits für die Fehlerkorrektur zu verwenden. Wir könnten also sagen, dass 90 Qubit-Sekunden 0,9 CPU-Sekunden Arbeit erfordern. Wir haben die Quantenkonstruktionen um ein Vielfaches effizienter gemacht, seitdem das obige Bild erstellt wurde. Nennen wir es stattdessen 0,1 CPU-Sekunden.

(Es gibt viele Annahmen, die in diese Schätzungen einfließen. Welche Art von Architektur, Fehlerraten usw. ich versuche nur, eine Größenordnung Idee zu vermitteln.)

Es sind 63 UND-Gatter erforderlich, um eine 64-Bit-Addition durchzuführen. 63 * 0,1 CPU-Sekunden ~ = 6 CPU-Sekunden. Quantumly kostet eine 64-Bit-Addition mehr als eine CPU-Sekunde. Klassischerweise kostet eine 64-Bit-Addition weniger als eine CPU-Nanosekunde. Hier gibt es leicht einen konstanten Faktorunterschied von 10 Milliarden. Wenn Sie mit einer parallelen klassischen Maschine wie einer GPU vergleichen, werden die Zahlen noch schlechter. Sie können konstante Faktoren mit so vielen Ziffern nicht ignorieren.

Betrachten Sie beispielsweise den Algorithmus von Grover, der es uns ermöglicht, in sqrt (N) -Bewertungen der Funktion anstelle von N Bewertungen nach einer befriedigenden Eingabe für eine Funktion zu suchen. Addieren Sie den konstanten Faktor von 10 Milliarden und finden Sie heraus, wo der Quantencomputer weniger Auswertungen benötigt:

Der Algorithmus von Grover kann die Auswertungen nicht parallelisieren, und für die Auswertungen ist mindestens ein UND-Gatter erforderlich, sodass Sie im Grunde genommen erst dann CPU-Zeitvorteile feststellen, wenn die Suche mehrere zehn Millionen Jahre in Anspruch nimmt.

Solange wir die konstanten Faktoren nicht wesentlich verbessern, wird niemand die Grover-Suche für irgendetwas Nützliches verwenden. Momentan ist die Quanten-gegen-Klassik-Situation ein exponentieller Vorteil oder eine Pleite.

Während andere Antworten gute Punkte liefern, habe ich das Gefühl, dass ich immer noch ein bisschen anderer Meinung bin. Also werde ich meine eigenen Gedanken zu diesem Punkt teilen.

Kurz gesagt, ich denke, die Konstante „wie sie ist“ zu zeigen, ist bestenfalls eine verpasste Gelegenheit. Vielleicht ist es das Beste, was wir derzeit bekommen können, aber es ist alles andere als ideal.

Aber zunächst halte ich einen kurzen Ausflug für notwendig.

Wann haben wir einen effektiven Algorithmus?

$10^6$

1. $P$ von (ziemlich großen) Primzahlen.
2. Berechnen $P^2$Die Menge aller Komposite mit genau zwei Faktoren aus $P$. Speichern Sie für jedes Komposit, mit welchem ​​Primzahlenpaar es erstellt wird.
3. Nun, wenn eine Instanz von gegeben $P^2$Schauen Sie sich einfach die Faktorisierung in unserer Tabelle an und geben Sie sie an. Andernfalls melden Sie "Fehler".

Ich hoffe, es ist offensichtlich, dass dieser Algorithmus Müll ist, da er nur dann richtig funktioniert, wenn unsere Eingabe in ist $P^2$. Können wir dies jedoch sehen, wenn der Algorithmus als Blackbox angegeben und "zufällig" nur mit Eingaben von getestet wird$P$? Sicher, wir können versuchen, viele Beispiele zu testen, aber es ist sehr einfach zu machen$P$ sehr groß, ohne dass der Algorithmus bei Eingaben von unwirksam ist $P^2$ (Vielleicht möchten wir eine Hash-Map oder so etwas verwenden).

Es ist also nicht unvernünftig, dass unser Müllalgorithmus zufällig "wundersame" Beschleunigungen zu haben scheint. Nun gibt es natürlich viele Techniken zur Versuchsplanung, mit denen das Risiko gemindert werden kann, aber vielleicht cleverere 'schnelle' Algorithmen, die in vielen Fällen immer noch versagen, aber nicht genügend Beispiele können uns täuschen! (Beachten Sie auch, dass ich annehme, dass kein Forscher böswillig ist , was die Sache noch schlimmer macht!)

Daher würde ich jetzt antworten: "Weck mich auf, wenn es eine bessere Leistungsmetrik gibt".

Wie können wir es dann besser machen?

Wenn wir es uns leisten können, unseren "Black-Box" -Algorithmus in allen Fällen zu testen, können wir uns von den obigen Ausführungen nicht täuschen lassen. Dies ist jedoch für praktische Situationen unmöglich. (Dies kann in theoretischen Modellen durchgeführt werden!)

Stattdessen können wir eine statistische Hypothese für eine bestimmte parametrisierte Laufzeit (normalerweise für die Eingabegröße) erstellen , um dies zu testen. Vielleicht können wir unsere Hypothese anpassen und erneut testen, bis wir eine Hypothese erhalten, die uns gefällt und die Null als vernünftig erscheint. (Beachten Sie, dass es wahrscheinlich andere Faktoren gibt, die ich ignoriere. Ich bin praktisch ein Mathematiker. Die Versuchsplanung entspricht nicht meinem Fachwissen.)

Der Vorteil des statistischen Testens einer Parametrisierung (zB ist unser Algorithmus) $O(n^3)$? ) ist, dass das Modell allgemeiner ist und es daher schwieriger ist, wie im vorherigen Abschnitt "betrogen" zu werden. Es ist nicht unmöglich, aber zumindest die statistischen Behauptungen, ob dies angemessen ist, können gerechtfertigt werden.

Was tun mit den Konstanten?

Ich denke nur, dass "$10^9$ "speedup, wow!" ist eine schlechte Methode, um diesen Fall zu lösen.

Ich denke, es ist am nützlichsten, die merkwürdige Konstante als eine Anomalie zu betrachten , dh es ist eine Behauptung, die an sich eine weitere Untersuchung rechtfertigt. Ich denke, dass das Erstellen von Hypothesen, die auf allgemeineren Modellen basieren, als nur „unser Algorithmus benötigt X-Zeit“, ein gutes Werkzeug ist, um dies zu tun. Obwohl ich nicht denke, dass wir hier einfach CS-Konventionen übernehmen können, ist es auch eine schlechte Idee, die „Verachtung“ von Konstanten völlig zu ignorieren.