Quaternionic Perfect Sequences and Hadamard Matrices

Resumo Técnico: Sequências Perfeitas Quaterniônicas e Matrizes de Hadamard

Enunciado do Problema
O artigo aborda a enumeração e a classificação de sequências perfeitas quaterniônicas e sua correspondência com matrizes de Hadamard do tipo quaternio com blocos circulantes. Uma sequência finita é "perfeita" se sua autocorrelação periódica desaparece para todos os deslocamentos cíclicos não triviais. Enquanto sequências binárias perfeitas são conjecturadas para existir apenas para comprimento 4, estender o alfabeto para os quaternions permite sequências mais longas. Especificamente, os autores focam em sequências sobre o alfabeto $Q^+ = Q_8 \cup qQ_8$ (onde $Q_8 = \{\pm 1, \pm i, \pm j, \pm k\}$ e $q = (1+i+j+k)/2$). Estas sequências estão em correspondência biunívoca com quadruplas de sequências binárias que satisfazem condições específicas de autocorrelação e autocorrelação cruzada, conhecidas como sequências QT.

Um desafio central neste domínio é a dificuldade computacional de buscar exaustivamente por estas sequências, particularmente ao relaxar as restrições de simetria frequentemente impostas às matrizes de blocos subjacentes. Buscas exaustivas anteriores foram limitadas a comprimentos $n \le 13$. A relação teórica entre sequências QT (que satisfazem condições de autocorrelação cruzada mais fracas) e sequências do tipo Williamson (que satisfazem condições de "amicabilidade" mais fortes) não estava totalmente estabelecida para o caso circulante, limitando a eficácia dos algoritmos de filtragem.

Metodologia
Os autores desenvolvem um novo algoritmo de enumeração baseado na decomposição das somas das linhas das sequências binárias. O núcleo da metodologia envolve:

1. Equivalência Teórica: Os autores provam (Teorema 9) que, para matrizes de blocos circulantes, as condições que definem as sequências QT são equivalentes às condições que definem as sequências do tipo Williamson. Especificamente, eles demonstram que as condições de autocorrelação cruzada (1.2) para blocos circulantes implicam a condição de amicabilidade par a par ($XY^\top = YX^\top$). Esta equivalência é crítica, pois permite o uso de critérios de filtragem mais fortes durante a busca.
2. Decomposição da Soma da Linha: O algoritmo utiliza o lema da "Decomposição da Soma da Linha", que afirma que, para uma quadrupla de sequências QT de comprimento $n$, a soma dos quadrados de suas somas de linha é igual a $4n$. O espaço de busca é restrito a sequências binárias cujas somas de linha satisfaçam esta decomposição.
3. Enumeração Par a Par: Em vez de enumerar triplas de sequências, o algoritmo separa as quatro sequências em dois pares. Ele enumera os pares $(A, B)$ e $(C, D)$ separadamente, computando suas autocorrelações e autocorrelações cruzadas. Em seguida, combina pares onde a soma das autocorrelações se cancela e as condições de autocorrelação cruzada são satisfeitas.
4. Filtragem no Domínio da Frequência: Para otimizar a busca, o algoritmo emprega a Transformada Discreta de Fourier (DFT). Ele filtra pares candidatos usando restrições de Densidade Espectral de Potência (PSD) derivadas da condição de autocorrelação e restrições de Densidade Espectral de Potência Cruzada (CPSD) derivadas das condições de autocorrelação cruzada. Esta filtragem é aplicada precocemente para descartar pares inválidos antes das verificações completas de correlação.
5. Classificação de Equivalência: Os autores definem três níveis de equivalência: equivalência do tipo Williamson, equivalência QT e equivalência de Hadamard. Eles implementam etapas de pós-processamento para filtrar os resultados enumerados até suas classes de equivalência, utilizando operações como negação, troca, decimação e deslocamentos cíclicos.

Principais Contribuições

