기술 요약: 큐디트(Qudit)에서의 벨 샘플링(Bell Sampling) 재정복

1. 문제 정의

벨 샘플링은 양자 정보 이론, 특히 스테빌라이저 상태(stabilizer states)를 분석하고 "매직(magic)"(비-스테빌라이저 자원)을 측정하는 데 있어 근본적인 프리미티브(primitive)입니다. 큐비트($d=2$)의 경우, 벨 샘플링(두 개의 상태를 벨 기저에서 측정하는 것)과 그 변형인 벨 차이 샘플링(Bell difference sampling)은 미지의 스테빌라이저 상태를 효율적으로 학습하고, 스테빌라이저 성질을 테스트하며, 의사 난수 상태(pseudorandom states)와 하르 무작위(Haar-random) 상태를 구별할 수 있게 해줍니다.

그러나 이를 큐디트(차원이 $d \geq 2$인 시스템)로 일반화하는 것은 매우 어려운 과제였습니다. 저자들의 이전 연구(arXiv'24)는 임의의 차원으로 벨 샘플링을 확장하려는 "자연스러운" 시도가 실패함을 보여주었습니다. 즉, 두 개의 스테빌라이저 상태를 일반화된 벨 기저에서 측정하면 완전히 무작위한 출력을 생성하여, 기저에 깔린 스테빌라이저 그룹에 대한 어떠한 정보도 제공하지 못한다는 것입니다. 이러한 실패는 전치 사상(transpose map, 복소 공액)이 완전 긍정(completely positive)이 아니며, $d > 2$인 경우 스테빌라이저 상태 $|S\rangle$와 그 복소 공액 $|S^*\rangle$가 큐비트의 경우($|S^*\rangle = W_z |S\rangle$)와 달리 단순한 파울리 연산자로 관계지어지지 않기 때문에 발생합니다.

이 논문에서 다루는 핵심 문제는, 큐비트 사례의 강력한 특성, 특히 스테빌라이저 그룹의 생성원(generators)을 샘플링할 수 있는 능력을 유지하면서 모든 차원 $d \geq 2$의 큐디트에 적용 가능한 유용한 벨 샘플링의 일반화를 개발하는 것입니다.

2. 방법론 및 핵심 프리미티브

저자들은 "자연스러운" 확장의 한계를 극러내기 위해 새로운 서브루틴인 **왜곡된 벨 차이 샘플링(Skewed Bell Difference Sampling)**을 제안합니다. 핵심 혁신은 **라그랑주의 네 제곱 합 정리(Lagrange's four-square theorem)**에 기반한 특정 유니터리 변환입니다.

$B_R$ 유니터리

이 방법은 네 개의 스테빌라이저 상태 $|S\rangle^{\otimes 4}$에 작용하는 유니터리 연산자 $B_R$에 의존합니다. 이 유니터리는 $a_1^2 + a_2^2 + a_3^2 + a_4^2 = d-1$을 만족하는 비음의 정수 $a_1, a_2, a_3, a_4$로부터 구성된 행렬 $R \in \mathbb{Z}_d^{4 \times 4}$에 의해 정의됩니다.
행렬 $R$은 $R J R = -I \pmod d$ (여기서 $J$는 심플렉틱 모듈 상의 인볼루션 맵)를 만족하도록 구성됩니다.

핵심 속성: 모든 스테빌라이저 상태 $|S\rangle$에 대하여, 유니터리 $B_R$은 네 개의 복사본을 (파울리 연산자 차이 내에서) 그들의 복소 공액으로 변환합니다:
$$B_R |S\rangle^{\otimes 4} = P(S) |S^*\rangle^{\otimes 4}$$
여기서 $P(S)$는 $|S\rangle$에 의존하는 파울리 연산자입니다. 이 변환은 상태들을 혼합하여 스테빌라이저 그룹을 그 복소 공액과 정렬시키며, 이는 성공적인 샘플링을 위한 필수 조건입니다.

참고: 특정 차원(예: $-1$이 이차 잔여인 소수 차원$d$)의 경우, 4개보다 적은 수의 복사본(예: 2개 또는$d \equiv 1 \pmod 4$인 경우 1개)만으로도 충분할 수 있습니다.

샘플링 절차

전체 왜곡된 벨 차이 샘플링 알고리즘은 다음과 같이 진행됩니다:

1. 상태 $|\psi\rangle$의 8개 복사본을 준비합니다.
2. 4개의 복사본에 유니터리 $B_R$을 적용하여 이들을 $|S^*\rangle^{\otimes 4}$(파울리 차이 내에서)로 변환합니다.
3. 변환된 복사본들을 원래의 4개 복사본과 쌍을 이룹니다.
4. 각 쌍 $(|S\rangle, |S^*\rangle)$에 대해 표준 벨 샘플링을 수행합니다.
5. 결과값들 사이의 차이를 계산합니다.

결과 분포 $\hat{p}_\psi$는 부호 없는 스테빌라이저 그룹 $Weyl(|\psi\rangle)$의 직교 보충(orthogonal complement) 위에 지지(support)된다는 것이 입증되었습니다. 만약 $|\psi\rangle$가 스테빌라이저 상태라면, 샘플들은 스테빌라이저 그룹 자체 위에서 균일하게 분포합니다.

3. 주요 기여 및 결과

이 논문은 이 새로운 프리미티브가 큐비트 기반의 여러 주요 결과들을 모든 차원 $d \geq 2$의 큐디트로 끌어올릴 수 있음을 보여줍니다.

A. 스테빌라이저 상태 학습 및 숨겨진 스테빌라이저 그룹 문제

• 문제: 미지의 스테불라이저 상태 $|S\rangle$ 또는 숨겨진 스테빌라이저 그룹 $Weyl(|\psi\rangle)$를 상태의 복사본들을 통해 식별하는 것.
• 결과: 저자들은 높은 확률로 스테빌라이저 그룹을 식별하는 양자 알고리즘을 제시하며, 이는 $O(n)$개의 샘플과 $O(n^3)$의 시간을 소요합니다.
• 개선점: 이는 $O(n \log d \max\{d, \epsilon^{-1}\})$개의 샘플을 요구했던 Hinsche, Eisert, และ Carrasco [HEC26]의 최근 푸리에 샘플링 방식보다 개선된 것입니다. 새로운 방법은 한 번에 최대 8개의 복사본(소수 차원의 경우 4개)에 작용하며, 이는 $D$개의 복사본(여기서 $D$는 $2d$가 될 수 있음)이 필요했던 이전 방식보다 실질적으로 더 실행 가능합니다.

B. 스테빌라이저 크기 속성 테스트 (Property Testing)

• 문제: 상태가 $d^t$ 이상의 스테빌라이저 크기(부호 없는 스테빌라이저 그룹의 카디널리티)를 갖는지, 아니면 그러한 상태로부터 $\epsilon$-멀리 떨어져 있는지 테스트하는 것.
• 결과: 알고리즘은 $O(n/\epsilon)$개의 샘플을 사용하여 $O(n^3/\epsilon)$ 시간 내에 이 두 경우를 구별합니다.
• 의의: 이는 Grewal 등의 큐비트 결과 [GIKL25]를 임의의 차원으로 일반화한 것입니다. 이 분석은 벡터 공간이 아닌 링 $\mathbb{Z}_d$ 상의 부분 모듈(submodule)을 다루므로, 샘플의 스팬(span)을 분석하기 위해 스미스 정규형(Smith normal forms)을 사용해야 합니다.

C. 도핑된 클리포드 회로 및 의사 난수성 테스트

• 문제: 하르 무작위 상태와 $t$-도핑된 클리포드 회로(클리포드 회로에 $t$개의 비-클리포드 게이트가 추가된 것)를 구별하는 것.
• 결과: 저자들은 $t < n/2$인 임의의 $t$-도핑된 클리포드 회로가 의사 난수 상태를 생성할 수 없음을 증명합니다.
• 개선점: 이는 큐디트에서 의사 난수성을 위해 필요한 비-클리포드 게이트의 하한선이 $n/2$임을 확립합니다. 이는 기존의 큐디트 관련 경계($O(\log_d n)$)에 비해 지수적인 개선이며, 큐비트의 최적 경계와 일치합니다. 알고리즘은 $O(n)$개의 샘플을 사용하여 $O(n^3)$ 시간 내에 두 경우를 구별합니다.

D. 내성적 스테빌라이저 테스트 (Tolerant Stabilizer Testing)

• 문제: 상태가 최소 $1-\epsilon_1$의 스테빌라이저 충실도(fidelity)를 갖는지, 혹은 최대 $1-\epsilon_2$를 갖는지 결정하는 것 ($\epsilon_1 < \epsilon_2$).
• 결과: 논문은 두 가지 알고리즘을 제안합니다:
  1. POVM 기반: 특정 POVM $\Pi_r^+$를 사용하는 Gross-Nezami-Walter (GNW) 프로토콜의 확장.
  2. 벨 샘플링 기반: 왜곡된 벨 차이 샘플링 후 특정 측정을 사용하는 프로토콜.
• 복잡도: 두 알고리즘 모두 대략 $O(d^2 \epsilon_2 / (\epsilon_2 - \epsilon_1)^2)$의 샘플 복잡도를 달성합니다. 벨 샘플링 방식은 많은 수의 복사본이 필요한 POVM 방식(여기서 $r$은 매우 클 수 있음)에 비해 더 적은 수의 복사본(8개)을 요구하지만, POVM 방식이 특정 차원에서 더 넓은 범위의 유효한 파라미터를 제공할 수도 있습니다.

4. 의의 및 주장

이 논문은 큐디트에서도 유용성을 유지하면서 큐비트 사례를 효과적으로 계승하는 비자명하면서도 단순한 일반화 방법을 제공함으로써, 큐디트에서의 벨 샘플링을 "재정복"했다고 주장합니다.

• 이론적 돌파구: 라그랑주의 네 제곱 합 정리에 기반한 유니터리 $B_R$의 구축은, 고차원에서 스테빌라이저 상태를 그 복소 공의로 매핑하는 근본적인 장애물을 해결하는 독립적인 관심사를 가진 프리미티브로 제시됩니다.
• 통합: 이 연구는 $d \geq 2$인 모든 차원에 걸쳐 스테빌라이저 상태 이론을 통합하며, 기존 연구들의 소수 차원 제한을 넘어섭니다.
• 효율성: 알고리즘은 $\mathbb{Z}_d$ 상의 모듈을 다루는 데 따른 대수적 복잡성 증가에도 불구하고, 큐비트 사례와 유사한 다항 시간 및 샘플 복잡도($O(n^3)$ 및 $O(n)$)를 유지합니다.
• 의사 난수성 경계: $n/2$개의 비-클리포드 게이트가 큐디트의 의사 난수성을 위해 필요하다는 결과는 기존의 경계를 크게 좁힌 중요한 성과이며, 큐비트와 큐디트 이론 사이의 간극을 메우는 작업입니다.

저자들은 자신들의 결과가 새로운 샘플링 분포 $\hat{p}_\psi$의 성질로부터 엄격하게 도출되었으며, 증명되지 않은 추측에 의존하지 않는다는 점을 강조합니다. 또한, 내성적 테스트를 위한 샘플 복잡도가 최적의 큐비트 결과보다 $d^2$ 배만큼 약간 더 높을 수 있지만, 이는 일반적인 큐디트에 대한 최초의 성공적인 내성적 테스트 프로토콜 확장임을 명시하고 있습니다.