기술 요약: 양자 대칭성 학습 (Learning Quantum Symmetries)

1. 문제 정의

본 논문은 양자 객체의 대칭성을 학습하는 계산 문제를 다룬다. 양자의 대가 된 고전적 객체의 대칭성을 찾는 알고리즘(은닉 부분군 문제, HSP를 통해)은 이미 잘 확립되어 있으나, 양자 객체로의 확장은 그동안 덜 탐구되어 왔다.

저자들은 이 문제의 세 가지 주요 차원에 집중한다:

1. 비가환 군 (Non-Abelian Groups): 기존에 연구된 아벨 군 설정을 넘어, 광범위한 비가환 군 클래스로 상태 은닉 부분군 문제(StateHSP)를 확장한다.
2. 물리적 대칭성 정의: "보존 대칭성(Bose symmetries)"(엄격한 불변성, $R(g)\rho = \rho$)을 넘어, 전역 위상(global phase) 차이만을 고려하는 "애니온 대칭성(Anyonic symmetries)"(불변성 $R(g)\rho = e^{i\theta}\rho$)으로 확장한다. 이는 전역 위상에 의해 차이가 나는 상태들의 물리적 구별 불가능성과 일치한다.
3. 일반 양자 객체: 양자 상태를 넘어 유니터리(unitary), 해밀토니안(Hamiltonian), 그리고 상태들의 집합과 같은 다른 객체로 대칭성 학습을 확장한다.

핵심 과제는 기존의 효율적인 대칭성 학습 알고리즘들이 아벨 군과 선형 표현(linear representations)에 국한되어 있다는 점이다. 일반적인 비가elian HSP는 어려운 문제로 여겨지며, 투영 표현(projective representations, Pauli 연산자와 같이 양자 역학에서 흔히 나타나는)은 표준적인 선형화 기법으로는 기존 알고리즘 프레임워크 내에서 쉽게 해결할 수 없는 대수적 복잡성을 도입한다.

2. 방법론 및 기술적 접근

본 논문은 이러한 과제들을 해결하기 위해 세 가지 별개의 기술적 기둥을 개발한다.

A. 비가환 StateHSP를 위한 정규 핵(Normal Core) 알고리즘

비가환 군을 다루기 위해, 저자들은 고전적 HSP(Hallgren, Russell, Ta-Shma)의 "정규 핵" 알고리즘을 양자 StateHSP 설정으로 일반화한다.

• 기법: 비가환 군에 대한 **약한 푸리에 샘플링(weak Fourier sampling)**을 활용한다. 은닉 부분군 $S$를 직접 복구하는 대신, $S$를 포함하는 가장 큰 정규 부분군인 정규 핵(normal core, $C = \text{core}_G(S)$)을 복구한다.
• 메커니즘: 군의 기약 표현(irrep) 라벨을 측정함으로써, 알고리즘은 $C \subseteq A$를 만족하는 부분군 $A$를 출력한다. 알고즘은 $A$가 $C$를 엄격하게 포함하는 최소 부분군을 포함하지 않을 때 성공한다.
• 복잡도 개선: 샘플 복잡도는 $|G|$가 아니라 $M$($C$를 엄격하게 포함하는 최소 부분군들의 집합)의 $\log |M|$에 의존한다. 이는 $|M| \ll |G|$인 경우 엄격한 개선을 제공한다.
• 응용: 이를 통해 "다항 근사 해밀토니안(polynomially near-Hamiltonian)" 군(Baer norm의 지수가 polylogarithmic인 군)에 대한 효율적인 학습이 가능해진다.

B. 애니온 대칭성을 위한 푸리에 차이 샘플링 (Fourier Difference Sampling)

애니온 대칭성 학습(위상까지 고려한 불변성)을 다루기 위해, 저자들은 보존 대칭성 학습으로의 환원을 도입한다.

• 아벨 사례: 만약 상태 $\rho$가 $R(g)$에 대해 애니온 대칭성을 가진다면, $\rho^{\otimes 2}$는 $R(g) \otimes R(g^{-1})$에 대해 보존 대칭성을 가진다는 점에 주목한다.
• 새로운 원시 연산: 두 번의 푸리에 샘플링을 수행하고 그 결과를 빼는 푸리에 차이 샘플링을 도입한다. 이는 상태의 추가 복사본을 상수 개만큼만 사용하여 $R \otimes R^{-1}$로부터 샘플링하는 효과를 낸다.
• 비가환 확장: 비가환 군의 경우 $R \otimes R^{-1}$가 반드시 선형 표현인 것은 아니다. 저자들은 $R'(g, k) = \omega^{-k}R(g)$로 정의된 선형 표현을 사용하여 문제를 더 큰 군 $G \times \mathbb{Z}_E$ ($E$는 $G$의 지수)로 임베딩한다. 이를 통해 애니온 대칭성을 확장된 군 위의 엄격한 보존 대칭성으로 변환한다.

C. 코딩 이론을 통한 투영 표현의 선형화

가장 중요한 기술적 기여는 투영 표현(예: Pauli 연산자)의 투영 애니온 대칭성 학습을 다루는 것이다. 표준적인 중심 확장(central extension)을 통한 선형화는 종종 학습하기 어려운 비가환 군을 생성한다.

