Pauli Decomposition by Character Theory: A Memory-Bounded Algorithm for Qubits and Qudits

기술 요약: 캐릭터 이론에 의한 파울리 분해 (Pauli Decomposition)

문제 정의
파울리 분해는 트로터화(Trotterization), 위상 추정(phase estimation), 희소 해밀토니안 시뮬레이션(sparse-Hamiltonian simulation), 변분 관측량(variational observables)을 포함한 양자 알고리즘의 필수 전제 조건이다. 본 과제의 목표는 임의의 $n$-큐비트 연산자 $H$를 다음과 같이 파울리 스트링(Pauli strings)의 선형 결합으로 표현하는 것이다:
$$H = \sum_{x,z} c_{x,z} P(x, z)$$
여기서 $P(x, z)$는 $\{I, X, Y, Z\}$의 텐서 곱이다. 트레이스 투영(trace projection, $c_{x,z} = \text{Tr}(H \cdot P(x,z))/2^n$)을 통해 이 계수들을 직접 계산하는 방식은 구현 방식에 따라 $O(2^{5n})$ 또는 $O(2^{3n})$의 지수적 비용이 발생하므로, 대규모 시스템에는 적용이 불가능하다. 기존 연구(예: Georges et al., Hamaguchi et al.)는 고속 월시-하다마드 변환(Fast Walsh-Hadamard Transform, FWHT)을 사용하여 점근적 시간 복잡도를 $O(n \cdot 4^n)$으로 줄였으나, 이러한 방법들은 일반적으로 전체 $2^n \times 2^n$ 연산자 행렬을 메모리에 실체화(materialize)해야 한다. 이는 결과물인 파울리 확장이 희소(sparse)하더라도 피크 메모리 사용량이 $O(4^n)$에 달하게 만드는 "메모리 벽(memory wall)"을 형성하며, 이로 인해 실제 적용 가능한 시스템이 약 $n \le 15$ 큐비트로 제한된다.

방법론
본 논문은 파울리 분해를 **아벨 군(abelian group) $(\mathbb{Z}_2)^n$의 캐릭터 이론(character theory)**을 통해 재정의한다.

1. 캐릭터 이론적 유도:

   • 저자들은 대각 성분 파울리 스트링($Z^{\otimes z}$)을 군 $(\mathbb{Z}_2)^n$의 캐릭터 $\chi_z(v) = (-1)^{\langle v, z \rangle}$로 식별한다.
   • 일반적인 파울리 스트링 $X^{\otimes x}Z^{\otimes z}$는 캐릭터 $\chi_z$와 결합된 이동 연산자(shift operator) $X^{\otimes x}$로 간주된다.
   • 분해 과정은 $2^n$개의 독립적인 고속 월시-하다마드 변환(FWHT)을 수행하는 것과 동등함을 보여준다. 고정된 이동 $x$에 대해, 계수들은 행렬 요소 $\{T_{v, v+x}\}_v$를 캐릭터에 대해 변환함으로써 얻어진다.
   • 본 논문은 "bare" 기저($X^{\otimes x}Z^{\otimes z}$)와 "genuine" 기저(중첩된 큐비트에 $Y = iXZ$가 삽입된 형태)를 구분한다. 알고리즘은 먼저 bare 기저에서 분해를 수행한 후(단계 1), 단계 2에서 위상 보정 $i^{|x \wedge z|}$를 적용하여 genuine 기저로 변환한다. 이러한 분리는 계산 비용이 두 기저 모두 동일하다는 점을 명확히 하며, 기저의 선택은 대수적 필연성이 아닌 게이트 컴파일을 위한 에르미트(Hermitian) 항 생성이라는 위상 규약(phase convention)에 따른 것임을 보여준다.

2. 메모리 제한 스트리밍 구현 (paulikit):

   • 메모리 병목 현상을 극복하기 위해, 저자들은 스트리밍 알고리즘을 구현한다. 입력의 성격에 따라 다음과 같이 동작한다:
     • 희소 행렬 입력(Sparse matrix inputs): paulikit는 $(x, z, \text{coefficient})$ 청크를 스트리밍하며, 전체 $2^n \times 2^n$ 밀집 연산자를 실체화할 필요가 없다.
     • 밀집 행렬 입력(Dense matrix inputs): assume_dense=True인 경우, 각 청크의 작업 세트(working set)는 작게 유지되지만, 전체 프로세스 메모리는 입력된 밀집 행렬 자체를 유지해야 한다(예: 13 큐비트에서 약 1 GiB).
   • 청크 독립성(Chunk Independence): 레마 2(Lemma 2)를 활용하여, 이동(shift) $x$를 서로 겹치지 않는 청크들로 분할한다. 각 청크는 독립적으로 처리된다: 행 $T_{v, v+x}$를 수집하고, FWHT를 통해 변환하며, 위상을 보정하고, 임계값(thresholding)을 적용한다.
   • 스트리밍 누적(Streaming Accumulation): 밀집된 중간 배열을 저장하는 대신, 알고리즘은 각 청크에 대해 원시 $(x, z, \text{coefficient})$ 트리플을 생성한다. 이를 통해 희소 입력 시 피크 메모리 사용량은 전체 연산자 크기가 아닌 $O(\text{chunk\_size} \times 2^n + N_{\text{terms}})$로 제한되며, 여기서 $N_{\text{terms}}$는 살아남은 계수의 수이다.
   • 최적화: 구현 과정에서 Python 레벨의 루프를 FWHT 및 계수 추출을 위한 컴파일된 C 커널로 대체하여 오버헤드를 최소화한다. 또한, 컴파일된 커널의 존재 여부에 따른 자동 선택 메커니즘을 통해 GIL 경합을 피하며, process-pool과 thread-pool 병렬 처리를 모두 지원한다.

