Quaternionic Perfect Sequences and Hadamard Matrices

기술 요약: 사원수 완벽 수열과 하다마르 행렬

문제 정의
본 논문은 사원수 완벽 수열의 열거 및 분류와 순환 블록을 갖는 사원수형 하다마르 행렬과의 대응 관계를 다룬다. 유한 수열이 모든 비자명한 순환 이동에 대해 주기적 자기상관이 0이 될 때 이를 "완벽(perfect)"하다고 한다. 완벽 이진 수열은 길이 4에서만 존재한다는 추측이 있으나, 알파벳을 사원수로 확장하면 더 긴 수열이 가능하다. 구체적으로, 저자들은 알파벳 $Q^+ = Q_8 \cup qQ_8$ (여기서 $Q_8 = \{\pm 1, \pm i, \pm j, \pm k\}$ 이고 $q = (1+i+j+k)/2$)에 대한 수열에 초점을 맞춘다. 이러한 수열은 특정 자기상관 및 교차상관 조건을 만족하는 네 개의 이진 수열의 쿼드러플(quadruple), 즉 QT 수열과 일대일 대응 관계에 있다.

이 분야의 중심적인 과제는, 종종 기저 블록 행렬에 부과되는 대칭 제약을 완화할 때 발생하는 계산적 어려움이다. 기존의 전수 조사 방식은 길이를 $n \le 13$으로 제한하였다. 또한, (더 약한 교차상관 조건을 만족하는) QT 수열과 (더 강한 "친밀성(amicability)" 조건을 만족하는) 윌리엄슨 유형(Williamson-type) 수열 사이의 이론적 관계가 순환 블록의 경우 완전히 확립되지 않아, 필터링 알고리즘의 효과적인 활용이 제한되었다.

방법론
저자들은 이진 수열의 행합(rowsum) 분해를 기반으로 한 새로운 열거 알고리즘을 개발하였다. 방법론의 핵심은 다음과 같다:

1. 이론적 동등성: 저자들은 순환 블록의 경우 QT 수열을 정의하는 조건이 윌리엄슨 유형 수열을 정의하는 조건과 동일함을 증명한다(정리 9). 구체적으로, 그들은 순환 블록에 대한 교차상관 조건 (1.2)이 쌍별 친밀성 조건($XY^\top = YX^\top$)을 함의함을 보여준다. 이 동등성은 더 강한 필터링 기준을 탐색 중에 사용할 수 있게 하는 결정적인 요소이다.
2. 행합 분해: 알고리즘은 길이 $n$인 네 개의 QT 수열에 대하여, 각 행합의 제곱의 합이 $4n$이라는 "행합 분해" 보조정리를 활용한다. 탐색 공간은 행합이 이 분해를 만족하는 이진 수열으로 제한된다.
3. 쌍별 열거: 알고리즘은 네 개의 수열을 세 개씩 묶어 열거하는 대신, 네 개를 두 쌍으로 분리한다. $(A, B)$ 쌍과 $(C, D)$ 쌍을 각각 별도로 열거하여 각각의 자기상관과 교차상관을 계산한다. 그 후, 자기상관의 합이 상쇄되고 교차상관 조건이 만족되는 쌍들을 매칭한다.
4. 주파수 영역 필터링: 탐색을 최적화하기 위해 알고리즘은 이산 푸리에 변환(DFT)을 사용한다. 알고리즘은 자기상관 조건으로부터 유도된 전력 스펙트럼 밀도(PSD) 제약과 교차상관 조건으로부터 유도된 교차 전력 스펙트럼 밀도(CPSD) 제약을 사용하여 후보 쌍들을 필터링한다. 이 필터링은 전체 상관도 검사 전에 유효하지 않은 쌍을 조기에 제거하기 위해 적용된다.
5. 동등성 분류: 저자들은 세 가지 수준의 동등성을 정의한다: 윌리엄슨 유형 동등성, QT 동등성, 그리고 하다마르 동등성. 저자들은 부정(negation), 교환(swapping), 데시메이션(decimation), 순환 이동과 같은 연산을 활용하여 열거된 결과들을 이러한 동등성 클래스까지 필터링하는 후처리 단계를 구현한다.

주요 기여

• 이론적 동등성: 본 논문은 순환 블록의 경우 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은 사원수의 내부 자기동형(inner automorphisms)을 통해 무수히 많은 동등한 정규화된 QHM 가계를 생성함을 증명한다.
• 비동등성: 새로 발견된 완벽 수열로부터 구축된 QHM은 다음의 것들과 동등하지 않음을 보여준다:
  • 복소 푸리에 행렬(Complex Fourier matrices).
  • 두 개의 복소 엔트리를 포함하는 순환 코어를 가진 QHM.
  • 기존 문헌(예: 차수 5 및 7)에서 발견된 특정 $Q_{24}$-수열으로부터 구축된 QHM.
• 존재의 부재: 이 동등성 결과는 순환 사원수 하다마르 행렬이 $Q^+$의 엔트리를 가질 때 차수 35, 47, 53, 59에서는 존재하지 않음을 의미하며, 이는 이전의 분석적 연구에서 남겨진 문제를 해결한다.

의의
본 논문의 결과는 사원수 하다마르 행렬이 기존에 이해되었던 것보다 더 풍부한 속성과 더 많은 양의 행렬을 가지고 있음을 시사한다. 순환 블록에 대해 QT 수열과 윌리엄슨 유형 수열 사이의 동등성을 확립함으로써, 저자들은 새로운 수열과 행렬을 발견할 수 있게 하는 강력한 필터링 및 열거 도구를 제공하였다.

구축된 QHM은 특히 양자 정보 이론에서 중요하다. 이들은 초고밀도 코딩(superdense coding) 및 기타 양자 통신 프로토콜과 관련된, 상호 무립(Mutually Unbiased Measurements, MUMs)이 상호 무립 기저(MUBs)의 직접 합이 아닌 경우에 대응한다. 본 논문은 $n \ge 4$ (특히 $n=5$ 및 $n=7$)에 대해 여러 개의 서로 다른 동등하지 않은 QHM 가계가 존재한다는 사실이, 실수나 복소수 사례(그 경우 동등성 클래스가 유한하거나 더 단순한 경우가 많음)보다 사원수 하다마르 행렬의 지형이 훨씬 더 복잡하고 다양함을 시사한다고 주장한다. 이 연구는 고정된 엔트리 패턴을 가진 QHM의 추가적인 분석적 특성 규명을 위한 토대를 마련한다.