Quaternionic Perfect Sequences and Hadamard Matrices

Resumen Técnico: Secuencias Perfectas Cuaterniónicas y Matrices de Hadamard

Planteamiento del Problema
El artículo aborda la enumeración y clasificación de las secuencias perfectas cuaterniónicas y su correspondencia con las matrices de Hadamard de tipo cuaterniónico con bloques circulantes. Una secuencia finita es "perfecta" si su autocorrelación periódica se anula para todos los desplazamientos cíclicos no triviales. Mientras que se conjetura que las secuencias binarias perfectas existen solo para la longitud 4, la extensión del alfabeto a los cuaterniones permite secuencias más largas. Específicamente, los autores se centran en secuencias sobre el alfabeto $Q^+ = Q_8 \cup qQ_8$ (donde $Q_8 = \{\pm 1, \pm i, \pm j, \pm k\}$ y $q = (1+i+j+k)/2$). Estas secuencias están en correspondencia biunívoca con cuadruples de secuencias binarias que satisfacen condiciones específicas de autocorrelación y correlación cruzada, conocidas como secuencias QT.

Un desafío central en este dominio es la dificultad computacional de buscar exhaustivamente estas secuencias, particularmente al relajar las restricciones de simetría que suelen imponerse a las matrices de bloques subyacentes. Las búsquedas exhaustivas previas se limitaron a longitudes $n \le 13$. Además, la relación teórica entre las secuencias QT (que satisfacen condiciones de correlación cruzada más débiles) y las secuencias de tipo Williamson (que satisfacen condiciones de "amicabilidad" más fuertes) no se había establecido completamente para el caso circulante, lo que limitaba la efectividad de los algoritmos de filtrado.

Metodología
Los autores desarrollan un nuevo algoritmo de enumeración basado en la descomposición de las sumas de filas de las secuencias binarias. El núcleo de la metodología consiste en:

1. Equivalencia Teórica: Los autores demuestran (Teorema 9) que, para matrices de bloques circulantes, las condiciones que definen a las secuencias QT son equivalentes a las condiciones que definen a las secuencias de tipo Williamson. Específicamente, demuestran que las condiciones de correlación cruzada (1.2) para bloques circulantes implican la condición de amicabilidad por pares ($XY^\top = YX^\top$). Esta equivalencia es crítica, ya que permite el uso de criterios de filtrado más fuertes durante la búsqueda.
2. Descomposición de Sumas de Filas: El algoritmo utiliza el lema de "Descomposición de Sumas de Filas", el cual establece que para un cuadruple de secuencias QT de longitud $n$, la suma de los cuadrados de sus sumas de filas es igual a $4n$. El espacio de búsqueda se restringe a secuencias binarias cuyas sumas de filas satisfagan esta descomposición.
3. Enumeración por Pares: En lugar de enumerar triples de secuencias, el algoritmo separa las cuatro secuencias en dos pares. Enumera los pares $(A, B)$ y $(C, D)$ por separado, computando sus autocorrelaciones y correlaciones cruzadas. Luego, empareja los pares donde la suma de las autocorrelaciones se cancela y se cumplen las condiciones de correlación cruzada.
4. Filtrado en el Dominio de la Frecuencia: Para optimizar la búsqueda, el algoritmo emplea la Transformada Discreta de Fourier (DFT). Filtra los pares candidatos utilizando restricciones de Densidad Espectral de Potencia (PSD) derivadas de la condición de autocorrelación y restricciones de Densidad Espectral de Potencia Cruzada (CPSD) derivadas de las condiciones de correlación cruzada. Este filtrado se aplica tempranamente para descartar pares inválidos antes de realizar los chequeos completos de correlación.
5. Clasificación de Equivalencia: Los autores definen tres niveles de equivalencia: equivalencia de tipo Williamson, equivalencia QT y equivalencia de Hadamard. Implementan pasos de post-procesamiento para filtrar los resultados enumerados hasta sus clases de equivalencia, utilizando operaciones como negación, intercambio, decimación y desplazamientos cíclicos.

Contribuciones Clave