• Equivalência Teórica: O artigo estabelece que, para blocos circulantes, as sequências QT e as sequências do tipo Williamson são equivalentes. Isso prova que as condições aparentemente mais fracas para sequências QT na verdade impõem a amicabilidade par a par mais forte exigida por matrizes do tipo Williamson no caso circulante.
• Eficiência Algorítmica: O algoritmo proposto é significativamente mais rápido que métodos anteriores. Ao alavancar a equivalência com sequências do tipo Williamson, os autores introduzem um mecanismo de filtragem que reduz o número de pares de blocos candidatos por um fator de mais de 25.000 para o comprimento $n=20$.
• Enumeração Exaustiva: Os autores implementam o algoritmo para enumerar exaustivamente sequências QT para comprimentos até $n=21$. Isso estende o limite de enumeração exaustiva anterior para $n=13$.
• Construção de Novas Matrizes: A enumeração produz novas sequências perfeitas quaterniônicas, que são usadas para construir novas matrizes de Hadamard quaterniônicas (QHMs). Os autores fornecem exemplos explícitos destas matrizes para ordens $n \le 21$.
• Caracterização Analítica: O artigo fornece uma caracterização analítica de QHMs de ordem cinco com um padrão de entrada específico, provando que as matrizes geradas pelas novas sequências perfeitas não são equivalentes a famílias conhecidas anteriormente (como aquelas construídas por Higginbotham e Worley ou Kuznetsov).

Resultados

• Dados de Enumeração: Os autores encontraram 124 conjuntos de sequências QT até a equivalência do tipo Williamson para comprimentos $n \le 21$. Destes, 94 correspondem a sequências de Williamson simétricas (consistente com o conhecimento prévio), enquanto 30 são não-simétricas.
• Sequências Não-Simétricas: A busca identificou sequências QT não-simétricas para comprimentos pares e para $n=9$. No entanto, para $n=21$, nenhuma sequência não-simétrica foi encontrada, apoiando uma conjectura de Fitzpatrick e O'Keeffe de que todas as sequências do tipo Williamson de certos comprimentos ímpares são equivalentes às simétricas.
• Famílias Infinitas: Os autores provam que qualquer QHM normalizada com pelo menos uma entrada não-real gera uma família unicamente infinita de QHMs normalizadas equivalentes via automorfismos internos dos quaternions.
• Não-Equivalência: O estudo demonstra que as QHMs construídas a partir das novas sequências perfeitas não são equivalentes a:
  • Matrizes de Fourier complexas.
  • QHMs com núcleos circulantes contendo duas entradas complexas.
  • QHMs construídas a partir de sequências $Q_{24}$ específicas encontradas na literatura anterior (ex: para ordens 5 e 7).
• Existência de Não-Existência: O resultado de equivalência implica que matrizes de Hadamard quaterniônicas circulantes com entradas em $Q^+$ não existem para as ordens 35, 47, 53 e 59, resolvendo uma questão deixada aberta por trabalhos analíticos anteriores.

Significância
O artigo afirma que seus resultados indicam um conjunto mais rico de propriedades e uma maior abundância de matrizes de Hadamard quaterniônicas do que o anteriormente compreendido. Ao estabelecer a equivalência entre sequências QT e do tipo Williamson para blocos circulantes, os autores fornecem uma ferramenta poderosa para filtragem e enumeração, permitindo a descoberta de novas sequências e matrizes que eram anteriormente inacessíveis.

As QHMs construídas são de particular interesse na teoria da informação quântica. Elas correspondem a Medições Mutuamente Não-Viesadas (MUMs) que não são somas diretas de Bases Mutuamente Não-Viesadas (MUBs), que são relevantes para codificação superdensa e outros protocolos de comunicação quântica. O artigo sugere que a existência de múltiplas famílias não-equivalentes de QHMs para ordens $n \ge 4$ (especificamente para $n=5$ e $n=7$) implica que o cenário das matrizes de Hadamard quaterniônicas é muito mais complexo e diverso do que nos casos real ou complexo, onde as classes de equivalência são frequentemente finitas ou mais simples. O trabalho lança as bases para uma caracterização analítica adicional de QHMs com padrões de entrada fixos.