Sample-optimal learning of stabilizer states

기술 요약: 안정자 상태(Stabilizer States)의 샘플 최적 학습

문제 정의
본 논문은 미지의 순수 $n$-큐비트 안정자 상태 $|\psi\rangle$를 학습하는 근본적인 문제를 다룬다. 이러한 상태를 학습하는 데에는 $n$에 선형적인 수의 복사본(copies), 즉 $O(n)$이 필요하다는 것은 이미 확립되어 있으나, 이 스케일링의 정확한 상수 계수는 결정되지 않은 채 남아 있었다. Aaronson과 Gottesman, 또는 Montanaro의 알고리즘과 같은 기존 방식들은 선형 스케일링을 달성했으나 더 큰 상수 계수(예: $3n$ 또는 $2n$ 개의 복사본과 로그 항 필요)를 요구했다. 핵심 질문은 실패 확률 $\delta$ 내에서 임의의 안정자 상태를 식별하기 위해 필요한 최소 복사본 수 $L_\delta(n)$은 정확히 얼마인가 하는 것이다.

방법론
저자들은 이전의 벨 샘플링(Bell sampling)이나 숨겨진 부분군(hidden subgroup) 방법과는 구별되는 새로운 접근 방식을 사용하여, 상한(upper bound)과 하한(lower bound) 모두에 대한 구성적 증명을 제시한다.

1. 상한 알고리즘 (Upper Bound Algorithm):
   제시된 알고리즘은 네 가지 주요 단계로 진행된다:

• 전체 지지 집합(Full-Support)으로의 축소: 알고리즘은 먼저 일반적인 학습 문제를 "풀 랭크(full-rank)" 안정자 상태를 학습하는 문제로 축소한다. $t$개의 상태 복사본 텐서 곱에 무작위 클리포드 유니터리 $C$를 적용함으로써, 알고즘은 상태를 계산 기저(computational basis) 전체에 걸쳐 전체 지지 집합을 갖는 상태로 확률적으로 매핑한다. 가역적 테스트를 통해 기저 문자열의 아핀 랭크(affine rank)가 $n$인지 확인하며, 그렇지 않을 경우 새로운 무작위 클리포드를 사용하여 과정을 반복한다.
• 동종 압축 (Isotypic Compression): 일단 풀 랭크 상태 $|\phi_{\alpha, \beta}\rangle$를 얻으면, 이를 아벨 군 $\Upsilon \cong \mathbb{Z}_4^n \times \mathbb{F}_2^{n(n-1)/2}$의 궤도(orbit)로 표현한다. 알고즘은 해밍 무게(Hamming weights)와 내적을 기반으로 한 "특성(character)" $h(x)$를 계산한다. 그 후, 각 동종 성분(동일한 $h$를 공유하는 상태들)을 단일 기저 상태로 매핑하여 상태를 일관되게 압축하며, 이는 실질적으로 시스템을 $\Upsilon$의 군 대수(group algebra)로 축소시킨다.
• 푸리에 변환 (Fourier Transform): $\Upsilon$ 위의 역 양자 푸리에 변환(Inverse QFT)이 수행된다. 이 단계는 상태의 이차 위상(quadratic phase)을 정의하는 파라미터 $(\alpha, \beta)$를 추출한다.
• 타블로 재구성 (Tableau Reconstruction): 회복된 파라미터 $(\alpha, \beta)$와 알려진 무작위 클리포드 $C$를 사용하여, 원래 상태의 안정자 타블로(stabilizer tableau)를 클래식하게 재구성한다.

2. 하한 증명 (Lower Bound Proof):
   하한을 설정하기 위해, 저자들은 학습 문제를 전체 지지 이차 위상 상태의 부분 집합으로 제한한다. 이들은 "프리티 굿 측정(pretty good measurements)" 이론을 활용하고, $t$개 복사본의 측정 결과 분포와 균등 분포 사이의 헬링거 중첩(Hellinger overlap)을 분석한다. 쌍대 군(dual group) $\hat{\Upsilon}$ 상의 특정 실수 함수를 구성함으로써, $t < n + \log_2(1/\delta) - O(1)$일 때 분포들이 구별 가능함을 입증하고, 이는 학습 성공 확률이 1에서 멀어짐을 의미한다.

주요 결과
본 논문은 임의의 $n$-큐비트 안정자 상태를 실패 확률 $\delta$ ($0 < \delta < 1/8$) 내에서 식별하는 데 필요한 최소 복사본 수 $L_\delta(n)$에 대한 타이트한 경계(tight bounds)를 확립한다:

$$n + \lceil \log_2(1/\delta) \rceil - 3 \leq L_\delta(n) \leq n + \lceil \log_2(1/\delta) \rceil + 4$$

• 선도 계수의 최적성 (Optimality of the Leading Coefficient): 결과적으로 샘플 복잡도의 최적 선도 계수가 정확히 1임을 증명한다. 이 알고리즘은 기존 방법(예: $\approx 3n$ 요구)에 비해 상수 차원의 개선을 달성하여 ($\approx n$으로 감소) 성능을 높였다.
• 알고리즘 효율성: 상한은 실행 시간 $O(n(n + \log(1/\delta))^4)$를 갖는 다항 시간 양자 알고리즘에 의해 달성된다.
• 클리포드 유니터리 학습: 초이-자미올코프스키 동형 사상(Choi-Jamiolkowski isomorphism)을 통한 결과로서, 저자들은 $2n + \lceil \log_2(1/\delta) \rceil + 4$ 번의 순방향 쿼리를 사용하여 미지의 $n$-큐비트 클리포드 유니터리를 학습하는 알고리즘을 도출한다. 이 결과의 $n$-의존성이 최적임을 입증한다.

의의 및 주장
저자들은 본 연구가 안정자 상태 학습의 정확한 샘플 복잡도를 해결했다고 주장하며, 이는 양자 학습 이론의 오랜 미결 과제였다. 이 연구의 의의는 다음과 같다:

1. 정확한 특성화: 샘플 복잡도가 $n + O(\log(1/\delta))$이며 선도 계수가 1임을 결정하였는데, 이는 정보 이론적으로 최적이다.
2. 새로운 기법: 아벨 군 $\mathbb{Z}_4^n \times \mathbb{F}_2^{n(n-1)/2}$ 상의 푸리에 분석을 포함하는 증명 기법은 이전의 접근 방식과는 질적으로 다르며, 다른 양자 학습 문제로의 자연스러운 일반화를 허용한다.
3. 자원 효율성: 제안된 알고리즘은 동일한 신뢰 수준을 달립하기 위해 더 적은 상태 복사본을 요구함으로써, Montanaro의 벨 샘플링과 같은 기존 방식보다 샘플 복잡도 측면에서 상수 배의 개선을 이룬다.

본 논문은 알고리즘이 모든 입력 복사본에 대한 일관된 집합적 측정(coherent collective measurements)에 의존한다는 점을 한계로 언급한다. 동일한 최적 샘플 복잡도를 한 번에 고정된 수의 복사본만을 측정하는 방식으로 제한된 상황에서도 달성할 수 있는지는 여전히 열린 문제이다. 또한, 클리포드 유니터리 학습에 대한 $n$-의존성은 최적이지만, 특정 $\delta$ 영역에 대한 $\delta$-의존성은 잠재적으로 개선될 여지가 있다.