Probabilistic Links Between Quantum Classification of Patterns of Boolean Functions and Hamming Distance

Sintesi Tecnica: Collegamenti Probabilistici tra la Classificazione Quantistica di Pattern di Funzioni Booleane e la Distanza di Hamming

Enunciato del Problema
Gli algoritmi di classificazione quantistica, come l'algoritmo di Deutsch-Jozsa e le sue estensioni, sono progettati per classificare perfettamente funzioni booleane che soddisfano specifiche "promesse" (ad esempio, essere costanti o bilanciate) con una probabilità di 1.0. Tuttavia, esiste un divario significativo nella comprensione del comportamento di questi algoritmi quando vengono presentati con funzioni sconosciute che cadono al di fuori della classe promessa. Mentre la letteratura precedente si è concentrata sulla distinzione di classi specifiche o sull'uso di metriche di distanza alternative (come le distanze basate su cluster), manca un'analisi rigorosa riguardante il comportamento dei classificatori quantistici quando la funzione di input è semplicemente "vicina" alla classe target. Questo articolo affronta la sfida di determinare se sia possibile estrarre informazioni utili su una funzione booleana $h$ sconosciuta e non classificabile, identificando i suoi "vicini più prossimi" all'interno di una classe perfettamente classificabile $F_{P_n}$, utilizzando la distanza di Hamming come metrica di prossimità.

Metodologia
Gli autori impiegano un framework che combina l'informatica quantistica, la teoria dell'informazione e la combinatoria, concettualizzato attraverso un strategico "Gioco del Ket del Vicino Prossimo" (Nearest Basis Ket Game) tra due giocatori, Alice e Bob.

1. Framework Teorico:

   • Vettori di Bit di Pattern: Le funzioni booleane sono mappate in vettori di bit di pattern unici di lunghezza $2^n$, stabilendo una biiezione tra funzioni e vettori.
   • Basi di Pattern e Classi: Lo studio utilizza "basi di pattern" ($P_n$), insiemi di vettori di pattern ortogonali, che definiscono classi di funzioni booleane perfettamente classificabili ($F_{P_n}$).
   • Costruzione del Classificatore: I classificatori quantistici ($G$) sono costruiti come prodotti tensoriali di classificatori elementari: la trasformata di Hadamard ($H$) e un classificatore specifico ($C_2$) derivato dal rapporto di squilibrio di basi $Q_2$.
   • Metrica di Distanza: La distanza di Hamming ($d_H$) è definita tra i vettori di bit di pattern della funzione sconosciuta $h$ e le funzioni nella classe $F_{P_n}$. I "vicini più prossimi" sono quelle funzioni nella classe con la minima distanza di Hamming da $h$.

2. Approccio Sperimentale:

   • Simulazione: Sono stati condotti estesi esperimenti utilizzando Qiskit per simulare circuiti quantistici che implementano lo schema di classificazione della Base di Pattern.
   • Ambito:
     • Enumerazione Esaustiva: Per scale più piccole (vettori di pattern di lunghezza 8 e 16), tutte le possibili funzioni booleane sono state enumerate per garantire la certezza statistica.
     • Campionamento Casuale: Per scale più grandi (lunghezze 32 e 64), dove l'enumerazione esaustiva è computazionalmente proibitiva, è stata impiegata una strategia di campionamento casuale statisticamente robusta.
   • Metrica: La metrica principale analizzata è la "soglia di classificazione" ($\vartheta$), definita come la probabilità che l'esito della misurazione della funzione sconosciuta $h$ corrisponda a uno dei suoi ket di base più vicini nella classe.

Risultati Chiave
I risultati sperimentali rivelano una relazione forte, seppur sfumata, tra la distanza di Hamming e la probabilità di classificazione:

1. Decrescita Monotona: Per la stragrande maggioranza delle classi di funzioni, la soglia di classificazione è una funzione decrescente monotona della distanza di Hamming. Man mano che la funzione sconosciuta $h$ devia ulteriormente dalla classe $F_{P_n}$, la probabilità di identificare correttamente un vicino più prossimo scende.
2. Tre Intervalli Distinti: Gli autori stabiliscono intervalli precisi per la distanza di Hamming che delimitano la probabilità di classificazione:
   • Intervallo di Alta Confidenza ($1$a$2^n/8$): La soglia di classificazione rimane strettamente sopra lo 0.50, consentendo di affermare con fiducia che la misurazione probabilmente corrisponde a un vicino più prossimo.
   • Intervallo di Transizione ($2^n/8 + 1$ a $2^n/2 - 1$): La soglia rimane positiva ma diminuisce costantemente verso lo 0.00.
   • Intervallo di Bassa Confidenza ($2^n/2$ a $2^n$): La soglia è effettivamente 0.00, indicando che la funzione non è un vicino più prossimo.
3. Eccezioni Sistemiche (Eterogeneità Intra-classe): Una deviazione significativa dalla tendenza monotona è stata osservata nelle classi formate dal prodotto esteso della base $Q_2$ ($F_{Q_2}^{\otimes m}$). In queste classi specifiche, la probabilità di classificazione ha un picco esattamente a 1.0 in una specifica distanza di Hamming ($\varrho$), invece di rimanere a 0.00. Questa anomalia non è casuale ma è una conseguenza prevedibile del rapporto fisso di 0 e 1 inerente a queste specifiche classi di funzioni.

Significatività e Contributi
L'articolo rivendica diversi contributi innovativi nel campo dell'apprendimento automatico quantistico e della classificazione:

• Validazione della Distanza di Hamming: Il lavoro valida robustamente la distanza di Hamming come metrica critica ed efficace per verificare o escludere i candidati vicini più prossimi nel processo di classificazione quantistica, anche quando l'input è al di fuori della classe promessa.
• Quantificazione delle Irregolarità: Lo studio dimostra che le deviazioni dalla tendenza monotona attesa non sono artefatti statistici ma sono sistemiche e prevedibili. Nello specifico, gli autori quantificano lo "spike" di probabilità per le classi $F_{Q_2}^{\otimes m}$, trasformando una potenziale fonte di errore in un fenomeno gestibile e ben compreso.
• Confini Probabilistici: Per quanto ne sappiano gli autori, questo è il primo lavoro che demarca intervalli precisi di distanza di Hamming che delimitano i possibili valori della probabilità di classificazione.
• Framework Pratico per il Processo Decisionale: Le conclusioni forniscono ai professionisti uno strumento fondamentale per la valutazione probabilistica. Gli utenti possono ora:
  1. Approvare i risultati della classificazione con alta certezza quando la distanza di Hamming rientra nell'intervallo di alta confidenza.
  2. Scartare i risultati con fiducia quando la distanza rientra nell'intervallo di bassa confidenza.
• Intuizione Teoria-del-Gioco: Il "Gioco del Ket del Vicino Prossimo" funge da framework concettuale per illustrare questi confini probabilistici, mostrando come l'interazione tra distanza e probabilità crei vantaggi strategici sia per "Alice" (il classificatore) che per "Bob" (il selettore della funzione), evidenziando in particolare la correttezza del gioco quando Bob seleziona funzioni alla soglia critica di distanza ($2^n/8$).

In sintesi, l'articolo stabilisce che, sebbene i classificatori quantistici siano progettati per input specifici "promessi", il loro comportamento su input non classificabili non è rumore casuale, ma segue una struttura probabilistica prevedibile governata dalla distanza di Hamming, con eccezioni specifiche e quantificabili per determinate classi strutturate.