주요 기여

1. 캐릭터 이론적 정식화: 본 논문은 $O(n \cdot 4^n)$ 파울리 분해 알고리즘을 $(\mathbb{Z}_2)^n$의 캐릭터 이론에 명시적으로 근거하여 유도하였으며, 이를 통해 큐디트(qudit)로의 자연스러운 일반화를 제시한다(Corollary 1).
2. 기저의 명확화: "bare" 기저에서의 분해가 완전하며 "genuine" 기저와 계산적으로 동등함을 입증하였다. 이는 $Y$의 사용이 변환 자체의 요구 사항이 아니라 에르미트성을 위한 위상 규약임을 명확히 한다.
3. 메모리 제한 알고리즘: 주요 공학적 기여는 $O(n \cdot 4^n)$의 시간 복잡도를 유지하면서도, 희소 입력에 대해 피크 메모리 사용량을 전체 연산자 크기와 무관하게 유지하는 paulikit 라이브러리이다. 이를 통해 가용 RAM의 힐베르트 공간 차원을 훨씬 초과하는 연산자(예: $2^{14}$ 차원 및 희소 출력)의 분해를 가능하게 한다.
4. 엄격한 검증 및 경계 설정: 저자들은 철저한 개별 항 정확도 검사(최대 $1.47 \times 10^9$개 항)를 수행하였으며, 이론적인 Work-Span 및 메모리 대역폭 상한을 도출하였다. 이러한 경계값은 특정 저사양 Linux 플랫폼에서의 실제 측정치를 통해 검증되었다.

결과

• 확장성: 알고리즘은 완전히 결합된 조화 진동자(fully coupled harmonic oscillator) 패밀리에 대해 테스트되었다. $N=150$개의 진동자(14 큐비트 필요, 힐베르트 공간 차원 $2^{14} = 16,384$)의 경우, 연산자는 $91,652,096$개의 비제로(nonzero) 파울리 항을 가졌다.
• 메모리 효율성: $N=150$의 경우 밀집 방식(naive dense approach)은 수 GiB의 메모리를 필요로 하여 노트북에서도 처리가 가능한 수준이다. 그러나 $N=300$ ($n=16$, 약 14.7억 개의 항)에 도달하면, 생존한 트리플만 약 44 GiB를 차지하며 전체 밀집 행렬은 64 GiB에 달한다. paulikit의 스트리밍 성능을 측정했을 때, $N=50$에서 $N=300$까지 생존한 항의 수가 1165배 증가하는 동안, 분해 메모리는 13.2 MiB에서 46.0 MiB로, 전체 프로세스 피크 RSS는 64.7 MiB에서 99.6 MiB로만 증가하여 메모리가 결과 크기와 분리되어 있음을 확인시켜 주었다.
• 성능: 4코어 플랫폼에서 스레드 구현은 $1.81\times$ (2개 워커) 및 $3.36\times$ (4개 워커)의 속도 향상을 달성하였으며, 이는 측정된 직렬 분율(serial fraction)로부터 도출된 암달의 법칙(Amdahl's law) 예측과 밀접하게 일치하였다. 컴파일된 커널은 $1.34$ GFLOPs/s의 처리량을 달성하였으며, 이는 커널이 메모리 제한적(memory-bound)임을 확인시켜 준다(플랫폼의 지속 가능한 대역폭 상한의 약 $34\%$에서 작동).
• 정확성: 모든 계수는 독립적인 투영법을 통해 검증되었으며, 최대 절대 오차는 $8.7 \times 10^{-19}$로 기계 정밀도(machine precision)와 일치하였다.

의의 및 주장
본 논문은 자신의 주요 기여가 점근적 시간 복잡도의 감소(여전히 $O(n \cdot 4^n)$으로 이전의 최첨단 기술과 동일함)가 아니라 메모리 확장성에 있다고 겸허히 주장한다. 의의는 메모리 제약으로 인해 과거에 접근 불가능했던 대규모 희소 해밀토니안의 파울리 분해를 가능하게 했다는 점에 있다.

• 이론적 범위: 본 연구는 "genuine" 파울리 기저가 $(\mathbb{Z}_2)^n \times (\mathbb{Z}_2)^n$의 중앙 확장(central extension) 내에서의 위상 규약 선택임을 확립하였으며, 캐릭터 이론적 접근 방식이 큐디트로 자연스럽게 확장됨을 보여준다.
• 실용적 범위: paulikit 라이브러리는 비에르미트(non-Hermitian) 연산자(첫 번째 클래스 입력으로 취급)와 대규모 희소 해밀토니안을 슈퍼컴퓨팅 자원 없이도 분해할 수 있게 한다.
• 한계점: 저자들은 계수 추출이 큐디트로 확장될 수는 있으나, 클리포드 트월링(Clifford twirling)의 설계 특성(예: 2-design)이 합성 차원(composite dimensions)으로 자동 확장되지는 않는다는 점을 명시하였다. 본 논문은 큐디트를 위한 클리포드 트월링 문제를 해결한다고 주장하지 않으며, 큐디트 모듈을 함께 제공하지도 않는다. 성능 경계는 테스트된 특정 하드웨어에 국한되며, 모든 영역에서 다른 구현보다 우월하다고 주장하지 않는다.

요약하자면, 본 논문은 이론적인 $O(n \cdot 4^n)$ 복잡도와 대규모 양자 시뮬레이션의 실제적인 제약 사이의 간극을 메우는, 이론적으로 근거 있고 메모리 효율적인 파울리 분해 구현을 제시한다.