기술 요약: 적응성이 전부다: 단일 복사본 측정만을 이용한 최적의 안정자 학습

1. 문제 정의

안정자 상태(Stabilizer states)는 양자 오류 정정, 결함 허용 컴퓨팅 및 효율적인 고전적 시뮬레이션의 기초가 된다. 핵심적인 운영상의 질문은 미지의 $n$-큐비트 안정자 상태를 실험 데이터로부터 얼마나 효율적으로 식별할 수 있는가이다.

이전 연구들은 측정 전략에 따라 샘플 복잡도(sample complexity)에서 상당한 격차가 있음을 밝혀냈다:

• 2-복사본 벨 샘플링(Two-copy Bell sampling): Montanaro [9]는 두 복사본에 대한 합동 벨 측정(joint Bell measurements)을 사용하여 안정자 상태를 학습하는 데 $\Theta(n)$개의 복사본이 충분함을 보여주었다. 이는 정보 이론적으로 최적이다.
• 비적응형 단일 복사본 측정(Non-adaptive single-copy measurements): 문헌 [10]은 측정이 단일 복사본으로 제한되고 비적응적(이전 결과와 독립적)이어야 하는 경우, 샘플 복잡도가 $\Omega(n^2)$로 급증한다는 것을 입증했다.

본 연구에서 다루는 열린 문제는 적응형 단일 복사본 측정(이전 결과에 따라 현재 측정 기저를 선택하는 방식)이 여러 복사본에 대한 결맞은 접근(coherent access)을 요구하지 않고도, 이 이차적 격차를 좁혀 최적의 $\Theta(n)$ 스케일링을 달-성할 수 있는지 여부이다.

2. 방법론

핵심 알고리즘: 적응형 안정자 학습

저자들은 오직 $\Theta(n)$개의 단일 복사본 적응형 측정을 사용하여 임의의 $n$-큐비트 안정자 상태를 학습하는 다항 시간 알고리즘(알고리즘 1)을 제안한다. 이 알고리즘은 미지의 상태를 계산 기저 상태(computational-basis state)로 점진적으로 변환하는 고전적 피드백에 의존한다.

핵-심 메커니즘:

1. 초기화: 항등 클리포드 회로 $C = I$로 시작한다. 목표는 $C|\psi\rangle = |z\rangle$를 만족하는 클리포드 $C$를 찾는 것이다 (여기서 $|z\rangle$는 계산 기저 상태이다).
2. 반복 라운드: 각 라운드에서, 알고리즘은 현재 변환된 상태 $C|\psi\rangle$의 두 개의 독립적인 복사본을 계산 기저에서 측정하여 결과 $x$와 $y$를 얻는다.
3. 차이 샘플링(Difference Sampling): 비트 단위 차이 $u = x + y$를 계산한다. 안정자 상태의 경우, 만약 $u \neq 0$이라면, 이 벡터는 계산 기저에서 대각 성분이 아닌 안정자 생성자의 $X$-부분을 식별한다.
4. 적응형 업데이트:
   • 알고리즘은 $u_i = 1$인 피벗 인덱스 $i$를 식별한다.
   • 알고리즘은 식별된 안정자를 형태 $(e_i, v')$로 매핑하는 CNOT 기반 클리포드 연산 $F_u$를 적용한다.
   • 결정적으로, $F_u$는 기존의 $Z$-타입 안정자들이 피벗 큐비트 $i$ 상에서 자명하게 작용하기 때문에, 이전에 찾아낸 모든 대각($Z$-타입) 안정자들을 보존한다.
   • 새로운 안정자를 $Z$-타입 안정자로 변환하기 위해 무작위 국소 보정($H_i$ 또는 $H_i S_i$)이 적용된다.
5. 종료: 이 과정은 대각 안정자 부분 공간의 차원을 단조롭게 증가시키며 반복된다. 차원이 $n$에 도달하면, 상태는 계산 기저 상태가 되며, 이는 최종 측정을 통해 완전히 결정된다. 원래의 상태는 $|\psi\rangle = C^\dagger |z\rangle$로 복구된다.

확장

본 논문은 이 적응형 메커니즘을 세 가지 추가 시나리오로 확장한다:

• 내성 학습(Tolerant Learning): 혼합 또는 비안정자 입력 $\rho$에 대해 가장 가까운 안정자 상태를 학습하는 경우 ($F_{\text{stab}}(\rho) > \sqrt{2/3}$). 알고리즘은 후보 리스트를 생성하고 클래식 섀도우(classical shadows)를 사용하여 충실도(fidelity)를 추정한다.
• 내성 테스트(Tolerant Testing): 안정자 상태 집합에 대해 충실도가 $\ge 1-\epsilon_1$인 상태와 $\le 1-\epsilon_2$인 상태를 구별한다.
• 메모리 보조 테스트(Memory-Assisted Testing): $k$ 큐비트의 결맞은 양자 메모리를 사용하여 테스트하며, 단일 복사본($k=0$)과 2-복사본($k=n$) 영역 사이를 보간한다.
• 낮은 안정자 영성(Low Stabilizer Nullity): 안정자 영성 $r$을 가진 순수 상태(안정자 부분 공간의 차원이 $n-r$인 상태, 여기에는 유계된 수의 비클리포드 게이트를 포함하는 클리포드 회로로 준비된 상태가 포함됨)를 학습한다.

3. 주요 기여 및 결과

A. 최적의 단일 복사본 학습

주요 결과는 적응성이 단일 복사본 학습과 2-복사본 학습 사이의 격차를 완전히 메운다는 증명이다.

• 정리 II.1: 미지의 $n$-큐비트 안정자 상태는 $N = O(n + \log(1/\delta))$개의 복사본과 적응형 단일 복사본 측정만을 사용하여 확률 $1-\delta$로 학습될 수 있다.
• 복잡도: 알고리즘은 다항 시간 $O(n T^2)$ 내에 실행된다 (여기서 $T = O(n + \sqrt{n \log(1/\delta)} + \log(1/\delta))$는 라운드 수이다).
• 최적성: 이는 $\Theta(n)$의 합동 측정(collective measurements) 하한선과 일치하며, 이 환경에서 최적의 샘플 복잡도를 달성하기 위해 결맞은 다중 복사본 접근이 필요하지 않음을 입증한다.

B. 내성 학습 및 테스트

• 내성 학습 (정리 III.1): $F_{\text{stab}}(\rho) \ge f_0 > \sqrt{2/3}$인 입력 $\rho$에 대해, 알고리즘은 $O(n + \xi^{-2}\log(1/\delta))$개의 복사본을 사용하여 최적값의 $\xi$ 이내의 충실도를 갖는 안정자 상태를 출력한다.
• 내성 테스트 (정리 IV.1): 저자들은 $F_{\text{stab}}(\rho) \ge 1-\epsilon_1$과 $F_{\text{stab}}(\rho) \le 1-\epsilon_2$를 구별하는 다항 시간 테스터를 샘플 복잡도 $O(n + \frac{\epsilon_2}{(\epsilon_2-\epsilon_1)^2} \log(1/\delta))$로 제공한다. 이는 단일 복사본 측정을 통한 효율적인 내성 테스트의 가능성에 대한 열린 질문을 해결한다.
• 하한선: 논문은 순수 입력에 대해 $\Omega(n + \frac{\epsilon_2}{(\epsilon_2-\epsilon-1)^2})$개의 복사본이 필요함을 확립하여, 제안된 테스터의 최적성을 확인한다.

C. 메모리-샘플 트레이드오프(Tradeoff)

• 정리 V.1: $k$ 큐비트의 양자 메모리를 가진 안정자 테스트의 경우, 최적의 샘플 복잡도는 $\Theta(n - k + 1/\epsilon)$이다.
• 시사점: 서브 리니어(sub-linear) 샘플 복잡도(즉, $\Theta(n)$보다 나은 성능)를 달성하려면 거의 전체 상태($k \approx n$)를 저장해야 한다. $k=0$이면 복잡도는 $\Theta(n)$이고, $k=n$이면 $\Theta(1)$로 떨어진다.

D. 낮은 영성 상태 학습

• 정리 VI.1: 안정자 영성 $r$을 가진 상태($t$개의 T-게이트가 도핑된 $t$-도핑 상태 포함)는 $O(2^r(n + \log(1/\delta)) + 2^r \epsilon^{-2}(r + \log(1/\delta)))$개의 복사본을 사용하여 학습될 수 있다.
• 메커니즘: 적응형 압축은 $2^r$ 배만큼 느려지는데, 이는 차이 샘플 중 유효한 안정자 방향을 드러내는 비율이 $2^{-O(r)}$이기 때문이다. 그러나 "해롭지 않은" 샘플은 기존의 대각 구조를 파괴하지 않는다.

4. 의의 및 주장

본 논문은 고전적 적응성만으로도 샘플 최적의 안정자 학습이 가능하다고 주장하며, 결맞은 다중 복사본 접근의 필요성을 제거한다. 이는 다음과 같은 이유로 중요한 발견이다:

1. 격차 해소: 비적응형 제한($\Omega(n^2)$)과 2-복사본 벨 샘플링($\Theta(n)$) 사이의 이차적 분리가 결맞은 다중 복사본 접근의 근본적인 한계가 아니라, 비적응형 제한에 의한 인위적인 결과임을 보여준다.
2. 실험적 실현 가능성: 알고리즘은 단일 복사본에 대한 클리포드 연산과 그에 따른 계산 기저 측정을 요구하므로, 결맞은 다중 복사본 저장이 어려운 현재의 실험적 제약 조건과 매우 잘 부합한다.
3. 구조적 통찰: 본 연구는 안정자 학습이 적응성이 근본적인 차이를 만드는 "자연스러운 구조적 환경"임을 강조한다. 측정 결과는 데이터를 제공하는 동시에, 이전에 발견한 구조를 보존하면서 상태를 단순화하는 변환을 식별하는 이중 목적을 수행한다.
4. 광범위한 맥락: 저자들은 적응성이 특정 구조적 작업(보존 가우시안 토모그래피 또는 안정자 학습 등)에는 도움이 되지만, 트레이스 거리(trace distance)에 대한 일반적인 혼합 상태 토모그래피에는 점근적 이점을 제공하지 않는다는 점을 언급한다. 이 연구는 적응성이 유익한 경계를 구분하는 데 도움을 준다.

논문은 낮은 영성 상태에 대한 $2^r$의 곱셈적 의존성을 가산적(additive)으로 만들 수 있는지, 그리고 샘플 복잡도의 선행 상수를 줄여 집합적 측정 하한선과 일치시킬 수 있는지와 같은 향후 과제를 제시하며 마무리된다.