Quaternionic Perfect Sequences and Hadamard Matrices

Technical Summary: Quaternionic Perfect Sequences and Hadamard Matrices

Problem Statement
The paper addresses the enumeration and classification of quaternionic perfect sequences and their correspondence to quaternion-type Hadamard matrices with circulant blocks. A finite sequence is "perfect" if its periodic autocorrelation vanishes for all non-trivial cyclic shifts. While perfect binary sequences are conjectured to exist only for length 4, extending the alphabet to quaternions allows for longer sequences. Specifically, the authors focus on sequences over the alphabet $Q^+ = Q_8 \cup qQ_8$ (where $Q_8 = \{\pm 1, \pm i, \pm j, \pm k\}$ and $q = (1+i+j+k)/2$). These sequences are in one-to-one correspondence with quadruples of binary sequences satisfying specific autocorrelation and crosscorrelation conditions, known as QT sequences.

A central challenge in this domain is the computational difficulty of exhaustively searching for these sequences, particularly when relaxing the symmetry constraints often imposed on the underlying block matrices. Previous exhaustive searches were limited to lengths $n \le 13$. Furthermore, the theoretical relationship between QT sequences (which satisfy weaker crosscorrelation conditions) and Williamson-type sequences (which satisfy stronger "amicability" conditions) was not fully established for the circulant case, limiting the effectiveness of filtering algorithms.

Methodology
The authors develop a novel enumeration algorithm based on the decomposition of the rowsums of the binary sequences. The core of the methodology involves:

1. Theoretical Equivalence: The authors prove (Theorem 9) that for circulant block matrices, the conditions defining QT sequences are equivalent to the conditions defining Williamson-type sequences. Specifically, they demonstrate that the crosscorrelation conditions (1.2) for circulant blocks imply the pairwise amicability condition ($XY^\top = YX^\top$). This equivalence is critical as it allows the use of stronger filtering criteria during the search.
2. Rowsum Decomposition: The algorithm utilizes the "Rowsum Decomposition" lemma, which states that for a quadruple of QT sequences of length $n$, the sum of the squares of their rowsums equals $4n$. The search space is restricted to binary sequences whose rowsums satisfy this decomposition.
3. Pairwise Enumeration: Instead of enumerating triples of sequences, the algorithm separates the four sequences into two pairs. It enumerates pairs $(A, B)$ and $(C, D)$ separately, computing their autocorrelations and crosscorrelations. It then matches pairs where the sum of autocorrelations cancels out and the crosscorrelation conditions are satisfied.
4. Frequency Domain Filtering: To optimize the search, the algorithm employs the Discrete Fourier Transform (DFT). It filters candidate pairs using Power Spectral Density (PSD) constraints derived from the autocorrelation condition and Cross Power Spectral Density (CPSD) constraints derived from the crosscorrelation conditions. This filtering is applied early to discard invalid pairs before full correlation checks.
5. Equivalence Classification: The authors define three levels of equivalence: Williamson-type equivalence, QT equivalence, and Hadamard equivalence. They implement post-processing steps to filter the enumerated results up to these equivalence classes, utilizing operations such as negation, swapping, decimation, and cyclic shifts.

Key Contributions

• Theoretical Equivalence: The paper establishes that for circulant blocks, QT sequences and Williamson-type sequences are equivalent. This proves that the seemingly weaker conditions for QT sequences actually enforce the stronger pairwise amicability required for Williamson-type matrices in the circulant case.
• Algorithmic Efficiency: The proposed algorithm is significantly faster than previous methods. By leveraging the equivalence to Williamson-type sequences, the authors introduce a filtering mechanism that reduces the number of candidate block pairs by a factor of over 25,000 for length $n=20$.
• Exhaustive Enumeration: The authors implement the algorithm to exhaustively enumerate QT sequences for lengths up to $n=21$. This extends the previous exhaustive limit of $n=13$.
• Construction of New Matrices: The enumeration yields new perfect quaternionic sequences, which are used to construct new quaternionic Hadamard matrices (QHMs). The authors provide explicit examples of these matrices for orders $n \le 21$.
• Analytical Characterization: The paper provides an analytical characterization of order-five QHMs with a specific entry pattern, proving that the matrices generated by the new perfect sequences are not equivalent to previously known families (such as those constructed by Higginbotham and Worley or Kuznetsov).

Results

• Enumeration Data: The authors found 124 sets of QT sequences up to Williamson-type equivalence for lengths $n \le 21$. Of these, 94 correspond to symmetric Williamson sequences (consistent with prior knowledge), while 30 are non-symmetric.
• Non-Symmetric Sequences: The search identified non-symmetric QT sequences for even lengths and for $n=9$. However, for $n=21$, no non-symmetric sequences were found, supporting a conjecture by Fitzpatrick and O'Keeffe that all Williamson-type sequences of certain odd lengths are equivalent to symmetric ones.
• Infinite Families: The authors prove that any normalized QHM with at least one non-real entry generates an uncountably infinite family of equivalent normalized QHMs via inner automorphisms of the quaternions.
• Nonequivalence: The study demonstrates that QHMs constructed from the newly found perfect sequences are not equivalent to:
  • Complex Fourier matrices.
  • QHMs with circulant cores containing two complex entries.
  • QHMs constructed from specific $Q_{24}$-sequences found in prior literature (e.g., for orders 5 and 7).
• Existence of Non-Existence: The equivalence result implies that circulant quaternionic Hadamard matrices with entries in $Q^+$ do not exist for orders 35, 47, 53, and 59, resolving a question left open by previous analytical work.

Significance
The paper claims that its results indicate a richer set of properties and a greater abundance of quaternionic Hadamard matrices than previously understood. By establishing the equivalence between QT and Williamson-type sequences for circulant blocks, the authors provide a powerful tool for filtering and enumeration, enabling the discovery of new sequences and matrices that were previously inaccessible.

The constructed QHMs are of particular interest in quantum information theory. They correspond to Mutually Unbiased Measurements (MUMs) that are not direct sums of Mutually Unbiased Bases (MUBs), which are relevant for superdense coding and other quantum communication protocols. The paper suggests that the existence of multiple nonequivalent families of QHMs for orders $n \ge 4$ (specifically for $n=5$ and $n=7$) implies that the landscape of quaternionic Hadamard matrices is far more complex and diverse than in the real or complex cases, where equivalence classes are often finite or simpler. The work lays the groundwork for further analytical characterization of QHMs with fixed entry patterns.