Quaternionic Perfect Sequences and Hadamard Matrices

Sintesi Tecnica: Sequenze Perfette Quaternioniche e Matrici di Hadamard

Enunciato del Problema
Il documento affronta l'enumerazione e la classificazione delle sequenze perfette quaternioniche e la loro corrispondenza con le matrici di Hadamard di tipo quaternionico con blocchi circolanti. Una sequenza finita è definita "perfetta" se la sua autocorrelazione periodica si annulla per tutti gli scorrimenti ciclici non triviali. Mentre si ipotizza che le sequenze binarie perfette esistano solo per lunghezza 4, estendere l'alfabeto ai quaternioni permette di ottenere sequenze più lunghe. Nello specifico, gli autori si concentrano su sequenze sull'alfabeto $Q^+ = Q_8 \cup qQ_8$ (dove $Q_8 = \{\pm 1, \pm i, \pm j, \pm k\}$ e $q = (1+i+j+k)/2$). Queste sequenze sono in corrispondenza biunivoca con quadrupli di sequenze binarie che soddisfano specifiche condizioni di autocorrelazione e crosscorrelazione, note come sequenze QT.

Una sfida centrale in questo dominio è la difficoltà computazionale della ricerca esaustiva di tali sequenze, in particolare quando si rilassano i vincoli di simmetria spesso imposti sulle matrici a blocchi sottostanti. Le precedenti ricerche esaustive erano limitate a lunghezze $n \le 13$. Inoltre, la relazione teorica tra le sequenze QT (che soddisfano condizioni di crosscorrelazione più deboli) e le sequenze di tipo Williamson (che soddisfano condizioni di "amicizia" più forti) non era stata pienamente stabilita per il caso circculante, limitando l'efficacia degli algoritmi di filtraggio.

Metodologia
Gli autori sviluppano un nuovo algoritmo di enumerazione basato sulla decomposizione delle somme di riga delle sequenze binarie. Il nucleo della metodologia prevede:

1. Equivalenza Teorica: Gli autori dimostrano (Teorema 9) che, per le matrici a blocchi circolanti, le condizioni che definiscono le sequenze QT sono equivalenti alle condizioni che definiscono le sequenze di tipo Williamson. Nello specifico, dimostrano che le condizioni di crosscorrelazione (1.2) per i blocchi circolanti implicano la condizione di amicizia a coppie ($XY^\top = YX^\top$). Questa equivalenza è critica poiché consente l'uso di criteri di filtraggio più forti durante la ricerca.
2. Decomposizione della Somma di Riga: L'algoritmo utilizza il lemma della "Decomposizione della Somma di Riga", il quale afferma che per un quadruplo di sequenze QT di lunghezza $n$, la somma dei quadrati delle loro somme di riga è uguale a $4n$. Lo spazio di ricerca è ristretto a sequenze binarie le cui somme di riga soddisfano questa decomposizione.
3. Enumerazione a Coppie: Invece di enumerare triadi di sequenze, l'algoritmo separa le quattro sequenze in due coppie. Enumerate separatamente le coppie $(A, B)$ e $(C, D)$, calcolandone le autocorrelazioni e le crosscorrelazioni. Successivamente, accoppia le coppie dove la somma delle autocorrelazioni si annulla e le condizioni di crosscorrelazione sono soddisfatte.
4. Filtraggio nel Dominio delle Frequenze: Per ottimizzare la ricerca, l'algoritmo impiega la Trasformata Discreta di Fourier (DFT). Filtra le coppie candidate utilizzando vincoli di Densità Spettrale di Potenza (PSD) derivati dalla condizione di autocorrelazione e vincoli di Densità Spettrale di Potenza Incrociata (CPSD) derivati dalle condizioni di crosscorrelazione. Questo filtraggio viene applicato precocemente per scartare le coppie non valide prima dei controlli completi di correlazione.
5. Classificazione di Equivalenza: Gli autori definiscono tre livelli di equivalenza: equivalenza di tipo Williamson, equivalenza QT ed equivalenza di Hadamard. Implementano passaggi di post-elaborazione per filtrare i risultati enumerati rispetto a queste classi di equivalenza, utilizzando operazioni quali negazione, scambio, decimazione e scorrimenti ciclici.

Contributi Chiave

