Quaternionic Perfect Sequences and Hadamard Matrices

Technische Samenvatting: Quaternionele Perfecte Sequenties en Hadamard-matrices

Probleemstelling
Het artikel behandelt de enumeratie en classificatie van quaternionele perfecte sequenties en hun correspondentie met quaternion-type Hadamard-matrices met circulant blokken. Een eindige sequentie is "perfect" als de periodieke autocorrelatie voor alle niet-triviale cyclische verschuivingen verdwijnt. Terwijl perfecte binaire sequenties vermoedelijk alleen voor lengte 4 bestaan, staat het uitbreiden van het alfabet naar quaternions toe langere sequenties toe. Specifiek richt de focus van de auteurs zich op sequenties over het alfabet $Q^+ = Q_8 \cup qQ_8$ (waarbij $Q_8 = \{\pm 1, \pm i, \pm j, \pm k\}$ en $q = (1+i+j+k)/2$). Deze sequenties staan in een één-op-één correspondentie met quadruples van binaire sequenties die specifieke autocorrelatie- en crosscorrelatievoorwaarden voldoen, bekend als QT-sequenties.

Een centrale uitdaging in dit domein is de computationele moeilijkheid van het exhaustief zoeken naar deze sequenties, met name wanneer de symmetriebeperkingen die vaak op de onderliggende blokmatrices worden opgelegd, worden versoepeld. Eerdere exhaustieve zoekopdrachten waren beperkt tot lengtes $n \le 13$. Bovendien was de theoretische relatie tussen QT-sequenties (die zwakkere crosscorrelatievoorwaarden voldoen) en Williamson-type sequenties (die sterkere "amicabiliteitsvoorwaarden" voldoen) voor het circulant geval nog niet volledig vastgesteld, wat de effectiviteit van filteralgoritmen beperkte.

Methodologie
De auteurs ontwikkelen een nieuw enumeratiealgoritme gebaseerd op de decompositie van de rij-sommen van de binaire sequenties. De kern van de methodologie omvat:

1. Theoretische Equivalentie: De auteurs bewijzen (Stelling 9) dat voor circulant blokmatrices de voorwaarden die QT-sequenties definiëren, equivalent zijn aan de voorwaarden die Williamson-type sequenties definiëren. Specifiek demonstreren zij dat de crosscorrelatievoorwaarden (1.2) voor circulant blokken de paarwijze amicabiliteitsvoorwaarde ($XY^\top = YX^\top$) impliceren. Deze equivalentie is cruciaal, omdat het het gebruik van sterkere filtercriteria tijdens de zoektocht mogelijk maakt.
2. Rij-som Decompositie: Het algoritme maakt gebruik van de "Rowsum Decomposition" lemma, die stelt dat voor een quadruple van QT-sequenties van lengte $n$, de som van de kwadraten van hun rij-sommen gelijk is aan $4n$. De zoekruimte wordt beperkt tot binaire sequenties waarvan de rij-sommen aan deze decompositie voldoen.
3. Paarwijze Enumeratie: In plaats van triples van sequenties te enumereren, splitst het algoritme de vier sequenties op in twee paren. Het enumereert paren $(A, B)$ en $(C, D)$ afzonderlijk, waarbij de autocorrelaties en crosscorrelaties worden berekend. Vervolgens worden paren gekoppeld waarbij de som van de autocorrelaties wegvalt en de crosscorrelatievoorwaarden worden voldaan.
4. Frequentiedomein Filtering: Om de zoektocht te optimaliseren, gebruikt het algoritme de Discrete Fourier Transformatie (DFT). Het filtert kandidaat-paren met behulp van Power Spectral Density (PSD) restricties afgeleid van de autocorrelatievoorwaarde en Cross Power Spectral Density (CPSD) restricties afgeleid van de crosscorrelatievoorwaarden. Deze filtering wordt vroegtijdig toegepast om ongeldige paren te elimineren voordat volledige correlatiecontroles plaatsvinden.
5. Equivalentie Classificatie: De auteurs definiëren drie niveaus van equivalentie: Williamson-type equivalentie, QT-equivalentie en Hadamard-equivalentie. Zij implementeren post-processing stappen om de geënumereerde resultaten te filteren tot deze equivalentieklassen, gebruikmakend van operaties zoals negatie, wisselen, decimatie en cyclische verschuivingen.

Belangrijkste Bijdragen

