Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP

논문 개요

이 논문은 상태 숨겨진 부분군 문제 (State Hidden Subgroup Problem, StateHSP) 의 비아벨 (non-abelian) 경우를 해결하는 새로운 알고리즘을 제안합니다. 구체적으로, 정사각형의 대칭군인 8 차 Dihedral 군 ($D_4$) 의 $N$ 개의 직곱 (direct product) 인 $D_4^N$ 에서 정의된 StateHSP 를 다룹니다. 이 알고리즘은 T 게이트로 켤레된 (T-conjugated) 안정자 (stabilizer) 를 학습하는 문제를 해결하며, 해밀토니안 분광학 (Hamiltonian spectroscopy) 및 양자 오류 정정과 같은 물리적 문제에 중요한 의의를 가집니다.

주요 성과는 샘플 복잡도와 계산 시간이 다항식 (polynomial) 이며, 상수 깊이 (constant depth) 의 회로만 필요하다는 점입니다. 이는 기존 비아벨 HSP 해결의 어려움 (예: 지수적으로 큰 차원을 가진 비가환 표현) 을 우회하여, 특정 표현 하에서 효율적인 해결책을 제시한 것입니다.

1. 문제 정의 (Problem Definition)

• StateHSP (상태 숨겨진 부분군 문제):
  • 유한군 $G$ 와 그 유니터리 표현 $\rho$ 가 주어졌을 때, 특정 부분군 $H \le G$ 와 상태 $|\Psi\rangle$ 를 제공합니다.
  • 조건 1: $h \in H$ 에 대해 $\rho(h)|\Psi\rangle = |\Psi\rangle$ (상태가 $H$ 에 의해 불변).
  • 조건 2: $g \notin H$ 에 대해 $|\langle\Psi|\rho(g)|\Psi\rangle| < 1 - \epsilon$ (다른 대칭성과의 중첩이 $\epsilon$ 만큼 떨어짐).
  • 목표: 숨겨진 부분군 $H$ 를 식별하는 것.
• Multiple-Squares StateHSP:
  • 군: $D_4^N$ ($N$ 개의 정사각형 대칭군의 직곱). $D_4$ 는 반사 $r$ 과 회전 $s$ 로 생성됨.
  • 표현: 더블 표현 (Doubled Representation) $U_2^N$. 이는 2 큐비트 (A, B) 쌍에 작용하며, $U_2(r^t s^k) = X_A^t e^{i\pi k Z_A/4} \otimes X_B^t e^{i\pi k Z_B/4}$ 형태를 가짐.
  • 숨겨진 원소: $h = (r^{t_1}s^{k_1}, \dots, r^{t_N}s^{k_N})$ 이며, $h^2=e$ (involution, 즉 자기 자신의 역원) 조건을 만족합니다.
  • 핵심 난제: $D_4$ 의 대부분의 기약 표현 (irreps) 이 지수적으로 큰 차원을 가지므로, 기존의 푸리에 샘플링 (Fourier sampling) 을 직접 적용하여 문제를 해결할 수 없습니다.

2. 방법론 (Methodology)

논문의 알고리즘은 비아벨 문제를 아벨 (abelian) 문제로 변환하여 해결하는 전략을 사용합니다. 주요 단계는 다음과 같습니다.

A. 알고리즘 단계

1. Pauli 안정자 학습 (Pauli Stabilizer Learning):
   • 숨겨진 원소가 이미 Pauli 연산자 (T 게이트가 없는 경우, 즉 $w=0$) 인지 확인합니다. 만약 그렇다면 기존 아벨 StateHSP 알고리즘으로 즉시 해결됩니다.
2. 반사 클래스 결정 (Determination of $w_{max}$):
   • 숨겨진 원소의 각 요소에서 반사 (reflection) 의 켤레 클래스를 결정하는 벡터 $w_{max}$ 를 찾습니다. 이는 다음 하위 과정을 통해 이루어집니다:
     • Parity Sampling (패리티 샘플링): $Z \otimes Z$ 측정을 수행하여 비트 문자열 $\pi$ 와 사후 측정 상태 $|\Psi(\pi)\rangle$ 를 얻습니다.
     • Bell-resolvable Set 생성: 여러 번의 샘플링을 통해 $\sum \pi_m = 0$ 을 만족하는 'Bell-해결 가능한 집합'을 구성합니다. 이 집합은 상태가 아벨 군 $Z_2^N \times Z_2^N$ 의 표현으로 변환되도록 합니다.
     • Bell-resolution (벨 분해): Bell-해결 가능한 집합에 대해 벨 측정과 X 측정을 수행하여 기약 표현 레이블 $(p, q)$ 를 추출합니다. 이는 푸리에 샘플링과 동일하게 작동합니다.
     • Null Space 및 $w_{max}$ 추출: 얻은 레이블들로부터 영공간 (null space) $K$ 를 구하고, 이를 통해 $w_{max}$ 를 계산합니다.
