Wie der Hase von der Schildkröte gelernt hat, ist Geschwindigkeit nicht alles. Theoretische Informatiker der Sandia National Laboratories und der Boston University haben entdeckt, dass Quantencomputer bei der Lösung eines anspruchsvollen mathematischen Problems unübertroffen sind. Ungewöhnlicherweise bewiesen sie, dass Quantencomputer nicht schneller sind als normale Computer; stattdessen verbrauchen sie viel weniger Speicher.
Diese Enthüllung widerlegt die herkömmliche Vorstellung, dass der Wert eines Quantencomputers darin liegt, dass er bestimmte Probleme viel schneller lösen kann als ein normaler Computer. Sie könnte Forschern auch dabei helfen, weitere praktische Anwendungen für die sich rasch weiterentwickelnde Technologie zu finden.
„Dies ist der erste exponentielle Quantenvorteil für ein natürliches Streaming-Problem“, sagte Ojas Parekh von Sandia, ein Mitglied des Teams.
Der Speicher ist für jeden Computer wichtig. Je mehr Speicher er hat, desto größere Probleme kann er lösen. Für Quantencomputer, die Informationen in Qubits speichern, „ist der Speicherplatz wirklich wichtig, weil es schwierig ist, Quantencomputer mit vielen Qubits zu bauen“, sagte Parekh.
Das Team präsentierte seine Ergebnisse auf dem Symposium on Theory of Computing, das vom 24. bis 28. Juni in Vancouver, British Columbia, stattfand. Der mathematische Beweis ist verfügbar auf der arXiv Preprint-Server.
Der Wert von Quantencomputern könnte nicht nur in der Geschwindigkeit, sondern auch in der Speichereffizienz liegen
1994 überraschte der amerikanische Wissenschaftler Peter Shor die Welt, als er bewies, dass zukünftige Quantencomputer in der Lage sein würden, Standard-Verschlüsselungsalgorithmen alarmierend schnell zu knacken. In den 30 Jahren seither haben Forscher allerdings nur eine Handvoll anderer Probleme gefunden, die diese Computer schneller lösen können als normale Computer.
Die Forschungsergebnisse von Sandia und der Boston University weisen nun auf einen anderen Bereich hin, in dem ein Quantenvorteil möglich ist.
„Der Schwerpunkt der Forschung zum Quantenvorteil lag bisher auf der Erzielung von Zeitvorteilen“, sagt Nadezhda Voronova, Doktorandin am Institut für Informatik der Boston University. „Die Forschung zum Quantenvorteil im Hinblick auf andere Ressourcen wie Speicher war relativ begrenzt.“
Wenn Wissenschaftler ihre Aufmerksamkeit auf diese anderen Eigenschaften, etwa die Effizienz, richten, können sie praktischere Einsatzmöglichkeiten für Quantencomputer finden.
„Verpassen wir derzeit wichtige Quantenvorteile, weil wir uns auf bestimmte Arten von Problemen konzentrieren oder diese bevorzugen?“, fragte Parekh.
Was ein natürliches Streaming-Problem ist und warum es wichtig ist
Das mathematische Problem, das im Mittelpunkt der Behauptung des Teams steht und als „maximal gerichteter Schnitt“ bezeichnet wird, ist bedeutsam, da es sich um das handelt, was Forscher als „natürliches Problem“ bezeichnen.
„Wenn wir über ein Naturproblem sprechen“, sagt John Kallaugher von Sandia, „dann meinen wir damit, dass es ein Problem von eigenständigem Interesse ist – dass die Menschen es bereits im klassischen Rahmen untersucht haben.“
Parekh erläuterte weiter: „Beim Max Directed Cut-Problem geht es darum, die beiden Agentengruppen in einem Netzwerk zu finden, bei denen die meiste Kommunikation von einer Gruppe zur anderen geleitet wird. Dieses Problem findet Anwendung in der Cybersicherheit und in der Analyse und Gestaltung sozialer Netzwerke.“
Normalerweise benötigen Computer viel mehr Speicher, wenn diese Art von Problem komplexer wird. Quantencomputer brauchen das jedoch nicht, wie das Team herausfand. Sie sind exponentiell effizienter bei der Speichernutzung, zumindest wenn die Daten in einem Stream ankommen. Streaming-Berechnungen sind nützlich, wenn Datensätze zu groß sind, um in den Speicher eines Computers zu passen, oder wenn die Daten kontinuierlich erstellt werden.
Kallaugher bereits veröffentlicht dass Quantencomputer einen deutlichen, aber geringeren Vorteil haben könnten als der, den er und sein Team jetzt bewiesen haben. Die neue Entdeckung eines Exponentialverhältnisses ist bedeutsam, da ein Vorteil sehr groß sein muss, um die Zeit und das Geld zu rechtfertigen, die für den Bau und Betrieb eines Quantencomputers erforderlich sind.
Wie Shors Algorithmus ist auch die neue Erkenntnis noch theoretischer Natur, da sie bisher nicht auf einem Computer demonstriert werden konnte.
Entdeckung deutet auf zukünftige Rollen des Quantencomputings hin
Der maximale gerichtete Schnitt ist an sich nicht sehr nützlich. Es handelt sich jedoch um ein weithin bekanntes Optimierungsproblem in der höheren Mathematik, das das Forschungsteam als Hinweis auf die Art und Weise betrachtet, wie Quantencomputer in Zukunft praktisch eingesetzt werden könnten.
„In der Cybersicherheit beispielsweise könnte die effiziente Lösung von Optimierungsproblemen zu einer besseren Ressourcenzuweisung, verbesserten Strategien zur Reaktion auf Vorfälle und genaueren Risikobewertungen führen“, sagte Voronova.
Kallaugher fügte hinzu: „Dies könnte den Weg zu Algorithmen weisen, die Probleme bewältigen können, die für jeden klassischen Computer zu groß sind.“
„Es könnte noch mehr solcher Algorithmen geben“, spekulierte Voronova.
„Niemand kennt wirklich das Gesamtbild“, sagte Parekh.
Mehr Informationen:
John Kallaugher et al., Exponentialer Quantenraumvorteil zur Approximation des maximalen gerichteten Schnitts im Streaming-Modell, arXiv (2023). DOI: 10.48550/arxiv.2311.14123