Gibt es eine allgemeine Methode, um Optimierungsprobleme als Hamiltonianer auszudrücken?

Nehmen wir an, wir haben ein Optimierungsproblem in der Form:

$$\min_x f(x) \\ g_i(x) \leq 0, i = 1, ..., m \\ h_j(x) = 0, j = 1, ..., p,$$

wobei eine Zielfunktion ist, sind Ungleichheitsbeschränkungen und Gleichheitsbeschränkungen.$f(x)$$g_i(x)$$h_j(x)$

Kürzlich habe ich über das adiabatische Quantencomputing gelesen . Die Wikipedia sagt:

Zunächst wird ein (möglicherweise komplizierter) Hamilton-Operator gefunden, dessen Grundzustand die Lösung des interessierenden Problems beschreibt. Als nächstes wird ein System mit einem einfachen Hamilton-Operator vorbereitet und auf den Grundzustand initialisiert. Schließlich wird der einfache Hamiltonianer adiabatisch zum gewünschten komplizierten Hamiltonianer entwickelt. Nach dem adiabatischen Theorem bleibt das System im Grundzustand, so dass am Ende der Zustand des Systems die Lösung des Problems beschreibt. Es wurde gezeigt, dass adiabatisches Quantencomputing im Schaltungsmodell polynomiell äquivalent zu herkömmlichem Quantencomputing ist.

Gibt es eine allgemeine Methode, um das Optimierungsproblem (z. B. wie oben dargestellt) im Hamilton-Formalismus auszudrücken, der beim adiabatischen Quantencomputing verwendet wird ?

Wie in den Kommentaren angefordert, ist hier ein Beispiel. Der Hauptteil befasst sich mit der Minimierung von $f(x)$ für ein bestimmtes Problem. Unten folgt eine kurze Diskussion der Einschränkungen, dann eine kurze Diskussion des allgemeinen Falls.

Lösen wir seitdem das Problem des gewichteten maximalen Schnitts

1. Ist ein relativ einfaches Beispiel
2. Ist klassisch schwer
3. Ist ein relativ häufiges Beispiel in der Literatur (z. B. https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.90.067903 )
4. Hat eine klare Verbindung zu einem physischen Hamiltonianer (Ising Spin-Brille)

Um das Problem zu verstehen, beginnen wir mit einem ungerichteten Graphen von $n$ Eckpunkten $\{V\}$ , wobei jeder Eckpunkt $v_i\in V$ das Gewicht $w_i\geq0$ und jede Kante, die $v_i$ und $v_j$ verbindet, ein Gewicht $w_{ij}\geq0$ . Wir schneiden dann die Grafik in zwei Teile. Der Schnitt muss nicht gerade sein, darf sich aber nicht selbst schneiden und darf keine Kante zweimal schneiden. Dann berechnen wir eine " Auszahlung " $P$für unseren Schnitt. Die Auszahlung ist die Summe der Gewichte der Kanten, die wir durchschneiden, plus der Summe der Gewichte der Eckpunkte auf einer Seite des Schnitts. 1$^1$

Quelle

In diesem Bild wäre die Auszahlung $1+4+3+3+2 = 13$ für die Kanten plus $5+6+1 = 12$ für die Eckpunkte $\to P=25$ (vorausgesetzt, die Zahl in jedem Eckpunkt ist sein Gewicht). Das Optimierungsproblem besteht darin, $P$ für einen gegebenen Graphen zu maximieren . 2$^2$

Um dies mathematisch zu schreiben, können wir in Bitfolgen denken. Wir definieren einen Schnitt durch ein String $s\in\{0,1\}^n$ wobei $s_i=0\to v_i$ ist nicht in der Summe gezählt und $s_i=1\to v_i$ wird in der Summe gezählt. Um die Mathematik ein wenig sauberer zu machen, wenn der Graph nicht vollständig verbunden ist, machen Sie den Graph vollständig verbunden und setzen Sie $w_{ij}=0$ für alle nicht verbundenen Paare $v_i,v_j$ .

