QUBO, Ising Hamiltonians und VQA
Ich verstehe, dass die kombinatorischen Optimierungsprobleme normalerweise in QUBO umgewandelt werden, das eine sehr einfache Zuordnung zu Ising Hamiltonianern aufweist. Ising Hamiltonianer haben wiederum die gewünschten Eigenschaften, in rechnerischer Basis diagonal zu sein, und der Grundzustand ist einer der rechnerischen Basisvektoren. Es ist somit einfach, den Zustand in der Berechnungsbasis zu messen und die Bitfolgenlösung zu erhalten.
Das Problem ist, dass Ising Hamiltonian und QUBO in ihren Begriffen quadratisch sind und höchstens 2 Körperinteraktionen zulassen. Ich bin kürzlich auf ein Papier über Integer-Factoring gestoßen, das als Optimierungsproblem ausgedrückt wird ( Quantenfaktorisierung von 56153 mit nur 4 Qubits ), bei dem die Kostenfunktion ein Polynom dritten Grades ist. Ich konnte dies auf 2 Körperinteraktionen reduzieren und so das Problem QUBO machen, es Ising Hamiltonian zuordnen und es auf IBM-Maschinen mit QAOA lösen. Diese Umwandlung zwischen Polynom Grad 3 und Grad 2 kostet mich jedoch zusätzliche Qubits.
Was ist dann der allgemeine Ansatz, wenn Sie 3/4 Körperinteraktionen haben, zum Beispiel wie in diesem Artikel, den ich verlinkt habe? Die Autoren dieses Artikels sowie die Autoren früherer Werke, die sie zitieren, befassen sich nicht mit der Tatsache, dass dies kein QUBO ist. Gibt es in solchen Fällen Alternativen zu Ising Hamiltonians und QUBOs? Ist es richtig, dass wir für QAOA / VQE jede Form von Hamilton (nicht unbedingt Ising) verwenden können, solange es in Tensorprodukte von Pauli Z-Operatoren zerlegbar ist (was es rechnerisch diagonal macht)?
Antworten
In der Definition aus diesem Artikel [ 1 ] sind die Kosten für Hamilton nicht auf den Fall Ising Hamilton beschränkt. Das Papier [ 1 ] hat auch eine Antwort auf den erwähnten "allgemeinen Ansatz für$3/4$ (($n$) Körperinteraktionen ".
Ein direktes Zitat aus [ 1 ]:
Aus einer klassischen Kostenfunktion, die ein Polynom in binären Variablen ist $x_1 , . . . , x_n $können wir einen Hamiltonianer konstruieren $H_C$ auf $n$ Qubits, indem zuerst die Kostenfunktion in Variablen umgeschrieben wird $z_i \in \{−1, 1 \}$, wo $x_i = (1 − z_i )/2$ ein Polynom erhalten $f (z) = \sum_{C \subset \{1,...n\}} \alpha_C \prod_{j \in C} z_j$ und dann jedes Vorkommen von ersetzen $z_i$ mit dem Pauli-Operator $\sigma_i^z$. So,$H_C$ ist diagonal in der $\sigma_z$-basis und nimmt die Form an
$$H_C = \sum_{C \subset \{1,...,n\}} \alpha_C \bigotimes_{j \in C} \sigma_i^z \tag{2}$$
wo $C$ ist eine Teilmenge aller Qubits und $\alpha_C$ ist ein realer Koeffizient für die Vielteilchenkopplung zwischen Qubits in der Teilmenge $C$.
Dies bedeutet , wenn wir eine klassische Kostenfunktion haben$f(x) = 4 x_1 +6x_1 x_2 - 2x_2 x_3 x_4$sollten wir ersetzen $x$s mit $z$s und erhalten:
$$f(z) = 2(1 - z_1) + 3 (1 - z_1) (1 - z_2) - (1 - z_2) (1 - z_3) (1 - z_4)$$
Nach der Vereinfachung ersetzen $z$s mit $\sigma_z$s:
$$H_C = 4 I - 5 \sigma_1^z - 2 \sigma_2^z + \sigma_3^z + \sigma_4^z + 3 \sigma_1^z \sigma_2^z -\sigma_2^z \sigma_3^z -\sigma_3^z \sigma_4^z -\sigma_2^z \sigma_4^z + \sigma_2^z \sigma_3^z \sigma_4^z$$
und fertig. Beachten Sie, dass dieses Verfahren auch für QUBO funktioniert$\rightarrow$Ising Hamiltonian (siehe diese Antwort ). Auf diese Weise können wir den Kosten-Hamilton-Operator mit der gewünschten (in QAOA) Eigenschaft konstruieren:
$$H_C |x\rangle = f(x)|x\rangle$$
wo $x = x_1 x_2 x_3 x_4$ ist eine Bitstring.
Ein Beispiel für die Kosten Hamiltonian mit$3$-Körperkopplung zwischen Qubits finden Sie in diesem Artikel [ 2 ] für das E3LIN2-Problem ([ 2 ] Gl.$6$ mit leicht geänderten Notationen):
$$ H_C = \frac{1}{2} \sum_{a < b < c} d_{abc} \sigma_a^z \sigma_b^z \sigma_c^z \tag{6}$$
wo $d_{abc}$ ist $0$ oder $+1$ oder $-1$, $a$, $b$ und $c$ sind Qubit-Indizes.
[ 1 ] Z. Wang, S. Hadfield, Z. Jiang, EG Rieffel, "Der Algorithmus zur Optimierung der Quantennäherung für MaxCut: Eine fermionische Ansicht"
[ 2 ] E. Farhi, J. Goldstone, S. Gutmann.