Was könnten mögliche zukünftige Anwendungen für den HHL-Algorithmus sein?

14

Anmerkung zum Wortschatz: In dieser Frage wird das Wort "Hamiltonian" verwendet, um über Hermitianische Matrizen zu sprechen.


Der HHL-Algorithmus scheint ein aktiver Forschungsgegenstand auf dem Gebiet des Quantencomputers zu sein, vor allem, weil er ein sehr wichtiges Problem löst, das darin besteht, die Lösung eines linearen Gleichungssystems zu finden.

Gemäß dem Originalpapier Quantenalgorithmus zum Lösen linearer Gleichungssysteme (Harrow, Hassidim & Lloyd, 2009) und einigen auf dieser Site gestellten Fragen

Der HHL-Algorithmus ist auf bestimmte Fälle beschränkt. Hier ist eine Zusammenfassung (die möglicherweise unvollständig ist!) Der Merkmale des HHL-Algorithmus:


HHL-Algorithmus

Der HHL-Algorithmus löst ein lineares System der Gleichung mit den folgenden Einschränkungen:

A|x=|b

Einschränkungen für :A

Einschränkungen bei :|b

  • sollte effizient herstellbaren sein. Dies ist der Fall für: |b
    1. Spezifische Ausdrücke . Zum Beispiel der Staat | b = n i = 0 ( | 0 + | 1 |b ist effizient herstellbar.
      |b=i=0n(|0+|12)
    2. , die die Diskretisierung einer effizienten integrierbare Wahrscheinlichkeitsverteilung (sieheÜberlagerungendass entsprechen effizient integrierbare Wahrscheinlichkeitsverteilungen erstellen (Grover & Rudolph, 2002)).|b

Einschränkungen bei (Ausgang):|x

  • kann nicht vollständig durchMessung gewonnen werden. Die einzige Informationwir wiederherstellen können von | x ist ein „allgemeine Informationen“ wie ( „Erwartungswert“ der Begriff in dem ursprünglichen HHL Papier beschäftigt ist)x | M | x |x|x
    x|M|x

Frage: Unter Berücksichtigung all dieser Einschränkungen und der Vorstellung, dass wir im Jahr 2050 (oder vielleicht im Jahr 2025, wer weiß?) Mit fehlertoleranten großen Quantenchips (dh wir sind nicht durch die Hardware beschränkt) Probleme in der realen Welt haben könnte der HHL-Algorithmus lösen (einschließlich der Probleme, bei denen HHL nur als Unterprogramm verwendet wird)?

Mir ist die Arbeit Konkrete Ressourcenanalyse des quantenlinearen Systemalgorithmus zur Berechnung des elektromagnetischen Streuquerschnitts eines 2D-Ziels (Scherer, Valiron, Mau, Alexander, van den Berg & Chapuran, 2016) und die entsprechende Implementierung in bekannt die Programmiersprache Quipper und ich suche nach anderen Beispielen aus der Praxis, bei denen die HHL in der Praxis anwendbar wäre. Ich habe kein veröffentlichtes Papier benötigt, nicht einmal ein nicht veröffentlichtes Papier, ich möchte nur einige Beispiele haben reale Anwendungsfälle.


BEARBEITEN:

Auch wenn ich an jedem Anwendungsfall interessiert bin, würde ich einige Beispiele vorziehen, bei denen HHL direkt verwendet wird, dh nicht als Unterprogramm eines anderen Algorithmus verwendet wird.

Ich interessiere mich noch mehr für Beispiele linearer Systeme, die aus der Diskretisierung eines Differentialoperators resultieren und mit HHL gelöst werden könnten.

Aber lassen Sie mich noch einmal betonen, dass mich jeder Anwendungsfall (Unterprogramme oder nicht) interessiert, den Sie kennen .

Nelimee
quelle
Sie erwähnen, dass Sie einige Beispiele wünschen, bei denen die HHL "direkt verwendet" wird. Ich weiß nicht genau, was Sie damit meinen. Ich kenne einige Algorithmen (die möglicherweise praktische Anwendungen haben können), bei denen die HHL einer der Hauptschritte ist, aber sicherlich nicht der einzige . Wäre es eine geeignete Antwort , genetische Sequenzen mithilfe von HHL als einen der Hauptschritte zu erkennen (vorbehaltlich aller von Ihnen genannten Einschränkungen)? Die anderen Hauptschritte umfassen hauptsächlich Hamilton-Simulation und Zustandsvorbereitung.
Sanchayan Dutta
Ich würde einige Beispiele bevorzugen, bei denen die HHL direkt verwendet wird. Dies bedeutet, dass das zu lösende Problem direkt als lineares Gleichungssystem formuliert werden kann. Dies ist der Fall bei der Lösung von Differentialgleichungen: Wir diskretisieren die Gleichung und lösen das diskretisierte Problem, das die meiste Zeit ein spärliches lineares System ist. Andere Beispiele sind jedoch zu begrüßen.
Nelimee

Antworten:

4

Vor einigen Jahren wurde in Quantenalgorithmen und der Finite-Elemente-Methode von Montanaro und Pallister gezeigt, dass der HHL-Algorithmus auf die Finite-Elemente-Methode (FEM) angewendet werden kann Probleme (BVPs) für partielle Differentialgleichungen, basierend auf der Diskretisierung des Parameterraums über ein endliches Netz " .

Sie zeigten, dass in diesem Zusammenhang mit HHL (vielleicht höchstens) eine polynomielle Beschleunigung gegenüber dem klassischen Standardalgorithmus (der "konjugierten Gradientenmethode") erzielt werden kann.

In Bezug auf reale Anwendungsfälle geben sie dies an

n

A

SLesslyTall
quelle
2
Ich habe momentan keine Zeit, den Artikel zu lesen, aber aus der Zusammenfassung geht hervor, dass das Papier interessant ist. Ich habe den Abschnitt III schnell gelesen und konnte keine Hinweise auf die Eigenwerte von findenM Mss=3
0

Rebentrost et al. haben kürzlich den HHL09-Algorithmus in ihrem Artikel A Quantum Hopfield Neural Network (2018) zur Optimierung der Energiefunktion des Hopfield-Netzwerks verwendet.

Grundsätzlich gilt, wenn der Lagrange (der zur Optimierung der Netzenergie verwendet wird) E=-12xTWx+θTx gegeben die Einschränkung Px-x(inc)=0) ist:

L=-12xTWx+θTx-λT(Px-x(inc))+γ2xTx
dann die Optimierungsgleichungen Lx=0 und Lλ=0 kann in das Formular geschrieben werden EINv=w. Notiere dass derγim Ausdruck ist der Regularisierungsparameter. Wir müssen findenv was die Netzwerkenergie extremisiert, die der Beschränkung unterliegt Px=x(inc)und deshalb brauchen wir eine Matrixinversionstechnik. In dem Artikel haben sie genau das getan und für die Matrixinversion den HHL09-Algorithmus verwendet. Siehe Seite 4 des Papiers.


Kurz gesagt, ich glaube, sobald wir Quantencomputer mit einer ausreichend großen Anzahl von Qubits und Dekohärenzzeiten haben, wird der HHL-Algorithmus eine der nützlichsten Unterroutinen für jeden Algorithmus des quantenmaschinellen Lernens (da fast alle maschinellen Lernvorgänge und neuronalen Netze) sein Algorithmen beinhalten irgendeine Form von "Gradientenabstieg" oder "Optimierung".

Sanchayan Dutta
quelle