CHSH 게임

이번 레슨에서 다룰 마지막 예제는 프로토콜이 아니라, CHSH 게임이라고 알려진 게임입니다.

여기서 게임이라고 할 때, 재미나 스포츠를 위해 즐기는 무언가를 뜻하는 것이 아니라, 게임 이론의 의미에서 수학적 추상화를 가리킵니다. 게임의 수학적 추상화는 예를 들어 경제학이나 컴퓨터 과학에서 연구되며, 매우 흥미롭고 유용합니다.

CHSH라는 글자는 1969년 논문의 저자들 — John Clauser, Michael Horne, Abner Shimony, Richard Holt — 의 이름에서 따온 것으로, 이 논문에서 해당 예제가 처음 소개되었습니다. 그들은 이 예제를 게임이 아닌 실험으로 기술했습니다. 하지만 게임으로 설명하는 것이 자연스럽고 직관적입니다.

CHSH 게임은 *비국소 게임(nonlocal games)*이라고 알려진 게임 분류에 속합니다. 비국소 게임은 매우 흥미롭고 물리학, 컴퓨터 과학, 수학과 깊은 연관이 있으며, 아직 해결되지 않은 미스터리를 품고 있습니다. 이 섹션에서는 먼저 비국소 게임이 무엇인지 설명한 뒤, CHSH 게임과 그 흥미로운 점에 집중하겠습니다.

비국소 게임

비국소 게임은 두 플레이어, Alice와 Bob이 특정 결과를 달성하기 위해 협력하는 협력 게임입니다. 게임은 심판이 진행하며, 심판은 Alice와 Bob이 알고 있는 엄격한 규칙에 따라 행동합니다.

Alice와 Bob은 원하는 방식으로 게임을 준비할 수 있지만, 게임이 시작되면 서로 소통이 금지됩니다. 마치 심판이 탐정 역할을 하고 Alice와 Bob이 각각 다른 방에서 심문받는 용의자처럼, 게임이 일종의 보안 시설에서 진행된다고 상상할 수 있습니다. 또는 Alice와 Bob이 아주 먼 거리에 떨어져 있어, 게임 진행 시간 내에 빛의 속도로도 통신이 불가능하기 때문에 소통이 금지된다고 생각할 수도 있습니다. 즉, Alice가 Bob에게 메시지를 보내려 해도, 그가 수신할 때쯤에는 게임이 이미 끝나 있을 것이고, 그 반대도 마찬가지입니다.

비국소 게임이 진행되는 방식은 다음과 같습니다. 먼저 심판이 Alice와 Bob 각각에게 질문을 합니다. Alice의 질문은 $x$, Bob의 질문은 $y$로 표기합니다. 여기서 $x$와 $y$는 고전 상태로 생각하며, CHSH 게임에서는 비트(bit)입니다.

심판은 무작위성을 사용하여 질문을 선택합니다. 정확히 말하면, 가능한 질문 쌍 $(x,y)$ 각각에 대해 확률 $p(x,y)$가 있으며, 심판은 게임 시점에 이 확률에 따라 무작위로 질문을 선택하기로 약속되어 있습니다. Alice와 Bob을 포함하여 모든 사람이 이 확률을 알고 있지만, 게임이 시작되기 전까지는 어떤 쌍 $(x,y)$이 선택될지 아무도 모릅니다.

Alice와 Bob이 질문을 받은 후, 각자 답변을 제시해야 합니다. Alice의 답변은 $a$, Bob의 답변은 $b$입니다. 마찬가지로 이것들도 일반적으로는 고전 상태이며, CHSH 게임에서는 비트입니다.

이 시점에서 심판은 결정을 내립니다. 답변 쌍 $(a,b)$가 어떤 고정된 규칙에 따라 질문 쌍 $(x,y)$에 대해 올바른지 아닌지에 따라 Alice와 Bob이 이기거나 지게 됩니다. 규칙이 다르면 게임도 달라지며, CHSH 게임에 대한 구체적인 규칙은 다음 섹션에서 설명합니다. 앞서 언급했듯이, 규칙은 모든 사람에게 알려져 있습니다.

다음 다이어그램은 이 상호작용을 그림으로 나타낸 것입니다.

어떤 질문이 주어질지 불확실하고, 특히 각 플레이어가 상대방의 질문을 모른다는 점이 Alice와 Bob에게 비국소 게임을 어렵게 만듭니다 — 마치 각자 다른 방에 있는 공모 용의자들이 진술을 맞추려는 것처럼 말이지요.

심판에 대한 정확한 설명이 비국소 게임의 하나의 인스턴스를 정의합니다. 여기에는 각 질문 쌍의 확률 $p(x,y)$ 명세와, 가능한 질문 쌍 $(x,y)$ 각각에 대해 답변 쌍 $(a,b)$가 이기는지 지는지를 결정하는 규칙이 포함됩니다.

잠시 후 CHSH 게임을 살펴보겠지만, 그에 앞서 다른 비국소 게임들도 흥미롭다는 점을 간략히 짚고 넘어가겠습니다. 사실 이것은 매우 흥미로운 주제이며, 엉킴(얽힘)을 사용했을 때 Alice와 Bob이 얼마나 잘 플레이할 수 있는지 현재까지 알려지지 않은 비국소 게임들도 있습니다. 설정은 단순하지만 그 안에는 복잡성이 내재되어 있으며, 일부 게임에서는 Alice와 Bob의 최선 또는 최선에 근접한 전략을 계산하는 것이 불가능할 정도로 어렵습니다. 이것이 비국소 게임 모델의 놀라운 본질입니다.

CHSH 게임 설명

다음은 CHSH 게임의 정확한 설명입니다. 여기서 (위와 같이) $x$는 Alice의 질문, $y$는 Bob의 질문, $a$는 Alice의 답변, $b$는 Bob의 답변입니다.

• 질문과 답변은 모두 비트입니다: $x,y,a,b\in\{0,1\}.$

• 심판은 질문 $(x,y)$를 균등 무작위로 선택합니다. 즉, 네 가지 가능성 $(0,0),$ $(0,1),$ $(1,0),$ $(1,1)$ 각각이 확률 $1/4$로 선택됩니다.

• 답변 $(a,b)$는 $a\oplus b = x\wedge y$이면 질문 $(x,y)$에 대해 이기고, 그렇지 않으면 집니다. 다음 표는 각 질문 쌍 $(x,y)$에 대해 답변 $(a,b)$의 이기는 조건과 지는 조건을 나열하여 이 규칙을 표현합니다.

$$\begin{array}{ccc} (x,y) & \text{win} & \text{lose} \\[1mm]\hline \rule{0mm}{4mm}(0,0) & a = b & a \neq b \\[1mm] (0,1) & a = b & a \neq b \\[1mm] (1,0) & a = b & a \neq b \\[1mm] (1,1) & a \neq b & a = b \end{array}$$

고전 전략의 한계

이제 CHSH 게임에서 Alice와 Bob의 전략을 살펴보겠습니다. 먼저 고전 전략부터 시작합니다.

결정론적 전략

먼저 결정론적 전략을 다루겠습니다. 여기서 Alice의 답변 $a$는 그녀가 받는 질문 $x$의 함수이고, 마찬가지로 Bob의 답변 $b$는 그가 받는 질문 $y$의 함수입니다. 예를 들어, Alice의 질문이 $0$일 때의 답변은 $a(0)$으로, 질문이 $1$일 때의 답변은 $a(1)$로 표기할 수 있습니다.

어떤 결정론적 전략도 CHSH 게임을 항상 이길 수는 없습니다. 한 가지 논증 방법은 모든 가능한 결정론적 전략을 하나씩 검토하여, 그 중 어느 것도 네 가지 가능한 질문 쌍 중 적어도 하나에서는 진다는 것을 확인하는 것입니다. Alice와 Bob 각자는 1비트에서 1비트로 가는 네 가지 가능한 함수 중 하나를 선택할 수 있으며 — 이는 강좌의 첫 번째 레슨에서 다뤘습니다 — 따라서 확인해야 할 결정론적 전략은 총 $16$가지입니다.

이를 분석적으로도 논증할 수 있습니다. Alice와 Bob의 전략이 $(x,y) = (0,0)$일 때 이기려면 $a(0) = b(0)$이어야 하고, $(x,y) = (0,1)$일 때 이기려면 $a(0) = b(1)$이어야 하며, 마찬가지로 $(x,y)=(1,0)$일 때 이기려면 $a(1) = b(0)$이어야 합니다. 따라서 세 가지 경우 모두에서 이기는 전략이 있다면,

$$b(1) = a(0) = b(0) = a(1).$$

이는 마지막 경우 $(x,y) = (1,1)$에서 전략이 진다는 것을 의미합니다. 이 경우 이기려면 $a(1) \neq b(1)$이어야 하기 때문입니다. 따라서 항상 이기는 결정론적 전략은 존재하지 않습니다.

반면, $a(0)=a(1)=b(0)=b(1)=0$처럼 네 가지 경우 중 세 가지에서 이기는 결정론적 전략은 쉽게 찾을 수 있습니다. 이를 통해 결정론적 전략을 사용했을 때 Alice와 Bob이 이길 수 있는 최대 확률은 $3/4$임을 알 수 있습니다.

확률론적 전략

방금 결론 내렸듯이, Alice와 Bob은 결정론적 전략을 사용하면 CHSH 게임에서 75%보다 높은 승률을 달성할 수 없습니다. 그렇다면 확률론적 전략은 어떨까요? 무작위성을 사용하는 것 — 공유 무작위성(shared randomness), 즉 무작위 선택이 서로 상관되는 경우를 포함하여 — 이 도움이 될 수 있을까요?

결론적으로 확률론적 전략은 Alice와 Bob의 승률을 높이는 데 전혀 도움이 되지 않습니다. 이는 모든 확률론적 전략이 결정론적 전략의 무작위 선택으로 볼 수 있기 때문입니다. 마치 확률론적 연산이 결정론적 연산의 무작위 선택으로 볼 수 있는 것처럼 말이지요. 평균은 최대값을 절대 초과하지 않으므로, 확률론적 전략은 전체 승률 면에서 어떠한 이점도 제공하지 않습니다.

따라서 확률론적이든 결정론적이든 어떤 고전 전략을 사용해도 Alice와 Bob이 달성할 수 있는 최선은 $3/4$의 승률입니다.

CHSH 게임 전략

이 시점에서 자연스럽게 떠오르는 질문은, Alice와 Bob이 양자 전략을 사용하면 더 잘할 수 있는가 하는 것입니다. 특히 다음 그림처럼 그들이 게임을 시작하기 전에 준비해 둔 얽힘 양자 상태를 공유하고 있다면, 승률을 높일 수 있을까요?

대답은 '그렇다'이며, 이것이 이 예제의 핵심이자 흥미로운 이유입니다. 그렇다면 Alice와 Bob이 얽힘을 사용하여 이 게임에서 어떻게 더 잘할 수 있는지 살펴보겠습니다.

필요한 벡터와 행렬

먼저 각 실수 $\theta$ (라디안 단위의 각도로 생각합니다)에 대해 qubit 상태 벡터 $\vert \psi_{\theta}\rangle$를 다음과 같이 정의합니다.

$$\vert\psi_{\theta}\rangle = \cos(\theta)\vert 0\rangle + \sin(\theta) \vert 1\rangle$$

몇 가지 간단한 예시는 다음과 같습니다.

$$\begin{aligned} \vert\psi_{0}\rangle & = \vert 0\rangle \\ \vert\psi_{\pi/2}\rangle & = \vert 1\rangle \\ \vert\psi_{\pi/4}\rangle & = \vert + \rangle \\ \vert\psi_{-\pi/4}\rangle & = \vert - \rangle \end{aligned}$$

아래 분석에서 등장하는 다음 예시들도 있습니다.

$$\begin{aligned} \vert\psi_{-\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle \\[1mm] \vert\psi_{\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle \\[1mm] \vert\psi_{3\pi/8}\rangle & = \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle \\[1mm] \vert\psi_{5\pi/8}\rangle & = -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle \end{aligned}$$

일반적인 형태를 살펴보면, 이 벡터들 사이의 내적은 다음 공식을 따릅니다.

$$\langle \psi_{\alpha} \vert \psi_{\beta} \rangle = \cos(\alpha)\cos(\beta) + \sin(\alpha)\sin(\beta) = \cos(\alpha-\beta). \tag{1}$$

자세히 말하면, 이 벡터들의 원소는 모두 실수이므로 복소켤레를 걱정할 필요가 없습니다. 내적은 코사인의 곱과 사인의 곱의 합입니다. 삼각법의 각도 덧셈 공식 중 하나를 이용하면 위와 같이 단순화됩니다. 이 공식은 실수 단위 벡터 사이의 내적이 그 사이 각도의 코사인이라는 기하학적 해석을 드러냅니다.

이 벡터들 중 임의의 두 벡터의 텐서곱과 $\vert \phi^+\rangle$ 상태의 내적을 계산하면, 분모에 $\sqrt{2}$가 있다는 점만 제외하고 비슷한 식을 얻습니다.

$$\langle \psi_{\alpha} \otimes \psi_{\beta} \vert \phi^+ \rangle = \frac{\cos(\alpha)\cos(\beta) + \sin(\alpha)\sin(\beta)}{\sqrt{2}} = \frac{\cos(\alpha-\beta)}{\sqrt{2}}. \tag{2}$$

이 특정 내적에 관심을 갖는 이유는 곧 명확해지겠지만, 지금은 단순히 공식으로 관찰하는 것으로 충분합니다.

다음으로, 각 각도 $\theta$에 대해 유니타리 행렬 $U_{\theta}$를 다음과 같이 정의합니다.

$$U_{\theta} = \vert 0 \rangle \langle \psi_{\theta} \vert + \vert 1\rangle\langle \psi_{\theta+\pi/2} \vert$$

직관적으로 말하면, 이 행렬은 $\vert\psi_{\theta}\rangle$를 $\vert 0\rangle$으로, $\vert \psi_{\theta + \pi/2}\rangle$를 $\vert 1\rangle$로 변환합니다. 이것이 유니타리 행렬임을 확인하는 핵심 관찰은, 벡터 $\vert\psi_{\theta}\rangle$와 $\vert\psi_{\theta + \pi/2}\rangle$이 모든 각도 $\theta$에 대해 직교한다는 것입니다.

$$\langle \psi_{\theta} \vert \psi_{\theta + \pi/2} \rangle = \cos(\pi/2) = 0.$$

따라서 다음을 알 수 있습니다.

$$\begin{aligned} U_{\theta} U_{\theta}^{\dagger} & = \bigl(\vert 0 \rangle \langle \psi_{\theta} \vert + \vert 1\rangle\langle \psi_{\theta+\pi/2} \vert\bigr) \bigl(\vert \psi_{\theta} \rangle \langle 0 \vert + \vert \psi_{\theta+\pi/2}\rangle\langle 1 \vert\bigr) \\[1mm] & = \vert 0 \rangle \langle \psi_{\theta} \vert \psi_{\theta} \rangle \langle 0 \vert + \vert 0 \rangle \langle \psi_{\theta} \vert \psi_{\theta+\pi/2} \rangle \langle 1 \vert + \vert 1 \rangle \langle \psi_{\theta+\pi/2} \vert \psi_{\theta} \rangle \langle 0 \vert + \vert 1 \rangle \langle \psi_{\theta+\pi/2} \vert \psi_{\theta+\pi/2} \rangle \langle 1 \vert \\[1mm] & = \vert 0 \rangle \langle 0 \vert + \vert 1 \rangle \langle 1 \vert\\[1mm] & = \mathbb{I}. \end{aligned}$$

이 행렬을 명시적으로 나타내면 다음과 같습니다.

$$U_{\theta} = \begin{pmatrix} \cos(\theta) & \sin(\theta)\\[1mm] \cos(\theta+ \pi/2) & \sin(\theta + \pi/2) \end{pmatrix} = \begin{pmatrix} \cos(\theta) & \sin(\theta)\\[1mm] -\sin(\theta) & \cos(\theta) \end{pmatrix}.$$

이것은 회전 행렬의 예시로, 구체적으로는 실수 원소를 가진 2차원 벡터를 원점 주위로 $-\theta$만큼 회전시킵니다. 다양한 형태의 회전에 대한 표준 명명 및 매개변수화 관례를 따르면, $U_{\theta} = R_y(-2\theta)$이며 여기서

$$R_y(\theta) = \begin{pmatrix} \cos(\theta/2) & -\sin(\theta/2)\\[1mm] \sin(\theta/2) & \cos(\theta/2) \end{pmatrix}.$$

전략 설명

이제 양자 전략을 설명할 수 있습니다.

• 준비: Alice와 Bob은 e-비트를 공유하며 게임을 시작합니다. Alice는 qubit $\mathsf{A}$를, Bob은 qubit $\mathsf{B}$를 보유하고, 두 qubit $(\mathsf{A},\mathsf{B})$은 함께 $\vert\phi^+\rangle$ 상태에 있습니다.

• Alice의 행동:

  • Alice가 질문 $x=0$을 받으면, 그녀의 qubit $\mathsf{A}$에 $U_{0}$를 적용합니다.
  • Alice가 질문 $x=1$을 받으면, 그녀의 qubit $\mathsf{A}$에 $U_{\pi/4}$를 적용합니다.

  Alice가 $\mathsf{A}$에 수행하는 연산은 다음과 같이 나타낼 수도 있습니다.

  $$\begin{cases} U_0 & \text{if $x = 0$}\\ U_{\pi/4} & \text{if $x = 1$} \end{cases}$$

  Alice는 이 연산을 적용한 후, 표준 기저 측정으로 $\mathsf{A}$를 측정하고 측정 결과를 답변 $a$로 설정합니다.

• Bob의 행동:

  • Bob이 질문 $y=0$을 받으면, 그의 qubit $\mathsf{B}$에 $U_{\pi/8}$를 적용합니다.
  • Bob이 질문 $y=1$을 받으면, 그의 qubit $\mathsf{B}$에 $U_{-\pi/8}$를 적용합니다.

  Alice와 마찬가지로, Bob의 $\mathsf{B}$에 대한 연산을 다음과 같이 표현할 수 있습니다.

  $$\begin{cases} U_{\pi/8} & \text{if $y = 0$}\\ U_{-\pi/8} & \text{if $y = 1$} \end{cases}$$

  Bob은 이 연산을 적용한 후, 표준 기저 측정으로 $\mathsf{B}$를 측정하고 측정 결과를 답변 $b$로 설정합니다.

다음은 이 전략을 설명하는 양자 Circuit 다이어그램입니다.

이 다이어그램에서 일반적인 제어 Gate 두 개를 볼 수 있습니다. 위쪽에는 $U_{-\pi/8}$용, 아래쪽에는 $U_{\pi/4}$용입니다. 또한 제어 Gate처럼 보이는 Gate가 두 개 더 있는데, 위쪽에는 $U_{\pi/8}$용, 아래쪽에는 $U_{0}$용입니다. 다만 제어를 나타내는 원이 채워져 있지 않습니다. 이는 제어가 $0$으로 설정될 때 Gate가 수행되는 다른 유형의 제어 Gate를 나타냅니다 (일반 제어 Gate처럼 $1$일 때가 아닙니다). 즉, Bob은 $y=0$이면 Qubit에 $U_{\pi/8}$를, $y=1$이면 $U_{-\pi/8}$를 수행하고, Alice는 $x=0$이면 Qubit에 $U_0$를, $x=1$이면 $U_{\pi/4}$를 수행하는데, 이는 위의 프로토콜 설명과 일치합니다.

이제 이 Alice와 Bob의 전략이 얼마나 잘 작동하는지 알아봐야 합니다. 네 가지 가능한 질문 쌍을 하나씩 살펴보겠습니다.

경우별 분석

• 경우 1: $(x,y) = (0,0).$

  이 경우 Alice는 자신의 Qubit에 $U_{0}$을 적용하고 Bob은 자신의 Qubit에 $U_{\pi/8}$을 적용합니다. 따라서 두 qubit $(\mathsf{A},\mathsf{B})$가 각자의 연산을 수행한 후의 상태는 다음과 같습니다.

  $$\begin{aligned} \bigl(U_0 \otimes U_{\pi/8}\bigr) \vert \phi^+\rangle & = \vert 00 \rangle \langle \psi_0 \otimes \psi_{\pi/8}\vert \phi^+\rangle + \vert 01 \rangle \langle \psi_0 \otimes\psi_{5\pi/8}\vert \phi^+\rangle \\ & \qquad + \vert 10 \rangle \langle \psi_{\pi/2} \otimes \psi_{\pi/8}\vert \phi^+\rangle + \vert 11 \rangle \langle \psi_{\pi/2} \otimes \psi_{5\pi/8}\vert \phi^+\rangle\\[2mm] & = \frac{ \cos\bigl(-\frac{\pi}{8}\bigr) \vert 00\rangle + \cos\bigl(-\frac{5\pi}{8}\bigr) \vert 01\rangle + \cos\bigl(\frac{3\pi}{8}\bigr) \vert 10\rangle + \cos\bigl(-\frac{\pi}{8}\bigr) \vert 11\rangle}{\sqrt{2}}. \end{aligned}$$

  따라서 네 가지 가능한 답 쌍 $(a,b)$에 대한 확률은 다음과 같습니다.

  $$\begin{aligned} \operatorname{Pr}\bigl((a,b)=(0,0)\bigr) & = \frac{1}{2}\cos^2\Bigl(-\frac{\pi}{8}\Bigr) = \frac{2+\sqrt{2}}{8} \\[2mm] \operatorname{Pr}\bigl((a,b)=(0,1)\bigr) & = \frac{1}{2}\cos^2\Bigl(-\frac{5\pi}{8}\Bigr) = \frac{2-\sqrt{2}}{8}\\[2mm] \operatorname{Pr}\bigl((a,b)=(1,0)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{3\pi}{8}\Bigr) = \frac{2-\sqrt{2}}{8}\\[2mm] \operatorname{Pr}\bigl((a,b)=(1,1)\bigr) & = \frac{1}{2}\cos^2\Bigl(-\frac{\pi}{8}\Bigr) = \frac{2+\sqrt{2}}{8} \end{aligned}$$

  이를 합산하여 $a=b$일 확률과 $a\neq b$일 확률을 구할 수 있습니다.

  $$\begin{aligned} \operatorname{Pr}(a = b) & = \frac{2 + \sqrt{2}}{4}\\[2mm] \operatorname{Pr}(a \neq b) & = \frac{2 - \sqrt{2}}{4} \end{aligned}$$

  질문 쌍 $(0,0)$에서는 $a=b$이면 Alice와 Bob이 이기므로, 이 경우 이길 확률은 다음과 같습니다.

  $$\frac{2 + \sqrt{2}}{4}.$$

• 경우 2: $(x,y) = (0,1).$

  이 경우 Alice는 자신의 Qubit에 $U_{0}$을 적용하고 Bob은 자신의 Qubit에 $U_{-\pi/8}$을 적용합니다. 따라서 두 qubit $(\mathsf{A},\mathsf{B})$가 각자의 연산을 수행한 후의 상태는 다음과 같습니다.

  $$\begin{aligned} \bigl(U_0 \otimes U_{-\pi/8}\bigr) \vert \phi^+\rangle & = \vert 00 \rangle \langle \psi_0 \otimes \psi_{-\pi/8}\vert \phi^+\rangle + \vert 01 \rangle \langle \psi_0 \otimes\psi_{3\pi/8}\vert \phi^+\rangle \\ & \qquad + \vert 10 \rangle \langle \psi_{\pi/2} \otimes \psi_{-\pi/8}\vert \phi^+\rangle + \vert 11 \rangle \langle \psi_{\pi/2} \otimes \psi_{3\pi/8}\vert \phi^+\rangle\\[2mm] & = \frac{ \cos\bigl(\frac{\pi}{8}\bigr) \vert 00\rangle + \cos\bigl(-\frac{3\pi}{8}\bigr) \vert 01\rangle + \cos\bigl(\frac{5\pi}{8}\bigr) \vert 10\rangle + \cos\bigl(\frac{\pi}{8}\bigr) \vert 11\rangle}{\sqrt{2}}. \end{aligned}$$

  따라서 네 가지 가능한 답 쌍 $(a,b)$에 대한 확률은 다음과 같습니다.

  $$\begin{aligned} \operatorname{Pr}\bigl((a,b)=(0,0)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2+\sqrt{2}}{8} \\[2mm] \operatorname{Pr}\bigl((a,b)=(0,1)\bigr) & = \frac{1}{2}\cos^2\Bigl(-\frac{3\pi}{8}\Bigr) = \frac{2-\sqrt{2}}{8}\\[2mm] \operatorname{Pr}\bigl((a,b)=(1,0)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{5\pi}{8}\Bigr) = \frac{2-\sqrt{2}}{8}\\[2mm] \operatorname{Pr}\bigl((a,b)=(1,1)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2+\sqrt{2}}{8} \end{aligned}$$

  마찬가지로, 합산을 통해 $a=b$일 확률과 $a\neq b$일 확률을 구할 수 있습니다.

  $$\begin{aligned} \operatorname{Pr}(a = b) & = \frac{2 + \sqrt{2}}{4}\\[2mm] \operatorname{Pr}(a \neq b) & = \frac{2 - \sqrt{2}}{4} \end{aligned}$$

  질문 쌍 $(0,1)$에서는 $a=b$이면 Alice와 Bob이 이기므로, 이 경우 이길 확률은 다음과 같습니다.

  $$\frac{2 + \sqrt{2}}{4}.$$

• 경우 3: $(x,y) = (1,0).$

  이 경우 Alice는 자신의 Qubit에 $U_{\pi/4}$을 적용하고 Bob은 자신의 Qubit에 $U_{\pi/8}$을 적용합니다. 따라서 두 qubit $(\mathsf{A},\mathsf{B})$가 각자의 연산을 수행한 후의 상태는 다음과 같습니다.

  $$\begin{aligned} \bigl(U_{\pi/4} \otimes U_{\pi/8}\bigr) \vert \phi^+\rangle & = \vert 00 \rangle \langle \psi_{\pi/4} \otimes \psi_{\pi/8}\vert \phi^+\rangle + \vert 01 \rangle \langle \psi_{\pi/4} \otimes\psi_{5\pi/8}\vert \phi^+\rangle \\ & \qquad + \vert 10 \rangle \langle \psi_{3\pi/4} \otimes \psi_{\pi/8}\vert \phi^+\rangle + \vert 11 \rangle \langle \psi_{3\pi/4} \otimes \psi_{5\pi/8}\vert \phi^+\rangle\\[2mm] & = \frac{ \cos\bigl(\frac{\pi}{8}\bigr) \vert 00\rangle + \cos\bigl(-\frac{3\pi}{8}\bigr) \vert 01\rangle + \cos\bigl(\frac{5\pi}{8}\bigr) \vert 10\rangle + \cos\bigl(\frac{\pi}{8}\bigr) \vert 11\rangle}{\sqrt{2}}. \end{aligned}$$

  따라서 네 가지 가능한 답 쌍 $(a,b)$에 대한 확률은 다음과 같습니다.

  $$\begin{aligned} \operatorname{Pr}\bigl((a,b)=(0,0)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2+\sqrt{2}}{8} \\[2mm] \operatorname{Pr}\bigl((a,b)=(0,1)\bigr) & = \frac{1}{2}\cos^2\Bigl(-\frac{3\pi}{8}\Bigr) = \frac{2-\sqrt{2}}{8}\\[2mm] \operatorname{Pr}\bigl((a,b)=(1,0)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{5\pi}{8}\Bigr) = \frac{2-\sqrt{2}}{8}\\[2mm] \operatorname{Pr}\bigl((a,b)=(1,1)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2+\sqrt{2}}{8} \end{aligned}$$

  다시 한번, $a=b$일 확률과 $a\neq b$일 확률은 다음과 같습니다.

  $$\begin{aligned} \operatorname{Pr}(a = b) & = \frac{2 + \sqrt{2}}{4}\\[2mm] \operatorname{Pr}(a \neq b) & = \frac{2 - \sqrt{2}}{4} \end{aligned}$$

  질문 쌍 $(1,0)$에서는 $a=b$이면 Alice와 Bob이 이기므로, 이 경우 이길 확률은 다음과 같습니다.

  $$\frac{2 + \sqrt{2}}{4}.$$

• 경우 4: $(x,y) = (1,1).$

  마지막 경우는 조금 다릅니다. 이 경우 승리 조건이 다르기 때문에 예상할 수 있었던 결과입니다. $x$와 $y$가 모두 $1$일 때, Alice와 Bob은 $a$와 $b$가 서로 다른 경우에 이깁니다. 이 경우 Alice는 자신의 Qubit에 $U_{\pi/4}$을 적용하고 Bob은 자신의 Qubit에 $U_{-\pi/8}$을 적용하므로, 두 qubit $(\mathsf{A},\mathsf{B})$가 각자의 연산을 수행한 후의 상태는 다음과 같습니다.

  $$\begin{aligned} \bigl(U_{\pi/4} \otimes U_{-\pi/8}\bigr) \vert \phi^+\rangle & = \vert 00 \rangle \langle \psi_{\pi/4} \otimes \psi_{-\pi/8}\vert \phi^+\rangle + \vert 01 \rangle \langle \psi_{\pi/4} \otimes\psi_{3\pi/8}\vert \phi^+\rangle \\ & \qquad + \vert 10 \rangle \langle \psi_{3\pi/4} \otimes \psi_{-\pi/8}\vert \phi^+\rangle + \vert 11 \rangle \langle \psi_{3\pi/4} \otimes \psi_{3\pi/8}\vert \phi^+\rangle\\[2mm] & = \frac{ \cos\bigl(\frac{3\pi}{8}\bigr) \vert 00\rangle + \cos\bigl(-\frac{\pi}{8}\bigr) \vert 01\rangle + \cos\bigl(\frac{7\pi}{8}\bigr) \vert 10\rangle + \cos\bigl(\frac{3\pi}{8}\bigr) \vert 11\rangle}{\sqrt{2}}. \end{aligned}$$

  따라서 네 가지 가능한 답 쌍 $(a,b)$에 대한 확률은 다음과 같습니다.

  $$\begin{aligned} \operatorname{Pr}\bigl((a,b)=(0,0)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{3\pi}{8}\Bigr) = \frac{2-\sqrt{2}}{8} \\[2mm] \operatorname{Pr}\bigl((a,b)=(0,1)\bigr) & = \frac{1}{2}\cos^2\Bigl(-\frac{\pi}{8}\Bigr) = \frac{2+\sqrt{2}}{8}\\[2mm] \operatorname{Pr}\bigl((a,b)=(1,0)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{7\pi}{8}\Bigr) = \frac{2+\sqrt{2}}{8}\\[2mm] \operatorname{Pr}\bigl((a,b)=(1,1)\bigr) & = \frac{1}{2}\cos^2\Bigl(\frac{3\pi}{8}\Bigr) = \frac{2-\sqrt{2}}{8} \end{aligned}$$

  앞선 세 경우와 비교해 확률이 사실상 자리를 바꾼 형태입니다. 합산하면 $a=b$일 확률과 $a\neq b$일 확률은 다음과 같습니다.

  $$\begin{aligned} \operatorname{Pr}(a = b) & = \frac{2 - \sqrt{2}}{4}\\[2mm] \operatorname{Pr}(a \neq b) & = \frac{2 + \sqrt{2}}{4} \end{aligned}$$

  질문 쌍 $(1,1)$에서는 $a\neq b$이면 Alice와 Bob이 이기므로, 이 경우 이길 확률은 다음과 같습니다.

  $$\frac{2 + \sqrt{2}}{4}.$$

네 가지 경우 모두에서 이길 확률은 동일합니다.

$$\frac{2 + \sqrt{2}}{4} \approx 0.85.$$

따라서 이것이 전체적인 승리 확률입니다. 이는 어떤 고전적인 전략보다도 훨씬 높은 수치입니다. 고전적인 전략의 승리 확률은 $3/4$으로 제한되어 있기 때문입니다. 그래서 이 예제는 매우 흥미롭습니다.

이 확률은 양자 전략에서 최적의 승리 확률이기도 합니다. 즉, 어떤 얽힘 상태나 측정 방법을 선택하더라도 이보다 더 좋은 결과를 낼 수는 없습니다. 이 사실은 Tsirelson의 부등식으로 알려져 있으며, 이를 처음 증명하고 CHSH 실험을 게임으로 처음 묘사한 Boris Tsirelson의 이름을 따서 명명되었습니다.

기하학적 그림

위에서 설명한 전략을 기하학적으로 생각해볼 수 있습니다. 이는 Alice와 Bob의 연산에서 선택한 다양한 각도 사이의 관계를 이해하는 데 도움이 될 수 있습니다.

Alice가 실질적으로 하는 일은 질문 $x$에 따라 각도 $\alpha$를 선택한 뒤, 자신의 Qubit에 $U_{\alpha}$를 적용하고 측정하는 것입니다. 마찬가지로 Bob은 $y$에 따라 각도 $\beta$를 선택한 뒤, 자신의 Qubit에 $U_{\beta}$를 적용하고 측정합니다. 우리는 $\alpha$와 $\beta$를 다음과 같이 선택했습니다.

$$\begin{aligned} \alpha & = \begin{cases} 0 & x=0\\ \pi/4 & x=1 \end{cases}\\[4mm] \beta & = \begin{cases} \pi/8 & y = 0\\ -\pi/8 & y = 1 \end{cases} \end{aligned}$$

지금은 $\alpha$와 $\beta$를 임의의 값이라고 생각해봅시다. Alice는 $\alpha$를 선택함으로써 다음과 같이 생긴 정규직교 기저 벡터들을 효과적으로 정의합니다.

Bob도 마찬가지이지만, 그의 각도는 $\beta$입니다.

벡터의 색깔은 Alice와 Bob의 답변에 대응합니다. 파란색은 $0$, 빨간색은 $1$입니다.

이제 $(1)$과 $(2)$를 결합하면 다음 식을 얻습니다.

$$\langle \psi_{\alpha} \otimes\psi_{\beta} \vert \phi^+ \rangle = \frac{1}{\sqrt{2}} \langle \psi_{\alpha} \vert \psi_{\beta} \rangle,$$

이 식은 모든 실수 $\alpha$와 $\beta$에 대해 성립합니다.

위에서 진행한 분석과 동일한 방식으로, 단 $\alpha$와 $\beta$를 변수로 놓고 전개하면 다음을 얻습니다.

$$\begin{aligned} & \bigl(U_{\alpha} \otimes U_{\beta}\bigr) \vert \phi^+\rangle\\[1mm] & \qquad = \vert 00 \rangle \langle \psi_{\alpha} \otimes \psi_{\beta}\vert \phi^+\rangle + \vert 01 \rangle \langle \psi_{\alpha} \otimes\psi_{\beta + \pi/2}\vert \phi^+\rangle \\ & \qquad \qquad + \vert 10 \rangle \langle \psi_{\alpha+\pi/2} \otimes \psi_{\beta}\vert \phi^+\rangle + \vert 11 \rangle \langle \psi_{\alpha+\pi/2} \otimes \psi_{\beta+\pi/2}\vert \phi^+\rangle\\[2mm] & \qquad = \frac{ \langle \psi_\alpha \vert \psi_\beta \rangle \vert 00\rangle + \langle \psi_\alpha \vert \psi_{\beta+\pi/2} \rangle \vert 01\rangle + \langle \psi_{\alpha+\pi/2} \vert \psi_\beta \rangle \vert 10\rangle + \langle \psi_{\alpha+\pi/2} \vert \psi_{\beta+\pi/2} \rangle \vert 11\rangle }{\sqrt{2}}. \end{aligned}$$

여기서 다음 두 공식을 도출할 수 있습니다.

$$\begin{aligned} \operatorname{Pr}(a = b) & = \frac{1}{2} \vert \langle \psi_\alpha \vert \psi_\beta \rangle \vert^2 + \frac{1}{2} \vert \langle \psi_{\alpha+\pi/2} \vert \psi_{\beta+\pi/2} \rangle \vert^2 = \cos^2(\alpha - \beta)\\[2mm] \operatorname{Pr}(a \neq b) & = \frac{1}{2} \vert \langle \psi_\alpha \vert \psi_{\beta+\pi/2} \rangle \vert^2 + \frac{1}{2} \vert \langle \psi_{\alpha+\pi/2} \vert \psi_\beta \rangle \vert^2 = \sin^2(\alpha - \beta). \end{aligned}$$

이 식들은 Alice와 Bob이 선택한 기저를 겹쳐 놓는 것으로 위의 그림들과 연결됩니다. 특히 $(x,y) = (0,0)$일 때 Alice와 Bob은 $\alpha = 0$과 $\beta = \pi/8$을 선택하며, 두 기저를 겹치면 다음 그림을 얻습니다.

빨간 벡터들 사이의 각도는 $\pi/8$이며, 두 파란 벡터들 사이의 각도도 동일합니다. Alice와 Bob의 측정 결과가 일치할 확률은 이 각도의 코사인 제곱으로,

$$\cos^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2 + \sqrt{2}}{4},$$

결과가 다를 확률은 이 각도의 사인 제곱으로,

$$\sin^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2 - \sqrt{2}}{4}$$

입니다.

$(x,y) = (0,1)$일 때 Alice와 Bob은 $\alpha = 0$과 $\beta = -\pi/8$을 선택하며, 두 기저를 겹치면 다음 그림을 얻습니다.

빨간 벡터들 사이의 각도는 다시 $\pi/8$이고, 파란 벡터들 사이의 각도도 마찬가지입니다. Alice와 Bob의 결과가 일치할 확률은 다시 이 각도의 코사인 제곱으로,

$$\cos^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2 + \sqrt{2}}{4},$$

결과가 다를 확률은 이 각도의 사인 제곱으로,

$$\sin^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2 - \sqrt{2}}{4}$$

입니다.

$(x,y) = (1,0)$일 때 Alice와 Bob은 $\alpha = \pi/4$와 $\beta = \pi/8$을 선택하며, 두 기저를 겹치면 다음 그림을 얻습니다.

기저는 바뀌었지만 각도는 변하지 않았습니다. 다시 한 번 같은 색 벡터들 사이의 각도는 $\pi/8$입니다. Alice와 Bob의 결과가 일치할 확률은

$$\cos^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2 + \sqrt{2}}{4},$$

결과가 다를 확률은

$$\sin^2\Bigl(\frac{\pi}{8}\Bigr) = \frac{2 - \sqrt{2}}{4}$$

입니다.

$(x,y) = (1,1)$일 때 Alice와 Bob은 $\alpha = \pi/4$와 $\beta = -\pi/8$을 선택합니다. 두 기저를 겹쳐 보면, 무언가 다른 일이 일어났음을 알 수 있습니다.

각도가 선택된 방식에 따라, 이번에는 같은 색 벡터들 사이의 각도가 $\pi/8$이 아닌 $3\pi/8$입니다. Alice와 Bob의 결과가 일치할 확률은 여전히 이 각도의 코사인 제곱이지만, 이번에는 그 값이

$$\cos^2\Bigl(\frac{3\pi}{8}\Bigr) = \frac{2 - \sqrt{2}}{4}$$

입니다.

결과가 다를 확률은 이 각도의 사인 제곱으로, 이 경우에는

$$\sin^2\Bigl(\frac{3\pi}{8}\Bigr) = \frac{2 + \sqrt{2}}{4}$$

입니다.

비고

CHSH 게임과 같이 얽힘이 순전히 고전적인 추론으로는 설명할 수 없는 통계적 결과를 이끌어낸다는 실험의 기본 아이디어는 Bell 상태의 이름을 딴 존 벨(John Bell)에서 비롯되었습니다. 이러한 이유로 사람들은 이런 종류의 실험을 흔히 *벨 테스트(Bell test)*라고 부릅니다. 또한 *벨의 정리(Bell's theorem)*를 언급하기도 하는데, 이는 다양한 방식으로 표현될 수 있지만 — 그 본질은 양자역학이 이른바 *국소 숨은 변수 이론(local hidden variable theory)*과 양립하지 않는다는 것입니다. CHSH 게임은 벨 테스트의 특히 명확하고 단순한 예이며, 벨의 정리에 대한 증명 또는 시연으로 볼 수 있습니다.

CHSH 게임은 양자 정보 이론을 실험적으로 검증하는 방법을 제공합니다. CHSH 게임을 구현하고, 위에서 설명한 얽힘 기반 전략들을 검증하는 실험을 수행할 수 있습니다. 이는 얽힘이 실재한다는 높은 수준의 확신을 제공합니다. 얽힘을 설명하는 때로는 모호하거나 시적인 표현들과 달리, CHSH 게임은 얽힘을 관찰할 수 있는 구체적이고 검증 가능한 방법을 제공합니다. 2022년 노벨 물리학상은 이 연구 흐름의 중요성을 인정합니다. 상은 알랭 아스페(Alain Aspect), 존 클라우저(John Clauser, CHSH의 C), 안톤 차일링거(Anton Zeilinger)에게 얽힌 광자를 이용한 벨 테스트를 통해 얽힘을 관찰한 공로로 수여되었습니다.