Displaced Gaussian Boson Sampling for enhanced max-clique search

Sintesi Tecnica: Campionamento di Bosoni Gaussiani Spostati per la Ricerca Potenziata del Max-Clique

Enunciato del Problema
Il Campionamento di Bosoni Gaussiani (GBS) si è affermato come una piattaforma promettente per dimostrare il vantaggio quantistico nella risoluzione di specifici problemi su grafi, in particolare la ricerca dei massimi clique (sottografi completi) in grafi non orientati pesati. La distribuzione di probabilità dei campioni GBS è legata all'hafniano di una matrice derivata dalla matrice di adiacenza del grafo. Tuttavia, le implementazioni pratiche del GBS affrontano ostacoli significativi: livelli di compressione limitati e elevate perdite di fotoni degradano le prestazioni del dispositivo, rendendo spesso il compito di campionamento simulabile classicamente. Sebbene gli stati coerenti (spostamenti) siano tipicamente considerati una risorsa classica a causa delle loro statistiche di Poisson, il loro potenziale utilizzo nel migliorare le prestazioni del GBS in condizioni realistiche e con perdite rimane una questione aperta.

Metodologia
Gli autori propongono e analizzano una variante del GBS denominata Campionamento di Bosoni Gaussiani Spostati (D-GBS). In questo schema, porte di spostamento vengono applicate a ciascuna modalità di uscita dell'interferometro, mescolando efficacemente stati coerenti con stati di vuoto compresso.

• Quadro Teorico: La probabilità di misurare un particolare pattern di numero di fotoni $n$ nel D-GBS è governata dalla funzione loop hafnian ($lHaf$), che generalizza l'hafniano standard. Il loop hafnian incorpora parametri di spostamento ($\gamma$) che modificano gli elementi diagonali della matrice utilizzata nel calcolo dell'hafniano.
• Codifica del Grafo: I grafi pesati sono mappati sull'esperimento GBS configurando i parametri di compressione e una rete unitaria passiva. La matrice di adiacenza viene riscalata per garantire la realizzabilità fisica.
• Post-Elaborazione Classica: Per estrarre il massimo clique dai campioni GBS grezzi, gli autori impiegano una routine euristica classica in due fasi:
  1. Riduzione Gredda: Rimuove casualmente vertici da un sottografo rilevato fino a formare un clique.
  2. Ricerca Locale: Cerca iterativamente di espandere il clique aggiungendo o scambiando vertici per massimizzare la dimensione e il peso del clique.
• Simulazione: Lo studio utilizza le librerie Python Strawberry Fields e The Walrus per simulare i campionatori GBS e D-GBS. Le prestazioni sono confrontate con il GBS standard, un campionatore uniforme e il "campionatore di Oh" (un algoritmo classico ispirato al quantum basato su interferenze a due fotoni).

Contributi e Risultati Chiave

1. Miglioramento in Condizioni di Bassa Compressione: Gli autori dimostrano che l'aggiunta di spostamento ($\gamma \neq 0$) aumenta significativamente il tasso di successo nella ricerca di clique a peso massimo quando la compressione disponibile è insufficiente per raggiungere il regime GBS ottimale. In scenari a bassa compressione, la probabilità di generare i necessari sottografi ad alta densità è diminuita; lo spostamento compensa ciò aumentando l'efficienza di segnalazione dei numeri di fotoni più elevati.
2. Resilienza alle Perdite: Lo studio mostra che il D-GBS è resiliente alle perdite di fotoni. Sebbene le perdite degradino generalmente le prestazioni del GBS, l'aggiunta di spostamento permette al sistema di mantenere un'alta probabilità di campionare il max-clique anche con perdite significative (ad esempio, il 50% per modalità). Lo spostamento può essere sintonizzato per compensare i fotoni persi, preservando la capacità di recuperare il max-clique dopo la post-elaborazione classica.
3. Scalabilità: Gli autori investigano la scalabilità del D-GBS per grafi più grandi. Scoprono che il vantaggio del D-GBS rispetto al GBS standard scala polinomialmente all'aumentare della dimensione del clique, a condizione che il rapporto tra i fotoni indotti dallo spostamento e quelli indotti dalla compressione sia gestito correttamente. Nello specifico, il numero medio di fotoni dallo spostamento dovrebbe scalare più lentamente di quello dalla compressione per mantenere il vantaggio relativo del loop hafnian.
4. Benchmarking: Nelle simulazioni che coinvolgono grafi di Erdős-Rényi, il campionatore D-GBS, quando combinato con la ricerca locale, supera sia il campionatore GBS standard (in condizioni di compressione vincolata) sia i campionatori puramente classici come il campionatore di Oh e il campionamento uniforme in termini di tasso di successo nella ricerca dei max-clique.

Significato e Affermazioni
Il paper afferma che lo spostamento funge da risorsa classica preziosa per migliorare l'utilità pratica del GBS per i problemi su grafi nell'era dei dispositivi Quantistici a Scala Intermedia e Rumorosi (NISQ).

• Praticità: Gli autori sottolineano che, sebbene l'alta compressione sia desiderabile, è spesso irraggiungibile o accompagnata da elevate perdite nelle configurazioni sperimentali attuali. Il D-GBS offre una via per migliorare le prestazioni in queste condizioni realistiche e imperfette.
• Accelerazione Modesta: Gli autori affermano esplicitamente di non rivendicare un vantaggio quantistico esponenziale. Invece, sostengono un "probabile vantaggio polinomiale" rispetto agli algoritmi stocastici classici (come il campionamento casuale o il campionatore di Oh) per la ricerca di max-clique in grafi a pesi non negativi.
• Complessità: La complessità computazionale della simulazione del D-GBS rimane difficile (relativa al loop hafnian #P-difficile) a condizione che il numero di fotoni coerenti ($N_{coh}$) rimanga inferiore al numero di fotoni compressi ($N_{sqz}$) in un specifico regime asintotico.
• Direzioni Future: Il lavoro suggerisce che la codifica di grafi a pesi complessi potrebbe estendere ulteriormente l'ambito delle applicazioni, ad esempio nell'analisi topologica dei dati, sebbene ciò rimanga una questione aperta per la ricerca futura.

In sintesi, il paper stabilisce che il D-GBS è un'alternativa robusta al GBS standard per la ricerca del max-clique, offrendo tassi di successo migliorati e resilienza alle imperfezioni sperimentali come le perdite di fotoni e la compressione limitata, senza richiedere risorse esponenziali.