기술 요약: 노이즈가 있는 얽힘을 이용한 비로컬 게임 및 통신 복잡도

문제 정의

본 연구는 양자 정보 이론의 두 가지 근간인 비로컬 게임(non-local games)과 얽힘 보조 통신 복잡도(entanglement-assisted communication complexity)에 노이즈가 미치는 영향을 조사한다. 표준 모델은 완벽하고 노이즈가 없는 얽힘(구체적으로는 무제한의 EPR 쌍 공급)을 가정하지만, 실제 근접 미래의 응용 분야에서는 노이즈가 있는 공유 자원을 사용하게 된다. 저자들은 완벽한 EPR 쌍의 한쪽 절반을 노이즈 채널에 통과시켜 생성된 고정된 노이즈 얽힘 상태 $\Psi_{E_A E_B}$의 독립적인 복사본을 임의의 수만큼 공유하는 모델을 연구한다.

이 논문은 다음 두 가지 주요 질문을 다룬다:

1. 노이즈가 있는 EPR 쌍을 공유할 때, 노이즈가 비로컬 게임의 승리 확률(값)에 어떤 영향을 미치는가(특히 CHSH 게임의 경우)?
2. 노이즈가 있는 얽힘은 통신 복잡도 작업(특히 Equality 함수 및 관계형 문제)에서 완벽한 얽힘과 동일한 계산 능력을 제공하는가?

연구에서는 네 가지 특정 노이즈 모델을 고려한다: 탈분극 노이즈(depolarizing noise), 유니탈 노이즈(unital noise) (탈분극 및 디페이징을 포함하는 일반적인 클래스), 편향된 리셋 노이즈(biased reset noise), 그리고 **소거 노이즈(erasure noise)**이다.

방법론

저자들은 연산자 대수(operator algebra), 하이퍼컨트랙티비티 부등식(hypercontractivity inequalities), 그리고 기하학적 논증을 결end하여 결과를 도출한다.

1. 최대 상관관계 및 하이퍼컨트랙티비티

핵심 도구는 Beigi가 도입한 고전적 개념의 양자 일반화인 공유 상태의 최대 상관관계(maximal correlation, $MC$)이다. 저자들은 네 가지 노이즈 모델에 대해 EPR 쌍의 최대 상관관계를 계산한다.

• 저자들은 노이즈 채널에 대한 하이퍼컨트랙티비티 정리를 확립한다. 탈분극 노이즈의 경우 알려진 결과를 활용하며, 일반적인 유니탈 노이즈의 경우 King의 곱 가능성(multiplicativity) 결과를 사용하여 새로운 하이퍼컨트랙티비티 정리를 증명하고, 소거 노이즈의 경우 기존 결과를 변형하여 적용한다.
• 이러한 정리들을 통해 저자들은 결합 출력 확률 분포 $P_{AB|xy}(a,b)$를 주변 확률 분포 $P_{A|x}(a)P_{B|y}(b)$의 거듭제곱(구체적으로 노이즈 파라미터에 의존하는 $1/(1+\rho)$승, 여기서 $\rho$는 최대 상관관계)에 의해 상한을 둔다.

2. 비로컬 게임 분석

• 상한(Upper Bounds): 저자들은 노이즈가 있는 얽힘 하에서의 CHSH 게임 값에 대한 상한을 도출한다. 유니탈 노이즈의 경우, 최대 상관관계로부터 유도된 추가 제약 조건을 가진 NPA 로컬 레벨 1 반정부호 계획법(SDP) 완화 기법을 사용한다. 일반적인 노이즈의 경우, CHSH 편향(bias)의 특정 구조를 활용하여 최대 상관관계를 직접 사용하여 상한을 도출한다.
• 병렬 반복(Parallel Repetition): 저자들은 노이즈가 있는 병렬 반복 정리를 증명한다. 단일 복사본의 양자 값이 지수적 감소의 밑(base)이 되는 표준 병렬 반복 정리와 달리, 이 정리는 감소율을 고전적 값과 최대 상관관계에 관한 식으로 표현한다.
  • 일반적인 게임의 경우, 점별 상한(pointwise bound)과 렌니 발산(Rényi divergence)을 사용하여 노이즈가 있는 양자 값을 고전적 병렬 반복 값과 연결한다.
  • 유니크 게임(CHSH 포함)의 경우, 충돌 연산자의 유도 노름(induced norms)을 통해 정의되는 충돌 값(collision value, $col_p(G)$)을 도입한다. 출력 공간을 주변 확률에 따른 "버킷(buckets)"으로 분할하고, "하드 리스트 상한"(고전적 값에 기반)과 "충돌 리스트 상한"(충돌 값에 기반) 사이를 보간하여 승리 확률의 상한을 구한다.