Wenn wir beispielsweise das obige Bild noch einmal betrachten, interpretieren wir die Zahlen innerhalb der Scheitelpunkte als Scheitelpunktindex anstelle des oben angenommenen Gewichts. Dann entspricht der gezeichnete Schnitt $s=100011$ . $s_1=s_5=s_6=1\to v_1, v_5, v_6$ sind auf der "guten" Seite des Schnitts und werden gezählt, während $s_2=s_3=s_4=0$ auf der "schlechten" Seite sind. Seite des Schnitts und werden nicht gezählt.

Dies ermöglicht es uns dann, P ( s ) = ∑ i s i w i + ∑ i , j s i ( 1 - s j ) w i j zu schreiben

$$P(s) = \sum_i s_i w_i + \sum_{i,j} s_i(1-s_j)w_{ij}$$

Der erste Term zählt nur die Gewichte aller Eckpunkte auf der "guten" Seite des Schnitts. Der zweite Term zählt das Gewicht einer Kante, wenn sich die Eckpunkte, die sie verbindet, auf gegenüberliegenden Seiten des Schnitts befinden. Beachten Sie, dass dies nicht doppelt zählt, da es nur die Kante zählt, wenn $s_i=1, s_j=0$ und nicht, wenn $s_i=0, s_j=1$ .

Unser Optimierungsproblem besteht nun darin, die Zeichenfolge $s$ , die $P(s)$ maximiert . Die Idee hier ist, $P(s)$ als ein Maß für die Energie eines Systems und $s$ als den Zustand des Systems zu betrachten. Dies bedeutet, dass wir $P(s)$ mit unserem Hamilton-Operator in Beziehung setzen können . Es gibt hier eine leichte Subtilität, dass wir versuchen, $P(s)$ zu maximieren, aber wir sprechen normalerweise darüber, den Grundzustand eines Hamiltonianers zu finden. Dies ist kein Problem, aber ich wollte darauf hinweisen - wir können stattdessen den angeregten Zustand mit der höchsten Energie (Anti-Boden-Zustand, wenn Sie so wollen) betrachten oder $-P(s)$ als unsere Energiefunktion arbeiten dann wie gewohnt mit dem Grundzustand. Lassen Sie uns mit dem höchsten angeregten Zustand arbeiten und$P$ maximieren.

Wir möchten einen Hamilton-Operator so erstellen, dass sein höchster Energiezustand $|s_0\rangle$ , so daß $P(s_0)$ , maximal ist. Im Wesentlichen wollen wir drehen $P(s)$ , eine Energiefunktion, in H , einen Energiebetreiber. Wir tun dies, indem wir feststellen, dass für | s ⟩ & egr ; { | 0 ⟩ , | 1 ⟩ } wir haben I - Z$\hat{H}$$|s\rangle\in\{|0\rangle,|1\rangle\}$

$$\frac{I-Z}{2}|s\rangle=s|s\rangle\to\text{ define } \hat{s}_i=\frac{I-Z_i}{2}$$

Wobei $Z_i$ das Pauli $Z$ , das auf Qubit $i$ wirkt . Jetzt bekommen wir unsere Hamilton - durch Ersetzen $s$ mit s (und 1 mit I ) in P$\hat{s}$$I$$P$

$$H=\sum_i \hat{s}_i w_i + \sum_{i,j} \hat{s}_i(I-\hat{s}_j)w_{i,j}=\sum_i\frac{I-Z_i}{2} w_i + \sum_{i,j} \frac{I-Z_i}{2}\left(I-\frac{I-Z_j}{2}\right)w_{i,j}$$

Dies kann durch Erweitern und Anzeigen von ∑ i , j ( Z i - Z j ) = 0 → bereinigt werden$\sum_{i,j}(Z_i-Z_j)=0\to$

$$H=\sum_i \frac{w_i}{2}\left(I-Z_i\right) + \sum_{i,j} \frac{w_{ij}}{4}\left(I-Z_iZ_j\right)=\sum_i \frac{w_i}{2}\left(I-Z_i\right) + \sum_{i<j} \frac{w_{ij}}{2}\left(I-Z_iZ_j\right)$$