3. T 게이트 보정 (T-gate Correction):
   • 계산된 $w_{max}$ 를 사용하여 상태 $|\Psi\rangle$ 에 T 게이트 (또는 S 게이트) 를 적용합니다.
   • $T[w_{max}] U^N_2(h) T[w_{max}]^\dagger$ 연산을 수행하면, 숨겨진 원소가 T 게이트가 제거된 Pauli 안정자 형태 ($U^N_2(t, v, 0)$) 로 변환됩니다.
4. 최종 학습:
   • 변환된 상태는 이제 순수한 아벨 StateHSP (Pauli 안정자 학습 문제) 가 되므로, 기존 알고리즘으로 $t$ 와 $v$ 를 학습합니다.
   • 최종적으로 $w = t \odot w_{max}$ 연산을 통해 숨겨진 원소의 모든 성분 $(t, v, w)$ 를 복원합니다.

B. 핵심 기법: 아벨화 (Abelianization)

• 비아벨 군 $D_4^N$ 의 복잡한 표현을 Bell-해결 가능한 집합 (Bell-resolvable set) 을 통해 $Z_2^N \times Z_2^N$ (아벨 군) 의 표현으로 축소합니다.
• 이 과정에서 $w$ (T 게이트의 위치 정보) 에 대한 정보를 잃지 않으면서, $v$ (회전 정보) 와 $t$ (반사 정보) 를 분리하여 학습할 수 있는 구조를 만듭니다.
• "Good Null Space" 개념을 도입하여, 완벽한 고유 해 (unique solution) 를 찾을 필요 없이, 알고리즘의 후속 단계 (T 게이트 보정) 를 성공적으로 수행할 수 있는 충분한 정보를 가진 부분군만 찾으면 된다는 점을 증명합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

• 비아벨 StateHSP 의 효율적 해결:
  • $D_4^N$ 에서 T 게이트로 변형된 안정자 문제를 다항식 시간과 상수 깊이 회로로 해결하는 최초의 알고리즘을 제시했습니다.
  • 기존 비아벨 HSP 알고리즘들은 보통 지수적인 계산 시간이나 복잡한 제어 연산이 필요했으나, 본 알고리즘은 이를 우회했습니다.
• 샘플 복잡도:
  • $O(\epsilon^{-2}(N^2 + \log(N/\delta)))$ 개의 샘플로 높은 확률 ($1-\delta$) 로 문제를 해결합니다.
  • 이는 기존 HSP 알고리즘 (예: Bacon 의 알고리즘) 보다 샘플 복잡도 측면에서 개선되었습니다 ($O(N^3)$ 대비 $O(N^2)$).
• 물리적 응용 가능성:
  • T-doped Stabilizer States 학습: 클리포드 회로에 T 게이트가 섞인 상태의 대칭성을 학습하는 문제와 직접적으로 연결됩니다.
  • 해밀토니안 분광학 (Hamiltonian Spectroscopy): 해밀토니안의 대칭성 (특히 T 게이트와 관련된 비-Clifford 대칭성) 을 학습하여 에너지 준위 추정을 효율화하는 데 활용 가능합니다.
  • 양자 오류 정정: 비-아벨 위상 질서를 가진 모델이나 비-Clifford 게이트를 허용하는 안정자 코드 연구에 기여합니다.

4. 의의 및 결론 (Significance)

• 표현 의존적 해결책의 중요성:
  • 일반적인 비아벨 HSP 는 해결이 어렵다고 알려져 있지만, 특정 표현 (Representation) 하에서는 StateHSP 가 효율적으로 해결될 수 있음을 보였습니다. 이는 군의 기약 표현 구조가 문제의 난이도를 결정하는 핵심 요소임을 시사합니다.
• 실용적 양자 알고리즘:
  • 복잡한 다중 큐비트 제어 연산이나 깊은 회로 없이, 2 큐비트 연산과 상수 깊이 회로만으로 구현 가능하다는 점은 현재의 오류 정정 전 (NISQ) 양자 컴퓨터나 초기 오류 정정 양자 컴퓨터에서도 실행 가능한 잠재력을 가집니다.
• 미래 연구 방향:
  • 이 연구는 비아벨 StateHSP 를 해결할 수 있는 다른 군과 표현을 찾는 새로운 연구 방향을 제시합니다. 특히, 일반 HSP 는 어렵지만 특정 StateHSP 는 쉬운 경우를 규명하는 것이 향후 중요한 과제로 꼽힙니다.

요약

이 논문은 T 게이트로 변형된 안정자 상태를 학습하는 문제를 Multiple-Squares StateHSP로 공식화하고, Bell-샘플링과 아벨화 전략을 통해 이를 효율적으로 해결하는 알고리즘을 제안했습니다. 이 알고리즘은 샘플 효율성과 회로 깊이 측면에서 우수하며, 양자 학습 및 해밀토니안 분광학 등 물리적 문제 해결에 중요한 도구가 될 것으로 기대됩니다.