• Equivalencia Teórica: El artículo establece que, para bloques circulantes, las secuencias QT y las secuencias de tipo Williamson son equivalentes. Esto demuestra que las condiciones aparentemente más débiles de las secuencias QT en realidad imponen la condición de amicabilidad por pares requerida para las matrices de tipo Williamson en el caso circulante.
• Eficiencia Algorítmica: El algoritmo propuesto es significativamente más rápido que los métodos anteriores. Al aprovechar la equivalencia con las secuencias de tipo Williamson, los autores introducen un mecanismo de filtrado que reduce el número de pares de bloques candidatos por un factor de más de 25,000 para la longitud $n=20$.
• Enumeración Exhaustiva: Los autores implementan el algoritmo para enumerar exhaustivamente las secuencias QT para longitudes hasta $n=21$. Esto extiende el límite de enumeración exhaustiva previo de $n=13$.
• Construcción de Nuevas Matrices: La enumeración produce nuevas secuencias perfectas cuaterniónicas, que se utilizan para construir nuevas matrices de Hadamard cuaterniónicas (QHMs). Los autores proporcionan ejemplos explícitos de estas matrices para órdenes $n \le 21$.
• Caracterización Analítica: El artículo proporciona una caracterización analítica de las QHMs de orden cinco con un patrón de entrada específico, demostrando que las matrices generadas por las nuevas secuencias perfectas no son equivalentes a familias previamente conocidas (como las construidas por Higginbotham y Worley o Kuznetsov).

Resultados

• Datos de Enumeración: Los autores encontraron 124 conjuntos de secuencias QT hasta la equivalencia de tipo Williamson para longitudes $n \le 21$. De estos, 94 corresponden a secuencias de Williamson simétricas (consistente con el conocimiento previo), mientras que 30 son no simétricas.
• Secuencias No Simétricas: La búsqueda identificó secuencias QT no simétricas para longitudes pares y para $n=9$. Sin embargo, para $n=21$, no se encontraron secuencias no simétricas, lo que respalda una conjetura de Fitzpatrick y O'Keeffe de que todas las secuencias de tipo Williamson de ciertas longitudes impares son equivalentes a las simétricas.
• Familias Infinitas: Los autores demuestran que cualquier QHM normalizada con al menos una entrada no real genera una familia incontablemente infinita de QHMs normalizadas equivalentes mediante automorfismos internos de los cuaterniones.
• No Equivalencia: El estudio demuestra que las QHMs construidas a partir de las nuevas secuencias perfectas no son equivalentes a:
  • Matrices de Fourier complejas.
  • QHMs con núcleos circulantes que contienen dos entradas complejas.
  • QHMs construidas a partir de secuencias $Q_{24}$ específicas encontradas en la literatura previa (por ejemplo, para órdenes 5 y 7).
• Existencia de la No Existencia: El resultado de equivalencia implica que las matrices de Hadamard cuaterniónicas circulantes con entradas en $Q^+$ no existen para los órdenes 35, 47, 53 y 59, resolviendo una cuestión dejada abierta por trabajos analíticos previos.

Significado
El artículo afirma que sus resultados indican un conjunto de propiedades más rico y una mayor abundancia de matrices de Hadamard cuaterniónicas de lo que se entendía anteriormente. Al establecer la equivalencia entre las secuencias QT y las de tipo Williamson para bloques circulantes, los autores proporcionan una herramienta poderosa para el filtrado y la enumeración, permitiendo el descubrimiento de nuevas secuencias y matrices que antes eran inaccesibles.

Las QHMs construidas son de especial interés en la teoría de la información cuántica. Corresponden a Mediciones Mutuamente No Sesgadas (MUMs) que no son sumas directas de Bases Mutuamente No Sesgadas (MUBs), las cuales son relevantes para la codificación superdensa y otros protocolos de comunicación cuántica. El artículo sugiere que la existencia de múltiples familias no equivalentes de QHMs para órdenes $n \ge 4$ (específicamente para $n=5$ y $n=7$) implica que el panorama de las matrices de Hadamard cuaterniónicas es mucho más complejo y diverso que en los casos real o complejo, donde las clases de equivalencia suelen ser finitas o más simples. El trabajo sienta las bases para una mayor caracterización analítica de las QHMs con patrones de entrada fijos.