QAOA con penalità personalizzata tramite trasformata di Walsh-Hadamard

Abstract degli autori

Nell’ottimizzazione combinatoria, i vincoli di disuguaglianza vengono comunemente gestiti introducendo variabili di slack e penalità quadratiche, che aumentano il numero di qubit e distorcono il paesaggio di ottimizzazione. Le formulazioni senza variabili di slack applicano invece una funzione di penalità non lineare personalizzata direttamente al vincolo, ma queste funzioni sono difficili da implementare nell’algoritmo di ottimizzazione quantistica approssimata (QAOA). Mostriamo che la trasformata di Walsh-Hadamard (WHT) rimuove questo ostacolo per qualsiasi funzione di penalità: una penalità applicata a un vincolo lineare è esattamente una somma pesata di stringhe di Pauli-$Z$. Proponiamo questo quadro come Walsh custom penalty QAOA (WCP-QAOA). Troncare lo sviluppo al grado di Walsh $k$ richiede $\mathcal{O}(n^k)$ termini di Pauli e lascia invariato il numero di qubit. Il troncamento è l’approssimazione ottimale di grado-$k$ della penalità in $L^2$ e forniamo una condizione sui coefficienti di Walsh scartati in base alla quale l’Hamiltoniana troncata continua ad assegnare a ogni soluzione ammissibile un valore inferiore a quello di ogni soluzione non ammissibile. Poiché calcolare un coefficiente di Walsh dalla sua definizione richiede tutti i $2^n$ valori della penalità, forniamo un algoritmo che restituisce un qualsiasi coefficiente in tempo subesponenziale, così che l’Hamiltoniana di grado-$k$ si ottiene in tempo polinomiale in $n$ per $k$ fissato. Mostriamo che, per la penalità esponenziale, esiste una forma di prodotto chiusa della WHT e, di conseguenza, un’espressione in forma chiusa per calcolare i coefficienti di Walsh. Individuiamo scorciatoie strutturali che accorciano lo spettro esatto. Abbiamo inoltre testato WCP-QAOA per risolvere un problema di knapsack a 6 qubit.