• 새로운 구성: 저자들은 유한 아벨 군 $G$의 투영 표현을 비가환 중심 확장을 거치지 않고 직접 선형화하는 방법을 구축한다.
• 코딩 이론과의 대응: 선형화와 $\mathbb{Z}_E$ 상의 선형 오류 정정 코드 사이의 대응 관계를 확립한다.
  • 선형화는 입력 그룹 요소들의 선형 결합(생성 행렬 $M$에 의해 결정됨)을 사용하여 텐서 곱 상태에 구성 성분별로 투영 표현을 적용함으로써 구축된다.
  • 결과적인 맵이 유효한 선형 표현이 되기 위해서는 행렬 $M$이 특정 직교 조건(행들이 modulo $E$에 대해 서로 직교해야 함)을 만족해야 한다.
  • 선형화가 대칭 구조를 보존하도록(은닉 부분군 복구를 허용하도록) 하기 위해, 코드는 **자기 직교(self-orthogonal)**여야 한다. 만약 코드가 또한 제로-섬(zero-sum) 성질을 가진다면, 차이 샘플링 대신 표준 푸리에 샘플링을 사용하여 선형화를 사용할 수 있다.
• 최적화: 저자들은 블록 길이(샘플당 필요한 상태 복사본 수)와 코드율(복사본당 얻는 샘플 수) 사이의 트레이드오프를 최적화한다. 이들은 최소한의 블록 길이로 최적의 샘플링 비율을 달_성하기 위해 확장 이진 해밍 코드($E=2$) 및 테르너리 골레이 코드($E=3$)와 같은 코드를 사용하는 명시적 구성을 제공한다.

3. 주요 결과 및 기여

1. 비가환 StateHSP:

   • QFT(양자 푸러리어 변환)가 효율적인 모든 유한 군에 대해 보존 대칭성 부분군의 정규 핵을 찾기 위한 효율적인 양자 알고리즘.
   • 다항 근사 해밀토니안 군에 대한 보존 대칭성 학습을 위한 효율적인 알고리즘.
   • **은닉 평행 이동 문제(Hidden Translation Problem)**에 대한 샘플 복잡도를 최악의 경우 $O(\log N)$에서 $O(\log N / \log \log N)$ 복사본으로 개선.

2. 애니온 대칭성 학습:

   • 다항 근사 아벨 군(선형 표현)에 대한 애니온 대칭성 학습을 위한 효율적인 알고리즘.
   • 임의의 유한 아벨 군에 대한 투영 애니온 대칭성 학습에 대한 효율적인 알고리즘. 이는 임의의 로컬 차원을 가진 혼합 큐디트(qudit) 상태의 스태빌라이저 군을 학습하는 첫 번째 명시적 알고리즘이다.
   • 혼합 상태 스태빌라이저 학습을 위한 알고리즘은 $O(n)$개의 복사본을 사용하며 다항 시간 내에 실행되며, 순수 상태에 대한 이전 결과와 일치하거나 이를 개선한다.

3. 기타 양자 객체의 대칭성:

   • 유니터리: Choi 상태와 표현 $R \otimes R$을 통해 유니터리 대칭성 학습을 보존 대칭성 학습으로 환원.
   • 해밀토니안: 시간 진화 연산자를 통해 해밀토니안 대칭성 학습을 유니터리 대칭성 학습으로(그리고 다시 보존 대칭성 학습으로) 환원.
   • 상태 집합: $G \times S_m$ 상의 보존 대칭성 학습으로 부분 집합 대칭성 학습을 환원. $|A|$가 작고 $G$가 다항 근사 아벨인 경우 효율적인 알고리즘이 제공된다.
   • 부공간(Subspaces): 부공간 대칭성과 혼합 상태의 공액 대칭성(Conjugate Symmetry) 간의 연결 고리를 확립.

4. 의의 및 주장

본 논문은 양자 대칭성 학습의 범위를 실질적으로 넓혀, 상태 대칭성 학습을 다양한 양자 대칭성 문제에 대한 공통적인 알고리즘 프리미티브로 확립한다고 주장한다.

• 격차 해소: 본 연구는 대칭성 테스트(광범위한 군과 객체에 대해 효율적인 것으로 알려짐)와 대칭성 학습(이전에는 아벨 군과 선형 표현에 국한되었던 것) 사이의 격차를 메운다.
• 물리적 관련성: 애니온 대칭성을 도입하고 투영 표현을 다룸으로써, 전역 위상은 관측 불가능하며 투영 표현(Pauli 군과 같은)이 근본적이라는 물리적 실재와 더 밀접하게 일치시킨다.
• 코딩 이론과의 연결: 투영 표현의 선형화와 선형 오류 정정 코드 사이의 대응 관계 발견은 (Bell 샘플링의 일반화와 같은) 대칭성 학습 너머의 잠재적 응용을 가진 새로운 이론적 통찰로 제시된다.
• 실질적 영향: 본 결과는 임의의 혼합 상태의 스태빌라이저 군을 학습하는 최초의 증명 가능한 정확하고 효율적인 양자 알고리즘을 제공하며, 이는 일반적인 경우에 해결되지 않았던 과제였다.

저자들은 비가환 사례에 대해 겸허한 입장을 유지하며, 비록 해결 가능한 군의 범위를 (근사 해밀토니안 및 근사 아벨까지) 확장했으나, 일반적인 비가환 HSP는 여전히 어렵다는 점을 인정한다. 따라서 일반적인 효율적 비가환 투영 대칭성 학습 알고리즘은 도달하기 어려울 수 있다. 그러나 그들은 자신들의 프레임워크가 더 좁은 시각의 HSP가 놓쳤을 수 있는 비가환 사례에 대한 새로운 통찰을 제공한다고 주장한다.