TSS Graphs for Hadamard Matrices: Real vs Complex

기술 요약: Hadamard 행렬에 대한 TSS 그래프: 실수형 대 복소수형

문제 정의

본 논문은 양자 게이트로 사용될 때 실수 및 복소수 Hadamard 행렬에 의해 유도되는 계산적 변환을 공식적으로 해석하는 과제를 다룬다. Hadamard 행렬은 균등한 중첩 상태를 생성하기 위해 이산 수학 및 양자 컴퓨팅 분야에서 잘 확립되어 있으나, 저자들은 특정 입력 조건(특히 상태들의 중첩된 조합) 하에서의 동작이 비균일한 확률 분포를 생성한다는 점에 주목한다. 핵심 문제는 이러한 변환을 단순히 선형 대수적 연산으로 보는 것이 아니라, 상태 라우팅, 간섭 및 수렴의 패턴을 드러내는 위상적 구조로 특징짓는 것이다. 저자들은 이러한 변환이 그래프 이론, 특히 위상적 중첩 구조(Topological Structure of Superpositions, TSS) 프레임워크 내에서 체계적으로 분석될 수 있는 독특한 계산 기하학을 생성하는지 결정하고자 한다.

방법론

본 연구는 Hadamard 행렬의 입력-출력 상태 매핑을 모델링하기 위해 그래프 이론적 접근 방식을 채택한다. 방법론은 다음과 같이 진행된다:

1. 데이터 소스: 본 연구는 Neil Sloane의 라이브러리(차수 최대 28)와 Bruzda 등의 복소수 Hadamard 행렬 카탈로그에서 추출한 실수 및 복소수 Hadamard 행렬을 활용한다. 분석에는 차수 16까지의 행렬이 포함되며, 계산상의 제약으로 인해 상세한 그래프 생성은 차수 8로 제한된다.
2. 그래프 구축 (TSS 프레임워크):
   • 정점 ($V$): 주소 지정 가능한 계산 기저 상태(computational basis states)를 나타낸다.
   • 간선 ($E$): 유향 간선 $(u, v)$는 건설적 및 파괴적 간섭에 의해 구동되는 입력 상태 $u$에서 출력 상태 $v$로의 허용 가능한 전이를 나타낸다.
   • 입력 생성: 저자들은 단일 입력 상태와, 결정적으로, 중첩된 상태들의 조합(얽힌 집합)을 테스트한다. 차수가 $n$인 행렬의 경우, $n/2$개의 1과 $n/2$개의 0으로 구성된 시퀀스를 결합하여 얽힌 집합을 생성한다.
3. 그래프 분석:
   • 동형 분류 (Isomorphism Classification): 진정한 계산 기하학을 사소한 재라벨링과 구분하기 위해, 그래프를 동형 클래스로 분할한다. 클래스를 고유하게 식별하고 정렬하기 위해 차수 다항식(degree polynomials)을 완전 불변량으로 사용한다.
   • 위상적 지표: 연구는 기본적인 지표(정점 카디널리티 $|V|$, 간선 수 $|E|$, 자기 루프 빈도)와 강결합 성분(Strongly Connected Components, SCCs), 단순 유향 사이클, 클래스 카디널리티를 포함한 고차 속성을 평가한다.
4. 실험 설정: 계산은 8코어 프로세서에서 수행되었다. 차수 16 행렬(특히 MS002)의 경우, 가능한 총 조합은 약 75,000개이다. 이 풀(pool)에서 플롯 생성을 위해 4,000개의 순열을 샘플링하였고, 통계 생성을 위해 10,000개를 사용하였다.

주요 기여

• 비균일 확률 관찰: 본 논문은 단일 입력 상태는 종종 동일한 확률의 조밀한 출력을 생성하는 반면, 중첩된 입력 상태의 조합은 비균일한 확률 분포를 생성함을 입증한다. 이는 Grover 연산자와 달리 수동적인 파라미터화 없이도 진폭 증폭(amplitude amplification)이 가능하다는 점에서 실질적인 중요성을 갖는다.
• Hadamard 게이트의 위상적 특징화: 저자들은 Hadamard 변환을 유향 그래프로 매핑하여, 이 연산자들이 무작위 또는 완전 그래프가 아닌, 제약이 있고 높은 대칭성을 가진 라우팅 네트워크 패밀리를 생성함을 밝혀냈다.
• 실수형 및 복소수형 행렬의 구분: 본 연구는 실수형 및 복소수형 Hadamard 행렬이 유사한 TSS 그래프 구조를 생성하지만, 복소수형 행렬은 위상 인자(via $+i, -i$)를 도입하여 간섭 패턴을 변화시키고, 결과적으로 다른 확률 인자 및 수렴 동작을 유도한다는 점을 강조한다.
• 구조적 끌개(Structural Attractors) 식별: 분석 결과, 다양한 입력 벡터가 보존된 고대칭 라우팅 토폴로지로 수렴하는 경향이 있으며, 이는 변환 공간 내에 "구조적 끌개"가 존재함을 시사한다.

결과

15개의 행렬(차수 8 및 16)을 분석한 결과 4,500개 이상의 유향 그래프가 도출되었으며, 이들은 행렬당 6개에서 97개의 고유한 동형 클래스로 분할되었다.

• 그래프 불변량 및 추세:
  • 간선 밀도: 동형 클래스 인덱스(차수 다항식에 의해 정렬됨)와 총 간선 수 사이에는 명확한 양의 상관관계가 존재한다. 동형 클래스가 적은 행렬일수록 간선 축적률이 더 가파르게 나타난다.
  • 자기 루프 (Self-Loops): 불변 상태(invariant states)인 자기 루프의 분포는 일반적으로 클래스 인덱스가 증가함에 따라 증가하며, 특정 클래스(예: M011의 특정 클래스에서 최대 11개)에서 고점과 정점에 도달한다.
  • 연결성: 강결합 성분(SCCs)은 대조적인 동작을 보인다. 일부 행렬(예: M008)은 클래스 인덱스가 증가함에 따라 SCC가 단조 감소하는 경향을 보이는 반면, 다른 행렬(예: M011)은 여러 컴포넌트로 파편화된 후 진동하는 모습을 보인다.
• 사이클 분포: 단순 사이클 수는 낮은 인덱스의 클래스에서는 일반적으로 낮지만, 높은 인덱스에서는 불연속적이고 양자화된 급증을 보이며 특정 구성에서 2,365개의 사이클 피크에 도달한다. 이는 국소적인 고구조적 재귀 및 폐쇄 루프 피드백 영역의 존재를 나타낸다.
• 입력 스케일링:
  • 행렬 차원: 입력 차원이 높아질수록 간선 수와 동형 클래스의 특정 블록 대각 분할(block-diagonal partitions)이 증가한다.
  • 중첩 카디널리티: 더 높은 차수의 동형 클래스에 접근하기 위해서는 더 조밀한 중첩(더 많은 비제로 입력 성분)이 필요하다.
• 수렴: 행렬 MS002(차수 16)에서 나타나는 "상태의 수렴"은 주목할 만한 발견으로, 특정 입력이 출력 상태의 수를 감소시키는 현상을 보여주며, 이는 밝은 색조의 빈도 발생으로 시각화된다.
• 동형성: 동일한 입력 상태 집합으로부터 생성된 그래프들은 거의 동형인 것으로 나타났으며, 이는 입력 중첩의 수에 기반한 높은 구조적 균일성을 시사한다.

의의 및 주장

본 논문은 TSS 그래프 프레임워크가 Hadamard 행렬의 전역적 계산 구조를 직접적인 위상적 시각화로 제공하며, 유니터리 연산자를 이산적인 조합 구조로 추상화한다고 주장한다.

• 알고리즘적 잠재력: 저자들은 이러한 TSS의 동형적 특성을 활용하여, 향후 양자 컴퓨터를 위한 어셈블리 언어에서 "변수 선언(variables declarations)"을 위한 잠재적 응용 가능성을 제시하며, 이 그래프들이 입력 중첩에 따라 거의 동형이라는 점을 이용할 수 있다고 제안한다.
• 진폭 증폭: 중첩된 입력에 의해 생성되는 비균일 확률의 발견은 Grover 연산자의 전형적인 수동 파라미터화가 필요 없는 진폭 증폭 메커니즘으로 제시된다.
• 한계점: 저자들은 차수 16(4 큐비트) 이상의 Hadamard 행렬를 처리하는 데 따르는 계산적 부담을 인정한다. 비록 통계 분석을 위해 차수 16 행렬(특히 MS002)을 포함했으나, 상세한 그래프 생성 및 분석은 차수 8로 제한되었다. 저자들은 이 작업을 자신들의 이전 TSS 연구의 확장으로 규정하며, 완전한 양자 알고리즘을 제시하기보다는 양자 소프트웨어 개발에 필요한 추상화를 구축하는 것을 목표로 한다.

요약하자면, 본 논문은 Hadamard 행렬의 대수적 성질과 그로부터 유도되는 상태 전이의 위상적 성질 사이의 가교를 구축하며, 양자 정보 라우팅과 잠재적 알고리즘 설계를 바라보는 새로운 관점을 제공한다.