3. 통신 복잡도 분석

• 분리 결과(Separation Results): 저자들은 통신 모델을 분리하기 위해 관계형 문제(특히 CHSH 게임의 임계 버전)를 구성한다. 이는 완벽한 얽힘을 사용하면 특정 문제를 통신 없이 해결할 수 있는 반면, 노이즈가 있는 얽힘을 사용할 때는 선형 통신이 필요함을 보여준다.
• 얽힘 시뮬레이션: 저자들은 노이즈가 있는 공유 무작위성(shared randomness)으로 완벽한 공유 무작위성을 시뮬레이션하는 것([CGMS15]의 방식)을 얽힘 보조 설정으로 일반화한다. 두 방향 얽힘 보조 프로토콜을 벡터의 내적 추정 문제로 환원한다. 존슨-린덴스트라우스(Johnson-Lindenstrauss) 차원 축소와 상관된 무작위 변수의 다항식 전개를 사용하여, 노이즈가 있는 공유 무작위성을 사용하는 동시 메시지 전달(SMP) 프로토콜을 구축한다.
• Equality에 대한 하한: Equality 함수($EQ_n$)에 대한 하한을 증명하기 위해, 표준 패킹 논증(packing argument)과 최대 상관관계 맵의 특이값 분해(SVD)를 결합한다. 저자들은 상수 통신을 위해 필요한 노이즈가 있는 EPR 쌍의 수가 $n$에 대해 다항식적으로 증가해야 함을 보여준다.

주요 기여 및 결과

1. CHSH 게임 값의 상한

본 논문은 네 가지 노이젤 모델 모두에 대해 CHSH 게임의 새로운 상한 및 하한을 제공한다.

• 상한: 값은 $\rho$의 함수로 상한이 결정된다. 유니탈 노이즈의 경우, 상한은 $\min\left(\frac{1}{2} + \frac{1}{4}\sqrt{1-\rho^2}, \frac{1}{2} + \frac{\sqrt{1+\rho}}{4}\right)$이다. 일반적인 노이즈의 경우, $\min\left(\frac{1}{2} + \frac{1}{4\sqrt{1-\rho^2}}, \frac{1}{2} + \frac{1}{2\sqrt{2}}\right)$이다.
• 의의: 이러한 상한은 이전 연구[FQXY26]가 트레이스리스(traceless) 관측량을 요구했던 것과 달리, 관측량에 대한 가정 없이 성립한다. 저자들은 탈분극 노이즈의 경우, 상태가 여전히 얽혀 있는 낮은 노이즈 수준(상한이 고전적 값을 초과하는 구간)에서 상한이 타이트하지 않다고 언급한다.

2. 노이즈가 있는 병렬 반복 정리

• 일반 게임: $n$개의 병렬 복사본을 가진 게임 $G$의 노이즈가 있는 양자 값은 $(2\rho \log(|A||B|) \cdot w_G)^{\frac{n}{1+\rho}}$로 상한이 제한된다 (여기서 $w_G$는 고전적 값이다).
• 유니크 게임: 더 정교한 상한이 도출된다: $O(n^2) \cdot \left( (col_{1+\rho}(G))^{4\rho} w_G^{1-\rho} \right)^{\frac{n}{1+3\rho}}$.
• CHSH 특이 사항: 탈분극, 유니탈, 소거 노이즈 하에서의 CHSH 게임에 대해, 저자들은 병렬 반복율이 노이즈가 없는 양자 값($\cos^2(\pi/8)$)보다 엄격히 작음을 증명한다(특히 최대 상관관계 $\rho \le 0.36$인 범위에서). 이는 노이즈가 상태를 분리(separable)시키기 전이라도 얽힘의 이점을 저하시킨다는 점에서 중요하다.

3. 통신 복잡도의 분리

• 노이즈 vs 완벽한 얽힘: 저자들은 완벽한 EPR 쌍을 사용하는 통신과 노이즈가 있는 EPR 쌍을 사용하는 통신 사이의 분리를 증명한다. $t$-out-of-$n$ CHSH에 기반한 관계형 문제가 존재하며, 이는 완벽한 얽힘을 사용하면 제로 통신으로 해결할 수 있지만, 충분히 노이즈가 있는 상태를 사용하는 노이즈 얽힘의 경우 $\Theta(n)$의 양방향 고전 통신이 필요함을 보여준다.
• 함의: 이는 특정 노이즈 상태로부터 $n$개의 거의 완벽한 EPR 쌍을 추출(distill)하는 데 필요한 양방향 통신 비용에 대한 $\Omega(n)$ 하한을 의미하며, 이는 해당 상태들에 대한 기존의 추출 프로토콜이 최적임을 보여준다.
• 노이즈 얽힘 vs 완벽한 무작위성: 충분히 낮은 노이즘 환경에서, 노이즈 얽힘은 특정 작업에 대해 완벽한 공유 무작위성보다 엄격히 약하다. 왜냐하면 노이즘 얽힘은 완벽한 무작위성이 할 수 있는 방식대로 통신 오버헤드 없이 완벽한 무작위성을 시뮬레이션할 수 없기 때문이다.

4. Equality를 위한 노이즈 얽힘의 비용

• 다항식 하한: 본 논문은 모든 네 가지 노이즈 모델 하에서, 상수 통신으로 Equality 함수($EQ_n$)를 계산하기 위해 다항식 개수의 노이즈 있는 EPR 쌍이 필요함을 증명한다(구체적으로 $n^{\Omega(1)}$).
• 열린 문제 해결: 이는 [CGMS15]의 질문에 대해 부정적인 답변을 내놓음으로써 문제를 해결한다: 로그 단위의 노이즈 있는 공유 비트(또는 노이즈 있는 EPR 쌍)는 Equality를 위한 상수 통신 프로토콜에 충분하지 않다. 완벽한 상관관계의 경우 $O(\log n)$이면 충분한 것과 대조적으로, 필요한 자원 비용은 기하급수적으로 높다.

5. 프로토콜 시뮬레이션

저자들은 모든 상호작적인 얽힘 보조 통신 프로토콜이 통신량의 지수적 팽창을 동반하며 노이즈 있는 공유 무작위성을 사용하는 SMP 프로토콜에 의해 시뮬레이션될 수 있음을 보여준다. 이는 노이즈 없는 공유 무작위성을 시뮬레이션하는 기존 연구를 일반화한 것이다.

의의 및 주장

본 논문은 노이즈가 있는 얽힘의 존재 하에서 통신 복잡도를 체계적으로 연구한 첫 번째 연구라고 주장하며, 이 모델이 여러 작업에서 노이즈 없는 모델보다 엄격히 약함을 입증한다.

• 비자명한 노이즈 영역: 핵심 기여 중 하나는 얽힘의 이점이 감소하는 "비자명한" 노이즈 영역(예: 탈분극 노이즘에서 $\rho > 1/3$인 경우)을 보여준 것이다. 병렬 반복율은 상태가 여전히 얽혀 있음에도 불구하고 노이즈가 없는 양자 값 아래로 떨어진다.
• 추출의 최적성: 분리 결과는 특정 노이즈 상태로부터 $n$개의 쌍을 추출하는 데 필요한 양방향 통신 비용에 대한 기존의 추출 프로토콜이 최적임을 시사한다. 이는 이전에 확립되지 않았던 결과이다.
• 자원 스케일링: 본 연구는 노이즈 얽힘의 자원 스케일링을 명확히 한다. 즉, Equality를 위한 상수 통신을 위해서는 다항식 개수의 복사본이 필요하며, 이는 완벽한 자원을 사용할 때 가능한 로그 스케일링과 극명하게 대조된다.

저자들은 한계점도 인정하는데, 사용된 기술이 현재 진폭 감쇄 노이즈(amplitude damping noise)(최대 상관관계가 1인 경우)에는 적용되지 않으며, 편향된 리셋 노이즈에 대한 병렬 반복 정리는 적절한 하이퍼컨트랙티비티 결과의 부재로 인해 여전히 미해결 상태라는 점을 언급한다. 또한 병렬 반복율에 대한 상한이 잠재적으로 개선될 수 있음을 시사한다.