Tipps für neue Multiplikationsansätze zur Verbesserung von Quantencomputern

In der Praxis können viele Programme, die für klassische Computer entwickelt wurden, nicht auf Quantencomputern ausgeführt werden, da sie Informationen nicht selektiv vergessen können. Der neue Multiplikationsalgorithmus zeigt, wie Sie dieses Problem umgehen können.

Klassische Bits sind schwarz und weiß, und Quantenbits sind etwas komplizierter

Als ich 9 war, kauften meine Eltern einen neuen Computer. In fast jeder Hinsicht war er besser als der alte, bis auf einen: Meine Lieblingsrennen starteten nicht damit. Ich erinnere mich, wie ich dachte - warum brauche ich einen neuen Computer, wenn er mein Lieblingsprogramm nicht startet?

Quantencomputer haben das gleiche Problem. Theoretisch sind sie zu allem fähig, wozu der Klassiker fähig ist. In der Praxis macht es ihre Quantennatur fast unmöglich, einige der wichtigsten klassischen Algorithmen auszuführen.

Deshalb enthält die am 15. April veröffentlichte Arbeit gute Nachrichten. Craig Gidney , Informatiker bei Google AI Quantum in Santa Barbara, Kalifornien, beschreibt eine Quantenversion des klassischen Algorithmus zur schnellen Multiplikation sehr großer Zahlen. Auf klassischen Computern läuft dieser Algorithmus schon seit einiger Zeit. Vor Gidneys Arbeit war jedoch unklar, ob es möglich sein würde, es für Quantenmaschinen anzupassen.

Noch wichtiger ist, dass der Multiplikationsalgorithmus zur Klasse der allgegenwärtigen Informatikalgorithmen gehört. Gidney glaubt, dass seine neue Technik es Quantencomputern ermöglichen wird, die gesamte Klasse dieser Algorithmen zu implementieren, die bisher als zu umständlich für die Verwendung in einer Quantenmaschine angesehen wurden.

Dieser Multiplikationsalgorithmus nutzt die Entdeckung, die der erste Durchbruch bei der Multiplikation über mehrere tausend Jahre war. Die traditionelle Schulmultiplikationsmethode erfordert n ² Schritte, wobei n die Anzahl der Zeichen in den multiplizierten Zahlen ist. Mehrere tausend Jahre lang glaubten Mathematiker, dass es keinen effizienteren Ansatz gibt.

Wie wir kürzlich in dem Artikel „ Mathematiker haben den idealen Weg zur Multiplikation von Zahlen entdeckt “ klarstellten, entdeckte der sowjetische Mathematiker Anatoly Karatsuba 1960 einen schnelleren Weg. Seine Methode bestand darin, lange Zahlen in kürzere aufzuteilen. Um beispielsweise zwei achtstellige Zahlen zu multiplizieren, müssen Sie sie zuerst in zwei vierstellige Zahlen und dann in zwei zweistellige Zahlen aufteilen. Dann müssen Sie mehrere Operationen mit zweistelligen Zahlen ausführen und das Ergebnis der endgültigen Multiplikation wiederherstellen. Um sehr große Zahlen zu multiplizieren, benötigt die Karatsuba-Methode viel weniger Schritte als die Schulmethode.

Wenn ein klassischer Computer mit dem Karatsuba-Algorithmus ausgeführt wird, werden dabei Informationen gelöscht. Wenn er beispielsweise zweistellige Zahlen auf vierstellige zurücksetzt, vergisst er zweistellige Zahlen. Jetzt interessiert er sich nur noch für vierstellige Zahlen. Die klassische Version des Algorithmus ähnelt einem Kletterer, der beim Klettern seine Ausrüstung wegwirft - er kann sich schneller bewegen, wenn er nicht den ganzen Müll mit sich trägt.

Quantencomputer können jedoch keine Informationen verwerfen.

Quantencomputer führen Berechnungen durch Manipulationen mit Quantenbits oder "Qubits" durch. Sie sind miteinander verflochten oder verwirrt. Diese Verwirrung bietet Quantencomputern enorme Möglichkeiten - anstatt Informationen in separaten Bits zu speichern, verwenden Quantencomputer komplexe Interaktionen aller Qubits. Infolgedessen können Quantencomputer für bestimmte Aufgaben im Vergleich zu klassischen Aufgaben eine exponentiell höhere Rechenleistung aufweisen.

Die gleiche Eigenschaft, die Quantencomputer so leistungsfähig macht, macht sie jedoch auch zerbrechlich. Da Qubits verwickelt sind, ist es unmöglich, einige davon zu ändern, ohne alle anderen zu beeinflussen. Dies macht es unmöglich, Informationen, die für klassische Computer verfügbar sind, selektiv zu löschen. Das Zurückschlagen von Qubits ist wie das Schneiden von Teilen einer Bahn - selbst ein einziger Schnitt kann die gesamte Bahn zerstören.

Diese Anforderung zur Erhaltung von Informationen erschwert die Erstellung von Quantenversionen rekursiver Algorithmen - das heißt, sich selbst zuzuwenden. In der Informatik werden rekursive Algorithmen sehr häufig verwendet. Um jedoch optimal zu funktionieren, muss der Computer bei jedem Schritt Informationen verwerfen. Ohne dies wird das Rechnen schnell unpraktisch. "Wenn Sie bei jeder Operation Informationen speichern, wächst der Platzbedarf mit der Anzahl der Operationen", sagte Ashley Montanaro , Quanteninformationsspezialistin an der Universität Bristol. Jeder praktischen Maschine geht schnell der Speicher aus.

In einer neuen Arbeit beschreibt Gidney eine Quantenmethode zur Implementierung der Karatsuba-Multiplikation, die keinen großen Speicherverbrauch erfordert. Anstatt Zwischenwerte zu generieren, um das Endergebnis zu erhalten, wird die Methode " Tail-Rekursionsoptimierung " verwendet, um Eingaben direkt in Ausgaben umzuwandeln. Auf diese Weise kann der Algorithmus vermeiden, Zwischeninformationen zu erstellen, die ein Quantencomputer nicht verwerfen kann. "Er beseitigt das Problem der zusätzlichen Qubits, ohne zusätzliche Qubits zu erzeugen", sagte Thomas Vaughn , ein Quanteninformationsspezialist an der Creiton University.

Gidney glaubt, dass seine Methode funktionieren wird, um viele klassische rekursive Algorithmen für Quantencomputer anzupassen. Bisher stecken Quantencomputer noch in den Kinderschuhen, so dass sie die Multiplikation einzelner Ziffern kaum bewältigen können. Der Algorithmus ist jedoch bereit, und wenn ihre Schemata verbessert werden, können sie viel mehr.