Wir können dies noch weiter bereinigen, indem wir mit 2 multiplizieren und eine konstante Energieverschiebung entfernen (die $I$ Terme löschen ). Neuer Hamilton-Operator mit denselben Eigenzuständen mit skalierten und verschobenen Eigenwerten (die maximale Energie wird von diesen Transformationen eindeutig nicht beeinflusst)

$$H=-\sum_i w_iZ_i - \sum_{i<j} w_{ij}Z_iZ_j$$

Wenn Sie ein Physiker der kondensierten Materie sind, werden Sie diesen Hamiltonianer wahrscheinlich als Ising-Spinglas erkennen. Nicht wirklich relevant für das Problem, aber ich finde es cool.

Jetzt haben wir also einen Hamilton-Operator, dessen (Anti-) Grundzustand die Bitfolge $s_0$ codiert, die $P(s)$ maximiert und das Problem löst.

Das Letzte, was wir brauchen, ist ein anfänglicher Hamilton- $H_0$ , den wir langsam (adiabatisch) in unseren endgültigen Hamilton- $H$ umwandeln, damit wir den vollständigen Hamilton-

$$H_T(t)=(1-f(t))H_0 + f(t)H: f(0)=0, f(t_f)=1$$

Als Ausgangspunkt wird $f(t)\propto t$ der Einfachheit halber häufig verwendet. Das Minimum $t_f$ wird durch die gewünschte Genauigkeit und die Spektrallücke 3 bestimmt . Die spektrale Lücke ist die minimale Energiedifferenz über alle t zwischen dem (Anti) Grundzustand und dem nächsten Energiezustand. Die Analyse der Lücke ist höchst nicht trivial (siehe https://arxiv.org/abs/quant-ph/0509162 ) und bestimmt die Komplexität / Effizienz des Algorithmus. Es ist nicht garantiert, dass ein Algorithmus mit einer Lücke von 0 überhaupt funktioniert.$^3$$t$

Wir wollen also ein $H_0$ so dass

1. Wir können seinen (Anti) Grundzustand leicht finden und vorbereiten
2. Die spektrale Lücke von $H$ ist in der Größe des Problems nicht exponentiell klein

Für dieses Problem ist ein guter anfänglicher Hamilton-Operator $H_0 = \sum_i X_i$ weil sein höchster Energiezustand leicht zu finden ist, es ist $|+\rangle^{\otimes n}$ . Es ist einfach vorzubereiten, wenden Sie einfach $H^{\otimes n}$ auf $|0\rangle^{\otimes n}$ . Ich habe keine Zeit, mich mit der Analyse der spektralen Lücke zu befassen, aber dieser Hamilton-Operator ist in dieser Hinsicht wahrscheinlich nicht ideal (siehe https://arxiv.org/abs/1701.05584 ).

$H_0$$f(t)=t/t_f$

$$H(t) = \left(1-f(t)\right)\sum_i X_i-f(t)\left[\sum_i w_iZ_i + \sum_{i<j} w_{ij}Z_iZ_j\right]$$

$|\psi_0\rangle = H^{\otimes n}|0\rangle^{\otimes n}$$t_f$$t_f$$s=s_0$$P(s)$

$^1$

$^2$$=-$

$^3$$H$

Einschränkungen

$5$$\sum_i s_i-5=0$$H_c = -\alpha\left(\sum_i \hat{s}_i -5I\right)^2$$\alpha$

$5$$k$$\mathcal{O}\left(N^{2k}\right)$ $k$$k^\text{th}$Ordnungspolynom. Dies scheint ein schrecklicher Weg zu sein - aber ich kann mir keinen besseren Weg vorstellen. Dies kommt von Troyer im Jahr 2017, so dass es relativ unwahrscheinlich, aber durchaus möglich ist, dass derzeit ein besserer Weg bekannt ist.

Der allgemeine Fall

$f(x)$$f(x)$$f(x)$$\hat{f}(x)$$\hat{f}(x)|x\rangle=f(x) |x\rangle$

$$H = \sum_x \hat{f}(x)|x\rangle\langle x|$$ $\hat{f}(x)$$f(x)$