Quaternionic Perfect Sequences and Hadamard Matrices

技术摘要：四元数完美序列与 Hadamard 矩阵

问题陈述
本文研究了四元数完美序列的枚举与分类，及其与具有循环块的四元数型 Hadamard 矩阵之间的对应关系。一个有限序列被称为“完美”的，是指其周期自相关在所有非平凡循环移位下均为零。虽然存在关于完美二元序列仅存在于长度 4 的猜想，但通过将字母表扩展到四元数，可以获得更长的序列。具体而言，作者关注的是字母表为 $Q^+ = Q_8 \cup qQ_8$（其中 $Q_8 = \{\pm 1, \pm i, \pm j, \pm k\}$ 且 $q = (1+i+j+k)/2$）的序列。这些序列与满足特定自相关和互相关条件的四元组二元序列（称为 QT 序列）具有一一对应关系。

该领域的一个核心挑战是寻找这些序列时的计算难度，特别是在放宽通常施加于底层块矩阵的对称性约束时。之前的穷举搜索被限制在长度 $n \le 13$。此外，QT 序列（满足较弱互相关条件）与 Williamson 型序列（满足较强“亲和性”条件）之间的理论关系在循环情形下尚未完全建立，这限制了过滤算法的有效性。

方法论
作者开发了一种基于二元序列行和分解的新型枚举算法。其核心方法论包括：

1. 理论等价性： 作者证明（定理 9）对于循环块，定义 QT 序列的条件与定义 Williamson 型序列的条件是等价的。具体而言，他们证明了循环块的互相关条件 (1.2) 蕴含了成对亲和性条件 ($XY^\top = YX^\top$)。这种等价性至关重要，因为它允许在搜索过程中使用更强的过滤准则。
2. 行和分解： 该算法利用“行和分解”引理，即对于长度为 $n$ 的四个 QT 序列，其行和平方之和等于 $4n$。搜索空间被限制在行和满足此分解关系的二元序列中。
3. 成对枚举： 算法并非枚举三元组序列，而是将四个序列分为两对进行处理。它分别枚举序列对 $(A, B)$ 和 $(C, D)$，计算它们的自相关和互相关，然后匹配使自相关之和抵消且满足互相关条件的序列对。
4. 频域过滤： 为了优化搜索，算法采用了离散傅里叶变换 (DFT)。它利用由自相关条件导出的功率谱密度 (PSD) 约束以及由互相关条件导出的互功率谱密度 (CPSD) 约束来过滤候选对。这种过滤在进行完整的相关性检查之前就被应用，以剔除无效的序列对。
5. 等价分类： 作者定义了三个层级的等价关系：Williamson 型等价、QT 等价和 Hadamard 等价。他们实现了后处理步骤，以在这些等价类下过滤枚举结果，利用包括取反、交换、抽取（decimation）和循环移位在内的操作。

主要贡献

• 理论等价性： 本文确立了对于循环块，QT 序列与 Williamson 型序列是等价的。这证明了对于循环情形，看似较弱的 QT 序列条件实际上强制执行了 Williamson 型矩阵所要求的更强的成对亲和性。
• 算法效率： 所提出的算法比以往的方法显著更快。通过利用向 Williamson 型序列的等价性，作者引入了一种过滤机制，对于长度 $n=20$，该机制将候选块对的数量减少了 25,000 倍以上。
• 穷举枚举： 作者实现了该算法，对长度高达 $n=21$ 的 QT 序列进行了穷举枚举。这扩展了之前 $n=13$ 的穷举极限。
• 构建新矩阵： 枚举过程产生了新的完美四元数序列，并用于构造新的四元数 Hadamard 矩阵 (QHM)。作者提供了这些矩阵在阶数 $n \le 21$ 时的显式示例。
• 解析特征化： 本文对具有特定条目模式的五阶 QHM 进行了解析特征化，证明了由新发现的完美序列生成的矩阵与先前已知的家族（如 Higginbotham 和 Worley 或 Kuznetsov 构建的矩阵）并不等价。

结果

• 枚举数据： 作者在长度 $n \le 21$ 内找到了 124 组在 Williamson 型等价下的 QT 序列集。其中，94 组对应于对称 Williamson 序列（符合先前的知识），30 组为非对称序列。
• 非对称序列： 搜索发现了偶数长度及 $n=9$ 时的非对称 QT 序列。然而，对于 $n=21$，未发现非对称序列，这支持了 Fitzpatrick 和 O'Keeffe 的猜想，即某些奇数长度的所有 Williamson 型序列都与对称序列等价。
• 无限族： 作者证明，任何至少包含一个非实条目的归一化 QHM，都会通过四元数的内自同构生成一个不可数无限的等价 QHM 族。
• 不等价性： 研究表明，由新发现的完美序列构造的 QHM 与以下对象不等价：
  • 复数傅里叶矩阵。
  • 包含两个复数条目的循环核 QHM。
  • 由先前文献中发现的特定 $Q_{24}$-序列构造的 QHM（例如对于阶数 5 和 7）。
• 存在性与不存在性： 等价性结果意味着，对于阶数 35、47、53 和 59，循环四元数 Hadamard 矩阵（条目属于 $Q^+$）不存在，这解决了先前解析工作留下的问题。

意义
本文的研究结果表明，四元数 Hadamard 矩阵具有比此前理解的更丰富的属性和更大量的存在。通过确立循环块中 QT 序列与 Williamson 型序列之间的等价性，作者提供了一个强大的过滤和枚举工具，从而能够发现此前无法触及的新序列和新矩阵。

构造出的 QHM 在量子信息理论中具有特殊的意义。它们对应于不是直接和形式的相互无偏测量 (MUMs)，这与超密集编码和其他量子通信协议相关。本文指出，对于 $n \ge 4$ 的阶数（特别是 $n=5$ 和 $n=7$），存在多个不等价的 QHM 族，这意味着 QHM 的景观比实数或复数情形更为复杂和多样，而在实数或复数情形下，等价类通常是有限的或更为简单的。这项工作为具有固定条目模式的 QHM 的进一步解析特征化奠定了基础。