Optimal Average Success Probabilities of Binary $(n,n-1)$ and $(n,n-2)$ Quantum Random Access Codes

기술 요약: 이진 $(n, n-1)$ 및 $(n, n-2)$ 양자 무작위 액세스 코드의 최적 평균 성공 확률

문제 정의
본 논문은 양자 무작위 액세스 코드(QRAC)의 근본적인 한계를 다룬다. 이진 $(n, m)$ QRAC에서 $n$비트의 클래식 문자열은 $m$-큐비트 양자 상태로 인코딩된다. 디코더는 주어진 상태와 무작위로 선택된 인덱스 $i \in \{1, \dots, n\}$를 사용하여 $i$번째 비트를 복구하려고 시도한다. 주요 성능 지표는 최적 평균 성공 확률 $P^{Q,avg,opt}_{n,m}$이다.

홀레보(Holevo)의 정리는 전역적인 정보 추출 한계를 설정하지만, 개별 비트에 접근하는 신뢰도를 완전히 규명하지는 못한다. 수치적으로 추측된 상한선인 $P^{Q,avg,opt}_{n,m} \leq \frac{1}{2} + \frac{1}{2}\sqrt{\frac{m}{n}}$은 특정 작은 사례들(예: $(2,1), (3,1), (3,2), (4,2), (6,2)$)에서 타이트함이 관찰되었다. 최근 스즈키(Suzuki)의 구성(for $m=n-1$)과 아키부에 외 저자들(Akibue et al.)의 구성(for $m=n-2$)은 정확히 이 상한선을 달성한다. 그러나 이러한 구성들의 엄격한 최적성—그리고 $m \in \{n-1, n-2\}$인 고율(high-rate) 영역에서의 추측된 상한선의 유효성—은 아직 증명되지 않은 상태였다.

방법론
저자들은 **전체 문자열 퍼티 굿 측정(Full-String Pretty Good Measurement, PGM)**의 특성을 분석함으로써 $m \in \{n-1, n-2\}$에 대한 추측된 상한을 증명한다. 증명 전략은 다음과 같은 단계들을 통해 문제를 로컬 비트 재구성에서 글로벌 문자열 재구성으로 변환하는 것이다:

1. 전체 문자열 PGM 구성: 저자들은 $m$-큐비트 인코딩으로부터 전체 $n$비트 문자열 $X$를 재구성하려는 POVM($Q^C_y$)을 정의한다. 이는 클래식 채널과 전이 확률 $T^{C,PGM}_{xy}$를 유도한다.
2. 로컬-글로벌 변환: 린(Lin)과 드 볼프(de Wolf)의 연구를 바탕으로, 저자들은 전체 문자열 PGM의 결과들을 $i$번째 비트를 제외한 나머지 모든 비트들에 대해 합산하면 정확히 $i$번째 비트에 대한 1-비트 PGM이 된다는 성질을 활용한다.
3. 해밍 거리 경계 설정: 증명은 입력 문자열과 PGM 출력 사이의 기대 해밍 거리 $\Delta_{C,PGM} = E[d_H(X, Y^{C,PGM})]$에 대한 상한과 하한을 설정한다:
   • 상한(Upper Bound): 레네스(Renes)의 정교화된 PGM 상한을 사용하여, 평균 성공 확률이 $P^C$라면 $\Delta_{C,PGM} \leq \frac{n}{2}(1 - (2P^C - 1)^2)$임을 보인다.
   • 하한(Lower Bound): 저자들은 차원 제약 조건과 유도된 채널의 특성을 기반으로 $\Delta_{C,PGM}$에 대한 하한을 도출한다.
     • 저자들은 전이 행렬 $T^{C,PGM}$이 **양의 준정부호(Positive Semidefinite, PSD)**임을 증명한다.
     • PSD 성질을 사용하여, 해밍 거리가 홀수일 확률이 $1/2$ 이하임을 보인다.
     • 나약(Nayak)의 정확한 문자열 복구 확률에 대한 상한($P[Y=X] \leq 2^{m-n}$)과 결합하여, $m=n-1$일 때 $\Delta_{C,PGM} \geq 1/2$이고, $m=n-2$일 때 $\Delta_{C,PGM} \geq 1$임을 입증한다. 일반적으로 $\Delta_{C,PGM} \geq \frac{n-m}{2}$이다.
4. 종합: $\Delta_{C,PGM}$에 대한 상한과 하한을 일치시킴으로써, 저자들은 부등식 $P^C \leq \frac{1}{2} + \frac{1}{2}\sqrt{\frac{m}{n}}$을 도출한다.

주요 기여 및 결과

• 최적성 증명: 본 논문은 $m = n-1$ 및 $m = n-2$인 경우에 대해 추측된 상한 $P^{Q,avg,opt}_{n,m} \leq \frac{1}{2} + \frac{1}{2}\sqrt{\frac{m}{n}}$이 엄격하게 성립함을 입증한다.
• 정확한 특성화: 결과적으로, 본 논문은 다음의 최적 평균 성공 확률을 정확히 결정한다:
  $$P^{Q,avg,opt}_{n,n-1} = P^{Q,avg,opt}_{n,n-2} = \frac{1}{2} + \frac{1}{2}\sqrt{\frac{m}{n}}$$
• 구성의 검증: 이 결과는 스즈키(Suzuki)의 QRAC 구성($n, n-1$용)과 아키부에 외 저자들(Akibue et al.)의 구성($n, n-2$용)이 엄격하게 최적임을 확인해 준다.
• 기술적 보조 정리(Lemmas): 본 연구는 전체 문자열 PGM에 관한 세 가지 핵심 보조 정리를 도입한다:
  1. 평균 성공 확률에 따른 기대 해밍 거리의 상한.
  2. 유도된 채널의 전이 행렬이 양의 준정부호(PSD)라는 증명.
  3. 해밍 거리가 짝수보다 홀수일 가능성이 높지 않음을 보여주는 경계.

의의
본 논문은 큐비트의 수가 클래식 비트 수보다 단 1개 또는 2개 적은 고율(high-rate) 이진 QRAC의 엄격한 최적성 문제를 해결하였다. 추측된 상한을 증명함으로써, 저자들은 이러한 특정 영역에서 압축성과 복구 가능성 사이의 트레이드오프를 정밀하게 규명하였다. 퍼티 굿 측정을 통해 로컬에서 글로벌 재구성으로 변환하는 방법론을 사용하고, 차원 및 PSD 제약을 활용한 이 연구의 방법론은 QRAC 한계를 연구하는 데 있어 새로운 분석적 프레임워크를 제공한다. 이 결과는 알려진 구성에서 관찰된 제곱근 스케일링($\sqrt{m/n}$)이 실제로 이러한 파라미터들에 대한 이론적 한계임을 확증한다.