Improved bounds on stabilizer extent and Clifford rank

기술 요약: 스테빌라이저 범위(Stabilizer Extent) 및 클리포드 랭크(Clifford Rank)에 대한 개선된 경계

문제 정의
본 논문은 양자 상태(또는 연산자)의 *스테빌라이저 랭크(stabilizer rank)*와 스테빌라이저 범위(stabilizer extent 또는 Clifford coefficient norm) 사이의 정량적 관계를 다룬다. 스테빌라이저 랭크 $\chi(|\psi\rangle)$는 상태 $|\psi\rangle$를 정확하게 분해하는 데 필요한 최소 스테빌라이저 상태의 수를 측정한다. 스테빌라이저 범위 $\xi(|\psi\rangle)$는 그러한 분해에서의 계수 제곱 합의 최솟값을 측정한다.

Gottesman-Knill 정리는 스테빌라이저 상태에 대한 클리포드 회로가 클래식하게 시뮬레이션 가능하다는 것을 확립했지만, 일반적인 양자 계산에는 "매직(magic)" 자원이 필요하다. 시뮬레이션 알고리ست들은 비-스테빌라이저 상태를 스테빌라이저 상태로 분해하는 데 의존한다. 이러한 알고리즘의 효율성은 스테빌라이저 범위에 달려 있는데, 이는 작은 계수가 희소화(sparsification)를 용이하게 하기 때문이다. 그러나 낮은 스테빌라이저 랭크를 가진 상태라 할지라도, 분해 과정에서 큰 계수들이 서로 상쇄될 수 있기 때문에 이론적으로는 큰 범위를 가질 수 있다.

핵심 문제는 스테빌라이저 랭크에 대한 경계가 스테빌라이저 범위를 얼마나 강력하게 제약하는가이다. 본 논문은 스테빌라이저 랭크가 $k$인 상태는 반드시 스테빌라이저 충실도(최근접 스테빌라이저 상태와의 중첩)가 $2^{-k/C}$로 하한이 정해져 있다는 Mehraban–Tahmasbi [MT25]의 정량적 추측을 조사한다. 이전 연구인 Kalra–Sinha [KS26]는 랭크-$k$ 상태에 대해 $\xi(|\psi\rangle) \le 2^{O(k \log k)}$라는 범위의 상한을 확립했다. 저자들은 이 상한을 개선하고 랭크에 따른 충실도의 스케일링에 관한 추측을 해결하고자 한다.

방법론
저자들은 **스테빌라이저 코드 공간으로의 무작위 투영(randomized projections onto stabilizer codespaces)**과 **코드 중첩에 기반한 클러스터링 논증(clustering argument)**을 결합한 새로운 접근 방식을 사용한다.

1. 코드 병합을 통한 클러스터링: 저자들은 상태 $|\psi\rangle$를 $k$개의 스테빌라이저 상태로 분해하는 것부터 시작한다. 이들은 "클러스터"를 공통된 스테빌라이저 코드 공간 내에 포함된 이 상태들의 부분 집합으로 정의한다. 보조정리(Lemma) 3.2를 사용하여, 두 코드 공간의 중첩(투영 연산자의 연산자 노름으로 측정됨)이 크다면, 이들을 더 큰 차원의 코드 공간으로 병합할 수 있음을 보여준다.
2. 이분법(Dichotomy): 클러스터링 과정은 이분법(보조정리 3.3)으로 이어진다. 즉, 저차원 코드 공간이 원래의 스테빌라이저 항들을 상당수 포함하거나, 아니면 항들이 거의 직교하는 클러스터들로 나뉜다.
   • 사례 1 (저차원 포함): 차원이 $d$인 코드 공간이 $r$개의 항을 포함하는 경우, 저자들은 차원 $d$인 임의의 스테빌라이저 코드에 속한 상태는 계수의 합이 $\sqrt{d}$로 제한되는 분해를 가진다는 사실을 이용한다.
   • 사례 2 (근사 직교성): 클러스터들이 거의 직교하는 경우, 이들 사이의 상쇄는 제한적이다. 저자들은 각 클러스터의 기여도를 합산함으로써 범위를 제한할 수 있다.
3. 무작위 투영을 통한 블록 제거: 클러스터 내의 항들을 처리하기 위해, 저자들은 무작위 파울리 투영을 활용한다. 코드 제약 조건을 만족하는 무작위 파울리 연산자의 고유 공간으로 투영함으로써, 나머지 항들의 스테빌라이저 성질을 (스칼라 값까지는) 유지하면서 $r$개의 스테빌라이저 항 블록을 제거할 수 있다. 이를 통해 문제의 크기를 귀납적으로 줄일 수 있다.
4. 클리포드 연산자로의 확장: 연산자의 경우, 정규화된 Choi 맵을 사용하여 이 프레임워크를 적응시킨다. 저자들은 엔탱글먼트 결핍(entanglement deficit)(최대 엔탱글먼트에서 부족한 ebit의 수)이라는 개념을 도입한다. 파울리 투영이 이 결핍에 미치는 영향(최대 1만큼 증가)을 추적하여, 중간 상태를 클리포드 유니터리에 대응하는 최대 엔탱글먼트 스테빌라이저 상태로 분해하는 비용을 제어한다.

주요 기여 및 결과

