A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation

Sintesi Tecnica: Un Algoritmo di Ricerca Quantistica Non Strutturata per l'Ottimizzazione Discreta

Definizione del Problema
Il documento affronta la sfida di risolvere problemi di ottimizzazione discreta, nello specifico l'ottimizzazione combinatoria, dove le variabili sono binarie e le derivate non possono essere definite. Mentre i metodi basati sul gradiente sono efficaci per le variabili continue, essi falliscono negli spazi discreti, che sono spesso NP-hard. Gli approcci quantistici esistenti, come il framework Quadratic Unconstrained Binary Optimisation (QUBO), sono limitati a funzioni obiettivo che contengono solo termini del primo e secondo ordine. Inoltre, molti algoritmi di ottimizzazione quantistica attuali (ad esempio, gli algoritmi quantistici variazionali) si affidano a loop ibridi classico-quantistici che possono soffrire di rumore o richiedere circuiti profondi. Gli autori propongono un metodo per trovare gli estremi o le radici di funzioni discrete generali, $f(x)$, che possono contenere termini di ordine superiore oltre il limite quadratico del QUBO.

Metodologia: L'Algoritmo QSERA
Gli autori introducono il Quantum Search for Extrema and Roots Algorithm (QSERA), un membro della famiglia di algoritmi di ricerca quantistica (QSA) basati sull'algoritmo di Grover. La metodologia procede in due fasi primarie:

1. Costruzione dell'Oracolo ($f(x) \to u(z)$):
   La prima fase consiste nel mappare la condizione di ricerca di un estremo (o di una radice) $f(x^*) \approx f^*$ in un problema di ricerca non strutturata per una stringa binaria $z^*$.

   • Riscalamento: La funzione obiettivo $f(x)$ viene riscalata in una funzione $g(x) \in [0, 1]$. Per la massimizzazione, $g(x) = (f(x) - f_{min}) / (f_{max} - f_{min})$; per la minimizzazione, $g(x) = (f_{max} - f(x)) / (f_{max} - f_{min})$; per la ricerca di una radice, viene applicata una trasformazione specifica. Ciò richiede la conoscenza a priori o stime del minimo globale ($f_{min}$) e del massimo globale ($f_{max}$).
   • Amplificazione: Per creare un oracolo binario $u(z)$ dove $u(z^*) = 1$ e $u(z \neq z^*) = 0$, la funzione $g(x)$ viene elevata a una potenza elevata $n$ (ovvero $u_n(z) \equiv g(x)^n$). Man mano che $n \to \infty$, $u_n(z)$ si avvicina all'oracolo ideale.
   • Generalizzazione: Il documento nota che $f(x)$ può essere un polinomio generale con termini fino all'ordine $K$ (Eq. 10), consentendo funzioni obiettivo più complesse rispetto alla forma standard del QUBO.
   • Implementazione delle Porte: Gli autori derivano il circuito quantistico per l'oracolo. Definiscono operatori auto-aggiunti $B_k$ corrispondenti alle variabili binarie e costruiscono un operatore unitario $G$ tale che $G|z\rangle = g(x)|z\rangle$. L'operatore oracolo $Q^*$ è quindi definito come $e^{i\pi G^n}$. Questo viene decomposto in un prodotto di operatori unitari $Q^*_j$ per ogni ordine di termine (ordine zero, primo, secondo, ecc.), implementati utilizzando qubit ancilla e porte di spostamento di fase (phase shift gates).

2. Esecuzione della Ricerca:
   Una volta costruito l'oracolo $Q^*$, l'algoritmo impiega l'operatore di diffusione di Grover ($Q_+$) e l'oracolo ($Q^*$) in un ciclo iterativo. Lo stato viene inizializzato in una sovrapposizione uniforme e l'operatore $(Q_+ Q^*)$ viene applicato $m_{opt} \approx (\pi\sqrt{N} - 2)/4$ volte per amplificare l'ampiezza dello stato target $|z^*\rangle$.

Contributi Chiave

