Stratified Sampling for Quasi-Probability Decompositions

1. Il Problema

Le Decomposizioni Quasi-Probabilistiche (QPD) sono fondamentali in molti algoritmi e protocolli quantistici (come la cancellazione probabilistica degli errori - PEC, e l'interpolazione probabilistica degli angoli - PAI). Il principio di base consiste nel sostituire un circuito quantistico "difficile" (o rumoroso) con un insieme di varianti di circuiti "più facili", i cui risultati ponderati riproducono l'osservabile target.

Tuttavia, questo approccio introduce una fonte di varianza aggiuntiva oltre al rumore intrinseco di Born (shot noise): la varianza di configurazione. Poiché si campiona casualmente tra diverse varianti di circuiti, la varianza totale dell'estimatore aumenta, richiedendo un numero esponenziale di esecuzioni (shot) per raggiungere una precisione target. Anche se il fattore esponenziale principale (legato alla norma-1 della QPD, $\|g\|_1$) è spesso inevitabile, i prefattori costanti nella varianza possono limitare drasticamente l'utilità pratica dei metodi QPD, specialmente nell'era NISQ e nei primi computer fault-tolerant.

L'obiettivo del lavoro è ridurre questa varianza di configurazione senza richiedere risorse quantistiche aggiuntive, intervenendo esclusivamente sulla strategia di campionamento classico.

2. Metodologia

Gli autori adottano una prospettiva di design del campionamento, importando strumenti dalla statistica classica per ridurre la varianza. Il loro approccio si basa sui seguenti pilastri:

• Decomposizione della Varianza: Utilizzano la legge della varianza totale per separare la varianza dell'estimatore in due componenti:

  1. Rumore di Born: Intrinseco al processo di misura quantistica (sopprimibile aumentando i ripetizioni $R$ per configurazione).
  2. Varianza di Configurazione: Derivante dalla randomizzazione classica sulle varianti del circuito.
     L'obiettivo è ridurre la seconda componente mantenendo l'estimatore invariato.

• Campionamento Stratificato (Stratified Sampling): Invece di campionare le configurazioni del circuito in modo indipendente e identico distribuito (i.i.d.) dalla distribuzione originale (campionamento "naif"), gli autori propongono di:

  1. Partizionare lo spazio delle configurazioni in strati (strata) basati su una statistica deterministica $S(\ell)$.
  2. Allocare un budget fisso di campioni a ciascuno strato.
  3. Combinare i risultati ponderati per ottenere l'estimatore finale.

• Statistica di Stratificazione: Il Vettore di Conteggio (Counts-Vector):
  Per le QPD a forma di prodotto, gli autori introducono una statistica specifica: il vettore di conteggio. Questo vettore conta quante volte ciascun "primitivo locale" (es. un certo canale di rumore o un angolo di rotazione) appare nella configurazione, ignorando l'ordine delle porte.

  • Esempio: In una QPD con 3 tipi di primitive su $\nu$ gate, una configurazione è definita da un vettore $(M_1, M_2, M_3)$ tale che $\sum M_i = \nu$.
  • Questo riduce lo spazio delle configurazioni da esponenziale ($O(d^\nu)$) a polinomiale ($O(\nu^{d-1})$), rendendo la stratificazione computazionalmente fattibile.

• Algoritmo Dinamico (Dynamic Programming - DP):
  Per rendere il metodo operativo, gli autori sviluppano un algoritmo DP classico che:

  1. Calcola esattamente i pesi degli strati (le probabilità marginali dei vettori di conteggio) in tempo $O(d \nu^d)$.
  2. Permette il campionamento condizionale esatto: dato un vettore di conteggio target, genera una configurazione specifica $\ell$ che rispetta quel conteggio, mantenendo la distribuzione corretta.
     Questo pre-processing classico non richiede risorse quantistiche aggiuntive.

• Allocazione Proporzionale:
  Viene utilizzata un'allocazione proporzionale (il numero di campioni in uno strato è proporzionale al suo peso). Gli autori dimostrano che, sotto questa allocazione ideale, il metodo è invariato (unbiased) e la varianza risultante è mai peggiore del campionamento naif, con un miglioramento rigoroso a meno di casi degeneri.

3. Contributi Chiave

1. Teorema di "Mai Peggio" (Never-Worse Guarantee): Dimostrazione matematica che il campionamento stratificato con allocazione proporzionale riduce la varianza rispetto al campionamento naif per qualsiasi QPD a forma di prodotto, eliminando la componente di varianza "tra gli strati" (between-stratum variance).
2. Costruzione Universale: Sviluppo di un metodo di stratificazione basato sul vettore di conteggio che è universale per QPD a forma di prodotto, indipendentemente dalla specifica fisica del problema (agostico rispetto al problema quantistico).
3. Algoritmo Efficiente: Implementazione di un pre-processing classico basato su DP per calcolare i pesi degli strati e generare campioni condizionati, con complessità polinomiale per larghezza locale fissa.
4. Gestione dell'Intero: Proposta di una procedura "residual-aware" (consapevole dei residui) per gestire l'allocazione intera dei campioni (poiché i pesi ideali non sono interi), garantendo l'invarianza esatta anche con budget finiti.

4. Risultati Numerici

Gli autori hanno testato il metodo su circuiti di evoluzione temporale del modello di Ising trasverso (TFIM) utilizzando due schemi QPD tipici:

• Probabilistic Angle Interpolation (PAI): Per l'interpolazione di angoli di rotazione.
• Probabilistic Error Cancellation (PEC): Per la cancellazione del rumore di depolarizzazione.

Risultati principali:

• Regime Oracle (Shot noise soppresso): In scenari dove il rumore di misura è trascurabile (o $R \to \infty$), la stratificazione ha portato a riduzioni della varianza complessiva fino al 60-80%. Questo indica che una grande frazione della varianza è spiegata dalla struttura dei conteggi.
• Regime Single-Shot (Dominio del rumore di Born): In scenari realistici con pochi shot per configurazione ($R=1$), si è osservata una riduzione robusta della varianza di circa il 10%.
• Risparmio di Risorse: Una riduzione della varianza si traduce direttamente in un risparmio costante nel numero totale di esecuzioni del circuito necessarie per raggiungere una data precisione.
• Scalabilità: Il metodo è stato validato per profondità di circuito fino a $\nu \approx 100$ e larghezze locali $d=3$ (PAI) e $d=4$ (PEC), rimanendo fattibile su workstation standard.

5. Significato e Implicazioni

Questo lavoro rappresenta un passo significativo per l'ottimizzazione degli algoritmi quantistici near-term e fault-tolerant:

• Efficienza Immediata: Il metodo può essere applicato immediatamente a qualsiasi protocollo QPD esistente senza modificare il circuito quantistico o richiedere hardware aggiuntivo. Richiede solo un pre-processing classico e un cambiamento nella logica di campionamento.
• Estensione della Finestra di Utilità: Riducendo i prefattori costanti nella varianza, il metodo estende il regime in cui i metodi QPD sono praticamente utili, permettendo di gestire circuiti più profondi o livelli di rumore più elevati con lo stesso budget di shot.
• Separazione Concettuale: Il lavoro chiarisce la distinzione tra la progettazione della QPD (che mira a minimizzare la norma-1 $\|g\|_1$) e il design del campionamento (che mira a minimizzare la varianza di configurazione). Questi due aspetti sono complementari.
• Generalità: Sebbene focalizzato sulle QPD, il framework di decomposizione della varianza e stratificazione è applicabile a una vasta gamma di protocolli di randomizzazione quantistica, come il randomized compiling, le classical shadows e la simulazione di Hamiltonian randomizzata.

In sintesi, gli autori dimostrano che una gestione intelligente della randomizzazione classica, attraverso la stratificazione basata su statistiche di conteggio, può fornire risparmi sostanziali e provati nelle risorse di campionamento, rendendo le tecniche di mitigazione degli errori e di simulazione quantistica più efficienti e scalabili.