HHL-Algorithmus

Der 2009 von Aram Harrow, Avinatan Hassidim und Seth Lloyd veröffentlichte HHL-Algorithmus löst lineare Systeme der Form Ax = b und liefert einen Quantenzustand proportional zum Lösungsvektor x in einer Zeit, die logarithmisch mit der Systemgröße skaliert — eine exponentielle Beschleunigung gegenüber den besten klassischen linearen Lösern unter den richtigen Bedingungen. Genau diese Bedingungen sind der Haken: Die Beschleunigung erfordert, dass die Matrix A dünn besetzt und gut konditioniert ist, dass der Eingabevektor b bereits als Quantenzustand ladbar ist (selbst im Allgemeinen ein schwieriges Problem), und die Ausgabe ist ein Quantenzustand, der die Lösung kodiert, nicht die einzelnen Zahlen der Lösung, sodass das Auslesen bestimmter Werte zusätzliche Messungen erfordert und die Beschleunigung oft vollständig zunichtemacht. HHL versteht man am besten als Subroutine, auf der andere Quantenalgorithmen aufbauen, allen voran mehrere vorgeschlagene Quanten-Machine-Learning-Algorithmen, die intern auf das Lösen eines linearen Systems zurückgeführt werden, statt als allgemeinen Ersatz für klassische lineare Algebra. Es existiert noch keine fehlertolerante Hardware, die HHL in einem Maßstab ausführen könnte, bei dem sich sein asymptotischer Vorteil in der Praxis zeigen würde.