1. 개선된 스테빌라이저 랭크–범위 경계 (정리 1.1):
   저자들은 $n$-큐비트 벡터 $|v\rangle$에 대해 $\chi(|v\rangle) \le k$인 경우, 스테빌라이저 범위가 다음과 같이 제한됨을 증명한다:
   $$\xi(|v\rangle) \le 2^{O(\sqrt{k} \log(k+1))} \|v\|^2$$
   이는 Kalra–Sima [KS26]의 $2^{O(k \log k)}$ 경계보다 지수 부분에서 제곱근 인자만큼 개선된 것이다.

2. 정량적 추측의 해결:
   새로운 경계는 스테빌라이저 충실도 하한 $FS(|\psi\rangle) \ge 2^{-O(\sqrt{k} \log(k+1))}$를 함의한다. 이는 [MT25]의 정량적 추측($2^{-k/C}$를 제안함)을 해결하며, 지수 부분에서 제곱근 인자만큼 스케일링을 개선한다.

3. 클리포드 랭크–계수 노름 경계 (정리 1.2):
   연산자에 대해서도 유사한 경계가 설정된다. 클리포드 랭크 $\chi_C(A) \le k$인 연산자 $A$에 대해, 제곱 클리포드 계수 노름은 다음과 같다:
   $$\Lambda_C(A)^2 \le 2^{O(\sqrt{k} \log(k+1))} 2^{-n} \|A\|_F^2$$

4. 근사 스테빌라이저 랭크에 대한 하한:
   이 경계들을 비-스테빌라이저 상태의 텐서 거듭제곱에 적용함으로써 근사 스테빌라이저 랭크에 대한 하한을 도출한다. 고정된 비-스테빌라이저 큐비트 상태 $|\phi\rangle$에 대해, $|\phi\rangle^{\otimes n}$의 근사 스테빌라이저 랭크는 다음과 같다:
   $$\chi_\delta(|\phi\rangle^{\otimes n}) = \Omega_\phi(n^2 / \log n)$$
   이는 [MT24]의 $T$-상태에 대한 기존 최적 하한을 임의의 비-스테빌라이저 큐비트 상태로 일반화한 것이다.

5. 불리언 함수의 클래식 표현:
   클리포드 랭크 경계는 이차 위상(quadratic phases)을 사용하는 $n$-비트 AND 함수의 정확한 표현에 대한 하한을 함의한다. 필요한 이차 위상의 수 $Q(n)$은 다음과 같다:
   $$Q(n) = \Omega(n^2 / \log n)$$
   이는 기존의 선형 하한을 개선한 것이다.

6. 의사 난수성(Pseudorandomness) 및 학습:

   • 의사 난수성: 이 결과들은 근사 스테빌라이저/클리포드 랭크가 $O((\log n)^2 / \log \log n)$인 의사 난수 상태 및 유니터리 앙상블의 존재 가능성을 배제하며, 이는 [KS26]의 $O(\log n / \log \log n)$ 임계값을 개선한 것이다.
   • 토모그래피: 저자들은 스테빌라이저 랭크가 최대 $k$인 상태에 대해 시간 및 복사 복잡도가 $\text{poly}(n) 2^{O(\sqrt{k} \log k)}$인 토모그래피 알고리즘을 도출한다. 이는 [KS26]에 기반한 최적 알고리즘에 비해 지수 부분에서 거의 제곱근 수준의 개선을 나타낸다.

의의 및 주장
본 논문은 도출된 경계가 양자 상태/연산자의 구조적 복잡성(랭크)과 그 계수 노름(범위) 사이의 더 강력한 연결을 제공한다고 주장한다. 범위를 좁힘으로써, 저자들은 낮은 스테빌라이저 랭크를 가진 상태가 스테빌라이저 상태와 임의로 작은 중첩을 가질 수 없음을 입증하며, 이를 통해 복잡성을 숨길 수 있는 "상쇄" 효과를 제한한다.

본 연구의 의의는 다음과 같다:

• 이론적 해결: 정량적 추측 [MT25]를 더 타이트한 경계로 해결함.
• 일반화: 매직 상태의 텐서 거듭제곱에 대한 하한을 특정 상태(예: $|T\rangle$)에서 모든 비-스테빌라이저 큐비트 상태로 확장함.
• 알고리즘적 개선: 저 랭크 상태 및 유니터리의 학습 및 토모그래피 복잡도에서 지수 부분을 거의 제곱근 수준으로 개선함.
• 클래식 복잡도: AND 함수의 이차 위상 랭크에 대해 거의 이차식에 가까운 하한을 설정하여 클래식 표현 이론의 최신 성과를 개선함.

저자들은 자신들의 경계 $2^{O(\sqrt{k} \log k)}$가 $2^{O(k)}$를 달성하는 동시 진행 연구 [Dut26]보다 강력하지만, 지수가 $O(\sqrt{k})$로 줄어들 수 있는지, 혹은 범위가 랭크에 대해 다항식적으로 유계되는지는 아직 알려지지 않았다고 언급한다. 이들은 현재 경계의 로그 손실이 코드 공간 병합에 따른 차원 비용에서 기인하며, 더 강력한 클러스터링 경계를 사용한다면 이 요인을 제거할 수 있을 것이라고 제안한다.