Quantencomputing: Einstieg in die Welt der Quantenalgorithmen

Quantencomputer können bisher recht wenig. Quantenalgorithmen sind schon etwas weiter entwickelt. Eine verständliche Einführung.

Lesezeit: 15 Min.
In Pocket speichern
vorlesen Druckansicht Kommentare lesen
Von
  • Jens Marre
Inhaltsverzeichnis

Next Big Thing oder überzogener Hype: Quantencomputer sind vermutlich beides. Die Eigenschaften der Quanten verleihen ihnen ein enormes Potenzial. Mehrere vielversprechende Quantenalgorithmen, die klassischen Methoden überlegen sind, existieren bereits. Sie benötigen allerdings skalierbare und fehlerkorrigierende Quantencomputer, deren Entwicklung gerade erst beginnt. Die aktuellen, sehr eingeschränkten NISQ-Rechner (Noisy Intermediate-Scale Quantum) eignen sich dazu noch nicht. Dennoch lohnt es sich schon jetzt, sich einen Überblick zu verschaffen über die zentralen Quantenalgorithmen und die Zusammenhänge, in denen sie stehen.

Mehr zu Quantencomputern

Quantenalgorithmen eignen sich unter anderem für Anwendungen, in denen man mit einer hochkomplexen Wahrscheinlichkeitsverteilung arbeitet, etwa in Random-Walk-Anwendungen. Nützlich sind Quantenalgorithmen vor allem dann, wenn es gelingt, diese Wellenfunktion im Verlauf der Berechnung derart zu interferieren, dass man am Ende ein mehr oder weniger eindeutiges Ergebnis auslesen kann. Wer sich genauer mit dem Potenzial von Quantencomputern beschäftigen möchte, kommt nicht umhin, sich mit der Komplexitätstheorie vertraut zu machen.

Vor etwa 50 Jahren beschäftigten sich Computerwissenschaftler mit der Frage: Was macht ein mathematisches Problem komplex? Genauer: Kann man Komplexität messen und kann man hierfür Klassen einführen? Das führte zur Komplexitätstheorie. Früh erkannte man, dass die Schrittlänge und die Speichergröße des besten Algorithmus zur Lösung des Problems geeignete Maße für Komplexität sind. Ein Problem gehört beispielsweise zu den P- oder PTIME-Problemen (Polynomial Time), wenn sich die Schrittlänge beziehungsweise die Ausführungszeit des Lösungsalgorithmus nur polynomial – also etwa linear, quadratisch oder kubisch – zur Eingabegröße steigert. Damit umfasst die Klasse P die Probleme, die man einigermaßen effizient lösen kann.

Immer mehr Wissen. Das digitale Abo für IT und Technik.

  • Zugriff auf alle Inhalte von heise+
  • exklusive Tests, Ratgeber & Hintergründe: unabhängig, kritisch fundiert
  • c't, iX, MIT Technology Review, Mac & i, Make, c't Fotografie direkt im Browser lesen
  • einmal anmelden – auf allen Geräten lesen - monatlich kündbar
  • erster Monat gratis, danach monatlich ab 9,95 €
  • Wöchentlicher Newsletter mit persönlichen Leseempfehlungen des Chefredakteurs
GRATIS-Monat beginnen Jetzt GRATIS-Monat beginnen Mehr Informationen zu heise+