• Equivalenza Teorica: Il documento stabilisce che, per i blocchi circolanti, le sequenze QT e le sequenze di tipo Williamson sono equivalenti. Ciò prova che le condizioni apparentemente più deboli delle sequenze QT impongono in realtà la più forte amicizia a coppia richiesta dalle matrici di tipo Williamson nel caso circculante.
• Efficienza Algoritmica: L'algoritmo proposto è significativamente più veloce dei metodi precedenti. Sfruttando l'equivalenza con le sequenze di tipo Williamson, gli autori introducono un meccanismo di filtraggio che riduce il numero di coppie di blocchi candidate di un fattore superiore a 25.000 per la lunghezza $n=20$.
• Enumerazione Esaustiva: Gli autori implementano l'algoritmo per enumerare esaustivamente le sequenze QT per lunghezze fino a $n=21$. Ciò estende il precedente limite di enumerazione esaustiva da $n=13$.
• Costruzione di Nuove Matrici: L'enumerazione produce nuove sequenze perfette quaternioniche, utilizzate per costruire nuove matrici di Hadamard quaternioniche (QHM). Gli autori forniscono esempi espliciti di queste matrici per ordini $n \le 21$.
• Caratterizzazione Analitica: Il documento fornisce una caratterizzazione analitica di matrici QHM di ordine cinque con un pattern di entrata specifico, provando che le matrici generate dalle nuove sequenze perfette non sono equivalenti alle famiglie precedentemente note (come quelle costruite da Higginbotham e Worley o Kuznetsov).

Risultati

• Dati di Enumerazione: Gli autori hanno trovato 124 insiemi di sequenze QT fino all'equivalenza di tipo Williamson per lunghezze $n \le 21$. Di questi, 94 corrispondono a sequenze di Williamson simmetriche (in linea con le conoscenze pregresse), mentre 30 sono non simmetriche.
• Sequenze Non Simmetriche: La ricerca ha identificato sequenze QT non simmetriche per lunghezze pari e per $n=9$. Tuttavia, per $n=21$, non sono state trovate sequenze non simmetriche, supportando una congettura di Fitzpatrick e O'Keeffe secondo cui tutte le sequenze di tipo Williamson di certe lunghezze dispari sono equivalenti a quelle simmetriche.
• Famiglie Infinite: Gli autori dimostrano che qualsiasi QHM normalizzata con almeno un'entrata non reale genera una famiglia uncountably infinita di QHM normalizzate equivalenti tramite automorfismi interni dei quaternioni.
• Non Equivalenza: Lo studio dimostra che le QHM costruite dalle nuove sequenze perfette non sono equivalenti a:
  • Matrici di Fourier complesse.
  • QHM con nuclei circolanti contenenti due entrate complesse.
  • QHM costruite con specifiche sequenze $Q_{24}$ trovate nella letteratura precedente (ad esempio, per ordini 5 e 7).
• Esistenza di Non Esistenza: Il risultato di equivalenza implica che le matrici di Hadamard quaternioniche circolanti con entrate in $Q^+$ non esistono per gli ordini 35, 47, 53 e 59, risolvendo una questione lasciata aperta da precedenti lavori analitici.

Significato
Il documento sostiene che i suoi risultati indicano un insieme più ricco di proprietà e una maggiore abbondanza di matrici di Hadamard quaternioniche rispetto a quanto precedentemente compreso. Stabilendo l'equivalenza tra le sequenze QT e quelle di tipo Williamson per i blocchi circolanti, gli autori forniscono uno strumento potente per il filtraggio e l'enumerazione, permettendo la scoperta di nuove sequenze e matrici precedentemente inaccessibili.

Le QHM costruite sono di particolare interesse nella teoria dell'informazione quantistica. Esse corrispondono a Misurazioni Mutuamente Non Correlate (MUM) che non sono somme dirette di Basi Mutuamente Non Correlate (MUB), le quali sono rilevanti per il superdense coding e altri protocolli di comunicazione quantistica. Il documento suggerisce che l'esistenza di molteplici famiglie non equivalenti di QHM per ordini $n \ge 4$ (specificamente per $n=5$ e $n=7$) implica che il panorama delle matrici di Hadamard quaternioniche è molto più complesso e diversificato rispetto ai casi reali o complessi, dove le classi di equivalenza sono spesso finite o più semplici. Il lavoro pone le basi per una ulteriore caratterizzazione analitica delle QHM con pattern di entrata fissi.