• Theoretische Equivalentie: Het artikel stelt vast dat voor circulant blokken QT-sequenties en Williamson-type sequenties equivalent zijn. Dit bewijst dat de ogenschijnlijk zwakkere voorwaarden voor QT-sequenties in het circulant geval feitelijk de sterkere paarwijze amicabiliteit afdwingen die vereist is voor Williamson-type matrices.
• Algoritmische Efficiëntie: Het voorgestelde algoritme is aanzienlijk sneller dan voorgaande methoden. Door gebruik te maken van de equivalentie met Williamson-type sequenties, introduceren de auteurs een filtermechanisme dat het aantal kandidaat-blokparen met een factor van meer dan 25.000 vermindert voor lengte $n=20$.
• Exhaustieve Enumeratie: De auteurs implementeren het algoritme om QT-sequenties exhaustief te enumereren voor lengtes tot $n=21$. Dit breidt de vorige exhaustieve limiet van $n=13$ uit.
• Constructie van Nieuwe Matrices: De enumeratie levert nieuwe perfecte quaternionele sequenties op, die worden gebruikt voor de constructie van nieuwe quaternionele Hadamard-matrices (QHM's). De auteurs bieden expliciete voorbeelden van deze matrices voor orden $n \le 21$.
• Analytische Karakterisering: Het artikel biedt een analytische karakterisering van orde-vijf QHMs met een specifiek invoerpatroon, waarmee bewezen wordt dat de door de nieuwe perfecte sequenties gegenereerde matrices niet equivalent zijn aan eerder bekende families (zoals die geconstrueerd door Higginbotham en Worley of Kuznetsov).

Resultaten

• Enumeratiegegevens: De auteurs vonden 124 sets van QT-sequenties tot Williamson-type equivalentie voor lengtes $n \le 21$. Hiervan zijn er 94 gerelateerd aan symmetrische Williamson-sequenties (consistent met eerdere kennis), en 30 zijn niet-symmetrisch.
• Niet-Symmetrische Sequenties: De zoektocht identificeerde niet-symmetrische QT-sequenties voor even lengtes en voor $n=9$. Echter, voor $n=21$ werden geen niet-symmetrische sequenties gevonden, wat de conjectuur van Fitzpatrick en O'Keeffe ondersteunt dat alle Williamson-type sequenties van bepaalde oneven lengtes equivalent zijn aan symmetrische sequenties.
• Oneindige Families: De auteurs bewijzen dat elke genormaliseerde QHM met ten minste één niet-reële invoer een aftelbaar oneindige familie van equivalente genormaliseerde QHMs genereert via inwendige automorfismen van de quaternions.
• Niet-Equivalentie: De studie toont aan dat QHMs geconstrueerd uit de nieuw gevonden perfecte sequenties niet equivalent zijn aan:
  • Complexe Fourier-matrices.
  • QHMs met circulant kernen die twee complexe invoerwaarden bevatten.
  • QHMs geconstrueerd uit specifieke $Q_{24}$-sequenties gevonden in eerdere literatuur (bijv. voor orden 5 en 7).
• Bestaan van Niet-Bestaan: De equivalentieresultaat impliceert dat circulant quaternionele Hadamard-matrices met invoerwaarden in $Q^+$ niet bestaan voor orden 35, 47, 53 en 59, waarmee een vraag wordt beantwoord die open bleef door eerder analytisch werk.

Betekenis
Het artikel claimt dat de resultaten wijzen op een rijker scala aan eigenschappen en een grotere overvloed aan quaternionele Hadamard-matrices dan voorheen begrepen. Door de equivalentie tussen QT- en Williamson-type sequenties voor circulant blokken vast te stellen, bieden de auteurs een krachtig instrument voor filtering en enumeratie, wat de ontdekking van nieuwe sequenties en matrices mogelijk maakt die voorheen ontoegankelijk waren.

De geconstrueerde QHMs zijn van bijzonder belang in de kwantuminformatietheorie. Ze komen overeen met Mutually Unbiased Measurements (MUM's) die geen directe sommen zijn van Mutually Unbiased Bases (MUB's), welke relevant zijn voor superdense coding en andere kwantumcommunicatieprotocollen. Het artikel suggereert dat het bestaan van meerdere niet-equivalente families van QHMs voor orden $n \ge 4$ (specifiek voor $n=5$ en $n=7$) impliceert dat het landschap van quaternionele Hadamard-matrices veel complexer en diverser is dan in de reële of complexe gevallen, waar equivalentieklassen vaak eindig of eenvoudiger zijn. Dit werk legt de basis voor verdere analytische karakterisering van QHMs met vaste invoerpatronen.