HHL-Algorithmus - warum ist das erforderliche Wissen über das Eigenspektrum kein großer Nachteil?

^{Diese Frage ist eine Fortsetzung der Quantenphasenschätzung und des HHL-Algorithmus - Kenntnisse über Eigenwerte erforderlich? .}

In der oben verlinkten Frage fragte ich nach der Notwendigkeit, dass HHL Informationen über das Eigenspektrum der berücksichtigten Matrix $A$ . Es stellte sich heraus , dass die HHL Algorithmus benötigt eine Matrix mit den Eigenwerten $\lambda_j \in [0,1)$ , um korrekt zu arbeiten.

Nach dieser Bedingung müssen wir bei gegebener Matrix $A$ eine der folgenden Bedingungen überprüfen, um den HHL-Algorithmus anzuwenden:

1. Die Eigenwerte der Matrix liegen alle innerhalb von $[0,1)$ .
2. Ein Paar $(L,M) \in \mathbb{R}^2$ , das (von unten für $L$ und von oben für $M$ ) die Eigenwerte $\lambda_j$ der Matrix gebunden hat $A$. Diese Grenzen können dann verwendet werden, um die Matrix $A$ so neu zu skalieren, dass Bedingung 1 validiert wird.

Erste Gruppe von Fragen: Ich habe viele Artikel über HHL gelesen und keiner von ihnen erwähnte diese Einschränkung. Warum? Ist diese Einschränkung bekannt, wird sie jedoch als schwach angesehen (dh es ist einfach, diese Art von Informationen zu haben)? Oder war die Einschränkung nicht bekannt? Gibt es ein Forschungspapier, das diese Einschränkung erwähnt?

Lassen Sie uns nun über die Komplexitätsanalyse von HHL sprechen. Aus Quantenlinearen Systemalgorithmen: Ein Primer (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) , die Komplexität von HHL (und mehrere Verbesserungen) wird in der folgenden Abbildung beschrieben.

Die Komplexitätsanalyse berücksichtigt nicht das notwendige Wissen über das Eigenspektrum (zumindest habe ich es nicht gefunden).

Der Fall, dass die betrachtete Matrix ausreichend gute Eigenschaften aufweist, um ihre Eigenwerte analytisch abzuschätzen, ist ungewöhnlich (zumindest für reale Matrizen) und wird ignoriert.

In dieser Antwort verwendet @DaftWullie den Gershgorin-Kreissatz , um die oberen und unteren Grenzen des Eigenspektrums abzuschätzen. Das Problem bei diesem Ansatz ist, dass -Operationen ( O ( √ ) erforderlich sind$\mathcal{O}(N)$wenn eine Amplitudenverstärkung anwendbar ist). Diese Anzahl von Operationen zerstört die logarithmische Komplexität von HHL (und ist gleichzeitig nur ein Vorteil gegenüber klassischen Algorithmen).$\mathcal{O}(\sqrt{N})$

Zweite Gruppe von Fragen: Gibt es einen besseren Algorithmus hinsichtlich der Komplexität? Wenn nicht, warum wird der HHL-Algorithmus dann immer noch als exponentielle Verbesserung gegenüber klassischen Algorithmen dargestellt?

Die Beschränkung der Eigenwerte wird üblicherweise in Form einer Bedingungsnummer angegeben . Dies ist das $\kappa$ , das Sie in allen Laufzeiten in Ihrer Tabelle sehen. $\kappa = |\lambda_{\rm{max}}/\lambda_{\rm{min}}|$wobei $\lambda_{\rm{max}}$ und $\lambda_{\rm{min}}$ die maximalen bzw. minimalen Eigenwerte sind.

In allen in Ihrer Tabelle aufgeführten Laufzeiten wird davon ausgegangen, dass die Bedingungsnummer bekannt ist. Man denkt normalerweise nicht daran, "die Bedingungsnummer zu berechnen" als Teil des Algorithmus zum Beispiel zum Lösen von $Ax=b$ . Wenn die Bedingungsnummer größer ist, ist das System schwerer zu lösen, und wenn es kleiner ist, ist das System leichter zu lösen (vorausgesetzt, alle anderen Parameter, einschließlich des maximal gewünschten Fehlers $\epsilon$ werden festgehalten).

In Bezug auf die Notwendigkeit zu wissen, dass $\lambda_{\rm{max}} < M$ und $\lambda_{\rm{min}}>L$ , gibt es viele Beispiele, bei denen wir die Grenzen der Eigenwerte kennen können, ohne tatsächlich den Aufwand für die Berechnung der Eigenwerte zu durchlaufen. Auf diese Weise kann HHL eine großartige Möglichkeit sein, den gesuchten Zustand zu finden, ohne die Kosten für die Berechnung der Bedingungsnummer oder Eigenwerte.

Lassen Sie mich nur ein Beispiel aus der Praxis nennen. Sagen wir , ich die molekulare Schwingungszustand finden wollen $|\psi\rangle$ , so daß nach $t=10$ ps unter der Hamilton - Operator von sich entwickelnden $H$ ist das Molekül , endet im Zustand $|b\rangle$ . Dies kann durch die folgende Gleichung beschrieben werden:

wo die $|\psi\rangle$ diese Gleichung erfüllt ist , was Sie wissen wollen. Sie finden Ihren gewünschten $|\psi\rangle$ durch den HHL - Algorithmus mit der Verwendung von $A = e^{-\frac{i}{\hbar}Ht}$und$|\psi\rangle = |x\rangle$ .

Das Erhalten der kleinsten und größten Eigenwerte eines molekularen Hamilton-Operators mit willkürlicher Genauigkeit ist für einen klassischen Computer äußerst kostspielig, aber das Wissen, dass sie innerhalb des Bereichs $(L,M)$ kann ohne Kosten bestimmt werden. Wenn das Molekül beispielsweise das Stickstoffdimer ist, wissen wir, dass die niedrigsten und höchsten Schwingungszustände Energien (Eigenwerte) zwischen 0 und 10 eV haben, und da $e^{0}=1$ , haben wir $L=1$ und $M = e^{-\frac{i}{\hbar} 10 \rm{eV} \cdot 10 \rm{ps}}$. Sie können eV in Hz und ps in Sekunden konvertieren, um$M$numerischauszuwerten, und dann können Sie die unteren und oberen Grenzen erhalten, die Sie beim Skalieren Ihrer Matrix verwenden müssen, wie Sie es in Ihrer vorherigen Frage beschrieben haben. Zu keinem Zeitpunkt musste ich die Eigenwerte eines 14-Elektronen-Molekül-Hamilton-Operators berechnen (was extrem schwierig wäre und den Zweck der Verwendung von HHL zunichte machen würde, denn wenn ich die Eigenwerte berechnen könnte, könnte ich einfach$A$berechnenund invertieren, um|zu erhalten& psgr;⟩$|\psi\rangle$). Ich habe nur die Dissoziationsenergie des Moleküls verwendet, um die Grenzen seiner Schwingungsenergien zu ermitteln. Ich hätte mit der halbklassischen WKB-Näherung noch bessere Grenzen finden können , auch mit viel geringeren Kosten als die tatsächliche Berechnung der Eigenwerte, aber das erste Beispiel reicht bereits aus.

Lassen Sie uns nun alle Ihre individuellen Fragen beantworten:

Erste Gruppe von Fragen: Ich habe viele Artikel über HHL gelesen und keiner von ihnen erwähnte diese Einschränkung. Warum? Ist diese Einschränkung bekannt, wird sie jedoch als schwach angesehen (dh es ist einfach, diese Art von Informationen zu haben)? Oder war die Einschränkung nicht bekannt? Gibt es ein Forschungspapier, das diese Einschränkung erwähnt?

Von den 539 Arbeiten, die (derzeit) die ursprüngliche HHL-Arbeit zitiert haben, kennen viele die feineren Details wie die Abhängigkeit ihrer Leistung von der Bedingungszahl oder den Eigenwerten nicht. Einige der Artikel werden sicherlich wissen, dass die Leistung des Algorithmus von der Bedingungsnummer oder den Eigenwerten der Matrix abhängt, nämlich den in Ihrer Tabelle aufgeführten Artikeln zu Verbesserungen des HHL-Algorithmus. Robin Kothari erwähnte dies beispielsweise auch zu Beginn seines Vortrags 2016 über den CKS-Algorithmus (der in Ihrer Tabelle erwähnt wird).

Zweite Gruppe von Fragen: Gibt es einen besseren Algorithmus hinsichtlich der Komplexität? Wenn nicht, warum wird der HHL-Algorithmus dann immer noch als exponentielle Verbesserung gegenüber klassischen Algorithmen dargestellt?

Der von DaftWulie vorgeschlagene Algorithmus zur Schätzung der Grenzen der Eigenwerte wird nicht verbessert $\mathcal{O}(\sqrt{N})$$N$$s \lll N$$\mathcal{O}(\sqrt{N})$

Sie haben Recht, die Leute sollten die Vorbehalte von Algorithmen in ihren Arbeiten häufiger erwähnen. In Bezug auf Ihre spezifische Frage "Warum wird der HHL-Algorithmus immer noch als exponentielle Verbesserung gegenüber klassischen Algorithmen dargestellt?" Skalierung, aber die Kosten steigen quadratisch mit der Bedingungsnummer und der Sparsity und umgekehrt mit der Größe des Fehlers, den Sie tolerieren möchten. Warum erwähnen die meisten anderen Menschen nach HHL nicht alle Vorbehalte? Nun, viele von ihnen kennen die Vorbehalte nicht, und diejenigen, die dies getan haben, haben möglicherweise das Gefühl, dass dies nicht notwendig ist, da die Berechnung der Bedingungsnummer nicht Teil des Algorithmus ist. Wenn Sie die Bedingungsnummer kennen, erfahren Sie, wie gut der Algorithmus funktioniert.