QUBO, Ising Hamiltonians e VQA
Capisco che di solito i problemi di ottimizzazione combinatoria vengono trasformati in QUBO, che ha una mappatura molto semplice con le Hamiltoniane di Ising. Le Hamiltoniane di Ising a loro volta hanno le proprietà desiderate di essere diagonali in base computazionale e lo stato fondamentale è uno dei vettori base computazionali. È quindi facile misurare lo stato nella base computazionale e ottenere la soluzione della stringa di bit.
Il problema è che l'Hamiltoniana di Ising e QUBO sono quadratiche nei suoi termini e consentono al massimo 2 interazioni corporee. Recentemente mi sono imbattuto in un articolo sulla fattorizzazione di interi espressi come problema di ottimizzazione ( fattorizzazione quantistica di 56153 con soli 4 qubit ), dove la funzione di costo è un polinomio di terzo grado. Sono stato in grado di ridurre questo a 2 interazioni del corpo e quindi rendere il problema QUBO, mapparlo su Ising Hamiltonian e risolverlo su macchine IBM utilizzando QAOA. Tuttavia, questa conversione dal polinomio di grado 3 al grado 2 mi costa qubit extra.
Qual è quindi l'approccio generale quando hai 3/4 interazioni corporee, ad esempio come in questo documento ho collegato? Gli autori di questo, così come gli autori di lavori precedenti che citano, non si preoccupano del fatto che questo non sia QUBO. Ci sono alternative agli Hamiltoniani Ising e ai QUBO in questi casi? È corretto che si possa usare qualsiasi forma di Hamiltoniano (non necessariamente Ising) per QAOA / VQE purché sia scomponibile in prodotti tensoriali di operatori Z di Pauli (il che lo rende diagonale in base computazionale)?
Risposte
Nella definizione di questo articolo [ 1 ] l'Hamiltoniana dei costi non è limitata al caso Hamiltoniano di Ising. Il documento [ 1 ] ha anche una risposta per il citato "approccio generale per$3/4$ ($n$) interazioni corporee ".
Una citazione diretta da [ 1 ]:
Da una classica funzione di costo che è un polinomio in variabili binarie $x_1 , . . . , x_n $, possiamo costruire un hamiltoniano $H_C$ sopra $n$ qubit riscrivendo prima la funzione di costo in termini di variabili $z_i \in \{−1, 1 \}$, dove $x_i = (1 − z_i )/2$ per ottenere un polinomio $f (z) = \sum_{C \subset \{1,...n\}} \alpha_C \prod_{j \in C} z_j$ e quindi sostituire ogni occorrenza di $z_i$ con l'operatore Pauli $\sigma_i^z$. Quindi,$H_C$ è diagonale in $\sigma_z$-base e assume la forma
$$H_C = \sum_{C \subset \{1,...,n\}} \alpha_C \bigotimes_{j \in C} \sigma_i^z \tag{2}$$
dove $C$ è un sottoinsieme di tutti i qubit e $\alpha_C$ è un coefficiente reale per l'accoppiamento a molti corpi tra i qubit nel sottoinsieme $C$.
Ciò significa che se abbiamo una funzione di costo classica$f(x) = 4 x_1 +6x_1 x_2 - 2x_2 x_3 x_4$, dovremmo sostituire $x$s con $z$se ottieni:
$$f(z) = 2(1 - z_1) + 3 (1 - z_1) (1 - z_2) - (1 - z_2) (1 - z_3) (1 - z_4)$$
Dopo aver semplificato sostituire $z$s con $\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$$
e fatto. Nota che questa procedura funzionerà anche per QUBO$\rightarrow$Ising Hamiltonian (vedi questa risposta ). In questo modo saremo in grado di costruire l'Hamiltoniana del costo con la proprietà desiderata (in QAOA):
$$H_C |x\rangle = f(x)|x\rangle$$
dove $x = x_1 x_2 x_3 x_4$ è una stringa di bit.
Un esempio dell'Hamiltoniana dei costi con$3$-body accoppiamento tra qubit può essere trovato in questo articolo [ 2 ] per il problema E3LIN2 ([ 2 ] Eq.$6$ con notazioni leggermente modificate):
$$ H_C = \frac{1}{2} \sum_{a < b < c} d_{abc} \sigma_a^z \sigma_b^z \sigma_c^z \tag{6}$$
dove $d_{abc}$ è $0$ o $+1$ o $-1$, $a$, $b$ e $c$ sono indici qubit.
[ 1 ] Z. Wang, S. Hadfield, Z. Jiang, EG Rieffel, "The Quantum Approximation Optimization Algorithm for MaxCut: A Fermionic View"
[ 2 ] E. Farhi, J. Goldstone, S. Gutmann, "A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem"