Guess your neighbor's input: Quantum advantage in Feige's game

이 논문은 1991 년 Feige 가 처음 제안한 비국소 게임 (nonlocal game) 인 "Feige's game"을 재조명하여, 이 게임에서 고전적 전략보다 우월한 양자 전략이 존재함을 증명하고, 게임의 다양한 수학적 성질을 규명합니다. 주요 내용은 다음과 같습니다.

1. 연구 배경 및 문제 정의

• Feige's Game: 두 명의 플레이어 (Alice, Bob) 가 각각 0 또는 1 의 비트 (질문) 를 받습니다. 각 플레이어는 $\{0, 1, \perp\}$ 중 하나의 답을 선택해야 합니다.
  • 승리 조건: 정확히 한 플레이어가 $\perp$를 답하고, 나머지 한 플레이어가 $\perp$를 답한 플레이어의 질문과 동일한 비트를 답해야 합니다.
  • 수식적 정의: $V(a, b, x, y) = 1$ iff $(a, b) = (\perp, x)$ 또는 $(a, b) = (y, \perp)$.
• 기존 연구: 이 게임은 병렬 반복 (parallel repetition) 에서 값이 감소하지 않는 반례로 연구되었습니다. 기존 문헌에서는 양자 우위 (quantum advantage) 가 없을 것으로 추측되었으나 ($\omega_q = \omega_c$), 이에 대한 구체적인 계산은 이루어지지 않았습니다.

2. 주요 결과 (Key Results)

A. 양자 우위의 발견 (Quantum Advantage)

• 고전적 값 ($\omega_c$): $1/2$입니다. 결정적 전략 (deterministic strategy) 을 분석하여 증명되었습니다.
• 양자 값 ($\omega_q$): $9/16$로 증명되었습니다. 이는 고전적 값보다 엄격하게 큽니다.
  • 최적 전략: 플레이어들은 3 차원 힐베르트 공간 ($\mathbb{C}^3$) 에서 작용하는 연산자를 사용하며, 최대 얽힘 상태 $|\psi_3\rangle = \frac{1}{\sqrt{3}}\sum_{i=0}^2 |i\rangle \otimes |i\rangle$을 공유합니다.
  • 구현: Pauli 행렬 $X, Z$를 확장한 $\tilde{X} = X \oplus 1$, $\tilde{Z} = Z \oplus 1$ 연산자와 특정 기저를 이용한 투영 측정을 통해 $9/16$의 승률을 달성합니다.

B. 강건한 자기 테스트 (Robust Self-Testing)

• Feige's game 은 3 차원 최대 얽힘 상태와 해당 최적 측정 연산자에 대한 **강건한 자기 테스트 (robust self-test)**입니다.
• 이는 게임의 최적 양자 전략이 국소 등거리 변환 (local isometries) 하에서 유일함을 의미합니다.
• 증명 방법: 게임 다항식 (game polynomial) 의 합 (sum-of-squares, SOS) 분해를 통해 얻은 대수적 관계를 기반으로 합니다. 특히, 게임 대수 (game algebra) 가 $3 \times 3$ 행렬 대수 ($M_3$) 와 동형임을 보임으로써 유일성을 증명했습니다. 이는 2 개의 질문과 3 개의 답만으로 $|\psi_3\rangle$을 자기 테스트하는 가장 작은 게임 중 하나임을 시사합니다.

C. "OR" 게임으로서의 구조

• Feige's game 은 두 개의 하위 게임 $G_1$과 $G_2$의 "OR" ($G_1 \lor G_2$) 로 표현될 수 있습니다.
  • $G_1$: Alice 가 Bob 의 입력을 맞히는 게임.
  • $G_2$: Bob 이 Alice 의 입력을 맞히는 게임.
• 역설적 발견: 각 하위 게임 $G_1, G_2$의 양자 값은 고전적 값과 동일하게 $1/2$입니다. 그러나 이들의 "OR" 게임인 Feige's game 의 양자 값은 $9/16$으로 증가합니다. 이는 "OR" 게임의 양자 값이 구성 요소 게임들의 양자 값의 최대값보다 클 수 있음을 보여주는 첫 번째 예시 중 하나입니다.

D. 병렬 반복 (Parallel Repetition)

• 짝수 반복 ($n=2m$): 고전, 양자, 비신호 (non-signalling) 값이 모두 일치하며 $1/2^m$이 됩니다. Feige 의 원래 주장대로 2 번 반복 시 값이 감소하지 않습니다 ($1/2 \to 1/2$).
• 홀수 반복 ($n=3$):
  • 고전 값: $5/16$.
  • 비신호 값: $1/3$.
  • 양자 값: 아직 결정되지 않음 (미해결 문제).
  • 흥미로운 점: $n=2$일 때는 고전과 양자 값이 같았으나, $n=3$일 때는 고전과 비신호 값이 다시 분리됩니다. 또한, 최적 양자 전략 (한 게임) 과 최적 고전 전략 (2 회 반복) 을 결합한 전략은 $n=3$의 최적 고전 전략보다 성능이 떨어집니다 ($9/32 < 5/16$).

E. 동기화 게임 (Synchronous Game)

• Feige's game 의 동기화 버전 ($G^s_F$) 을 고려했을 때, 동기화 양자 값 ($\omega^s_q$) 은 고전 값과 동일한 $1/2$로 떨어집니다.
• 이는 동기화 조건 하에서는 양자 우위가 사라지지만, 비동기화 조건에서는 양자 우위가 존재하는 게임의 예시가 됩니다.

3. 방법론 (Methodology)

1. 양자 전략 구성: 3 차원 공간에서의 특정 연산자 ($\tilde{X}, \tilde{Z}$) 와 기저를 설계하여 승률을 계산.
2. 상한 증명 (Upper Bound): NPA 계층 (NPA hierarchy) 과 유사한 SOS (Sum-of-Squares) 분해 기법을 사용하여 게임 다항식을 분석. 컴퓨터 보조 계산을 통해 유리수 계수의 정확한 SOS 분해 ($F^* Y F = \frac{9}{16} - \beta$) 를 유도하여 양자 값의 상한을 엄밀히 증명.
3. 대수적 구조 분석: 최적 전략에서 연산자가 만족해야 하는 대수적 관계 (algebraic relations) 를 도출하고, 이를 통해 게임 대수 $C^*(G)$가 유일 기약 표현 (unique irreducible representation) 을 가짐을 증명하여 자기 테스트 성립.
4. 상호 무관 측정 (MUM) 의 일반화: Feige 게임의 대수적 구조가 상호 무관 측정 (MUM) 의 일반화임을 보이고, 특정 행렬 $\nu$에 대한 유니타리 동치성 (unitary equivalence) 을 증명.

4. 의의 및 결론

이 논문은 Feige's game 이 단순한 병렬 반복의 반례를 넘어, 양자 우위를 보이는 비국소 게임임을 최초로 증명했습니다. 특히, 다음과 같은 이론적 기여를 합니다:

• 최소 자기 테스트: 2 질문 3 답 구조로 3 차원 최대 얽힘 상태를 자기 테스트하는 가장 작은 게임 제공.
• 게임 조합의 비선형성: "OR" 연산이 게임의 양자 값을 비선형적으로 증가시킬 수 있음을 보임.
• 병렬 반복의 복잡성: 반복 횟수에 따라 고전, 양자, 비신호 값의 관계가 복잡하게 변화함을 보여줌 ($n=2$와 $n=3$의 차이).
• 대수적 접근: SOS 분해와 C*-대수 이론을 결합하여 비국소 게임의 최적 전략과 대수적 구조를 체계적으로 분석하는 프레임워크를 제시.

이 연구는 양자 정보 이론, 특히 비국소 게임과 자기 테스트 분야에서 중요한 이정표가 될 것으로 기대됩니다.