• Generalizzazione oltre il QUBO: A differenza di molti metodi di ottimizzazione quantistica limitati a forme quadratiche, QSERA può gestire funzioni obiettivo con termini di ordine superiore (cubici, quartici, ecc.), rendendolo applicabile a una classe più ampia di problemi combinatori.
• Costruzione Esplicita del Circuito: Il documento fornisce una derivazione matematica dettagliata per la costruzione delle porte dell'oracolo quantistico per arbitrarie ordini polinomiali, inclusi il calcolo ricorsivo dei coefficienti richiesti per i parametri del circuito.
• Gestione di Limiti Approssimativi: Gli autori analizzano lo scenario in cui $f_{min}$ e $f_{max}$ non sono noti esattamente. Dimostrano che, sebbene l'algoritmo possa ancora funzionare con delle stime, la probabilità di trovare l'esatto ottimo dipende dalla scelta del parametro di potenza $n$. Se $n$ è troppo grande, il segnale dell'oracolo può svanire; se troppo piccolo, il segnale non è abbastanza distinto. Esiste un $n$ ottimale per bilanciare questi fattori.

Caso di Studio: Ottimizzazione di Portafoglio
Gli autori validano QSERA utilizzando un problema di ottimizzazione di portafoglio con $N_a = 4$ asset, che risulta in $N=16$ possibili portafogli.

• Configurazione: L'obiettivo era trovare un portafoglio di 2 asset che minimizzasse la distanza dal rendimento di riferimento e dalla volatilità. La funzione obiettivo includeva termini fino al quarto ordine.
• Implementazione: Un circuito quantistico è stato assemblato utilizzando 4 qubit per gli stati del portafoglio, 2 qubit ancilla per le operazioni AND e 1 ancilla per il tracciamento della fase.
• Prestazioni:
  • Con il numero ottimale di iterazioni di Grover ($m_{opt} = 2$) e un valore di $n$ scelto accuratamente ($n \approx 24$), l'algoritmo ha identificato con successo il portafoglio ottimale (stato $|1001\rangle$) con la probabilità più alta.
  • Anche il secondo miglior portafoglio ($|0101\rangle$) ha mostrato una probabilità relativamente alta, riflettendo il fatto che l'algoritmo ha trovato la soluzione più vicina ai limiti stimati.
  • Lo studio ha confermato che se $f_{min}$ e $f_{max}$ sono stimati anziché esatti, la probabilità di misurare il vero ottimo è inferiore a 1, rendendo necessari molteplici "shot" (esecuzioni ripetute) per distinguere il vero ottimo dalle soluzioni quasi ottimali.
  • La relazione tra la potenza $n$ e la probabilità di successo è stata visualizzata, mostrando un picco di probabilità per valori intermedi di $n$, con prestazioni che degradano se $n$ è troppo grande (soppressione del segnale) o troppo piccolo (discriminazione insufficiente).

Significato e Rivendicazioni
Il documento afferma che QSERA offre un accelerazione quadratica ($O(\sqrt{N})$) rispetto alla ricerca brute-force classica per trovare estremi o radici di funzioni discrete. La sua importanza primaria risiede nella sua capacità di:

1. Risolvere problemi di ottimizzazione con funzioni obiettivo di ordine superiore che sono incompatibili con le formulazioni standard QUBO.
2. Operare senza la necessità di loop di ottimizzazione dei parametri classico-quantistici ibridi (a differenza dei VQA), affidandosi invece a un'esecuzione quantistica "single-shot" (sebbene possano essere necessari più shot per la confidenza statistica se i limiti sono approssimativi).
3. Affrontare potenzialmente funzioni continue con "rumore" o gradienti ripidi (dopo la discretizzazione) dove i metodi basati sul gradiente potrebbero fallire, sebbene gli autori notino che la ricerca strutturata è generalmente più efficiente per le variabili continue.

Gli autori concludono che, sebbene l'algoritmo richieda la conoscenza dei limiti della funzione per una garanzia di successo, rimane uno strumento robusto per l'ottimizzazione discreta, particolarmente quando la struttura della funzione obiettivo eccede le capacità degli approcci basati su QUBO correnti.