Quaternionic Perfect Sequences and Hadamard Matrices

技術要約：四元数完全系列とアダマール行列

問題の定義
本論文は、四元数型完全系列および巡回ブロックを持つ四元数型アダマール行列の列挙と分類について扱っている。有限系列が「完全（perfect）」であるとは、その周期自己相関がすべての非自明な巡回シフトに対して消失することを指す。完全バイナリ系列は長さ4においてのみ存在すると予想されているが、アルファベットを四元数に拡張することで、より長い系列が可能となる。具体的には、著者らはアルファベット $Q^+ = Q_8 \cup qQ_8$ （ここで $Q_8 = \{\pm 1, \pm i, \pm j, \pm k\}$ および $q = (1+i+j+k)/2$）上の系列に焦点を当てている。これらの系列は、特定の自己相関および相互相関条件を満たす4つのバイナリ系列の組、すなわちQT系列と一対一に対応している。

この領域における中心的な課題は、ブロック行列に課される対称性の制約を緩和した場合の、完全系列の網羅的な探索における計算の困難さである。従来の網羅的探索は、長さ $n \le 13$ に限定されていた。さらに、QT系列（より弱い相互相関条件を満たすもの）とウィリアムソン型系列（より強い「両立性（amicability）」条件を満たすもの）との理論的な関係は、巡回ブロックの場合において完全には確立されておらず、フィルタリング・アルゴリズムの有効性を制限していた。

手法
著者らは、バイナリ系列の行和の分解に基づく新しい列挙アルゴリズムを開発した。本手法の核心は以下の通りである：

1. 理論的等価性： 著者らは（定理9）、巡回ブロック型行列において、QT系列を定義する条件がウィリアムソン型系列を定義する条件と等価であることを証明した。具体的には、巡回ブロックにおける相互相関条件 (1.2) が、両立性条件 ($XY^\top = YX^\top$) を含意することを示した。この等価性は極めて重要であり、探索中に強力なフィルタリング基準を使用することを可能にする。
2. 行和分解： アルゴリズムは、「行和分解」補題を利用している。これは、長さ $n$ のQT系列の組に対して、それらの行和の平方和が $4n$ に等しいというものである。探索空間は、行和がこの分解を満たすバイナリ系列に制限される。
3. ペア列挙： 4つの系列を3つずつの組として列挙する代わりに、アルゴリズムは4つの系列を2つのペアに分離する。まずペア $(A, B)$ と $(C, D)$ を個別に列挙し、それぞれの自己相関と相互相関を計算する。その後、自己相関の和が相殺され、かつ相互相関条件が満たされるペアを照合する。
4. 周波数領域フィルタリング： 探索を最適化するため、アルゴリズムは離散フーリエ変換（DFT）を採用している。候補となるペアに対し、自己相関条件から導かれるパワースペクトル密度（PSD）の制約、および相互相関条件から導かれる相互パワースペクトル密度（CPSD）の制約を用いてフィルタリングを行う。このフィルタリングは、完全な相関チェックを行う前に、無効なペアを排除するために早期に適用される。
5. 等価分類： 著者らは、3つの等価レベルを定義している：ウィリアムソン型等価、QT等価、およびアダマール等価である。著者らは、反転、入れ替え、デシメーション（間引き）、および巡回シフトなどの操作を利用して、列挙された結果をこれらの等価類までフィルタリングするための後処理ステップを実装している。

主な貢献

• 理論的等価性： 本論文は、巡回ブロックの場合、QT系列とウィリアムソン型系列が等価であることを確立した。これにより、QT系列の比較的弱い条件が、巡回ケースにおけるウィリアムソン型行列に求められる強力なペア両立性条件を実際に強制していることが証明された。
• アルゴリズムの効率性： 提案されたアルゴリズムは、従来の手法よりも大幅に高速である。ウィリアムソン型系列への等価性を活用することで、候補となるブロックペアの数を、長さ $n=20$ において25,000倍以上の係数で削減するフィルタリングメカニズムを導入した。
• 網羅的列挙： 著者らは、長さ $n \le 21$ までのQT系列を網羅的に列挙するためにこのアルゴリズムを実装した。これにより、従来の網羅的限界であった $n=13$ を更新した。
• 新しい行列の構成： 列挙によって得られた新しい完全系列を用い、新しい四元数型アダマール行列（QHM）を構成した。著者らは、$n \le 21$ の次数に対するこれらの行列の具体的な例を提示している。
• 解析的特性化： 著者らは、特定の成分パターンを持つ次数5のQHMの解析的特性化を行い、新たに発見された完全系列から生成される行列が、既知のファミリー（HigginbothamやWorley、あるいはKuznetsovによって構成されたものなど）と等価ではないことを証明した。

結果

• 列挙データ： 著者らは、ウィリアムソン型等価までで、長さ $n \le 21$ において124組のQT系列を見出した。このうち、94組は対称なウィリアムソン系列に対応しており（既知の知見と一致）、30組は非対称である。
• 非対称系列： 探索により、偶数の長さおよび $n=9$ において非対称なQT系列が特定された。しかし、$n=21$ では非対称な系列は見つからず、特定の奇数長のすべてのウィリアムソン型系列は対称なものと等価であるというFitzpatrickとO'Keeffeの予想を支持する結果となった。
• 無限族： 著者らは、少なくとも一つの非実成分を持つ正規化されたQHMは、四元数の内部自己同型を通じて、正規化されたQHMの非可算無限族を生成することを証明した。
• 非等価性： 本研究は、新しく発見された完全系列から構成されるQHMが、以下に対して等価ではないことを示している：
  • 複素フーリエ行列。
  • 2つの複素成分を含む巡回コアを持つQHM。
  • 先行文献で見つかった特定の $Q_{24}$ 系列から構成されるQHM（例：次数5および7）。
• 存在の不在： この等価性の結果は、次数35、47、53、および59において、成分 $Q^+$ を持つ巡回型四元数型アダマール行列が存在しないことを意味しており、これまでの解析的研究によって残されていた問題を解決した。

意義
本論文の結果は、四元数型アダマール行列がこれまで理解されていたよりも豊かな特性と豊富さを持っていることを示唆していると著者らは主張している。巡回ブロックにおけるQT系列とウィリアムソン型系列の間の等価性を確立することで、著者らはフィルタリングと列挙のための強力なツールを提供し、以前はアクセス不可能であった新しい系列と行列の発見を可能にした。

構成されたQHMは、量子情報理論において特に重要である。これらは、相互無相関基底（MUBs）の直接和ではない相互無相関測定（MUMs）に対応しており、これらは超高密度符号化やその他の量子通信プロトコルに関連している。本論文は、$n \ge 4$（具体的には $n=5$ および $n=7$）の次数において、互いに非等価な複数のQHMのファミリーが存在することは、実数または複素数の場合（等価類が有限であったりより単純であったりすることが多い）よりも、四元数型アダマール行列の景観がはるかに複雑で多様であることを示唆している。本研究は、固定された成分パターンを持つQHMのさらなる解析的特性化のための基礎を築くものである。