Prueba de optimización para la estrategia clásica del juego CHSH

Soy consciente de que la optimización de la estrategia cuántica para el juego CHSH está dada por el límite de Tsirelson , pero todas las presentaciones omiten la prueba (ciertamente menos interesante) de la optimización de la estrategia clásica.

En el juego CHSH, tenemos dos jugadores: Alice y Bob. Se les da por separado bits aleatorios independientes $X$ y $Y$ como entrada, y sin bits de comunicación debe de salida de su propio ( $A$ y $B$ ) con el objetivo de hacer verdadera la fórmula lógica $X \cdot Y = A \oplus B$ . La estrategia clásica óptima afirmada es que Alice y Bob siempre produzcan $0$ , lo que resulta en una ganancia del 75% del tiempo:

$\begin{array}{|c|c|c|c|c|c|} \hline X & Y & A & B & X \cdot Y & A \oplus B \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 & 0 \\ \hline \end{array}$

La estrategia cuántica (que paso por aquí ) resulta en una ganancia ~ 85% del tiempo. Puede usar esto como prueba de la insuficiencia de las variables ocultas locales para explicar el enredo de la siguiente manera:

Suponga que los qbits deciden en el momento del enredo cómo colapsarán (en lugar de en el momento de la medición); Esto significa que deben llevar consigo cierta información (la variable oculta local), y esta información puede escribirse como una cadena de bits.
Dado que la información es suficiente para describir completamente la forma en que colapsan los qbits enredados, Alice y Bob podrían, si se les da acceso a esa misma cadena de bits clásicos, simular el comportamiento de un par compartido de qbits enredados.
Si Alice y Bob pudieran simular el comportamiento de un par compartido de qbits entrelazados, podrían implementar la estrategia cuántica con métodos clásicos locales utilizando la cadena precompartida de bits clásicos. Por lo tanto, debe existir alguna estrategia clásica que proporcione una tasa de éxito del 85% con alguna cadena de bits como entrada.
Sin embargo, no existe una cadena de bits que permita una estrategia clásica con una tasa de éxito superior al 75%.
Por contradicción, el comportamiento de las partículas enredadas no es reducible a una cadena de bits (variable oculta local) y, por lo tanto, las partículas enredadas deben afectarse instantáneamente entre sí en el momento de la medición.

Estoy interesado en la prueba de (4). Me imagino que esta prueba toma la forma de un par no comunicativo de máquinas de Turing que toman como entrada bits aleatorios independientes $X$ e $Y$ más una cadena de bits compartida arbitraria, que luego gana el juego CHSH con una probabilidad superior al 75%; presumiblemente esto da como resultado cierta contradicción que demuestra la inexistencia de tales TM. Entonces, ¿qué es esta prueba?

En segundo lugar, ¿qué documentos han presentado una prueba de la optimización de la estrategia clásica?

Pregunta adicional: en (1), afirmamos que la variable oculta local se puede escribir como una cadena de bits; ¿Hay una razón simple por la cual este es el caso?

games ahelwer
fuente

Respuestas:

Yo diría que este es el tema crítico a entender para las desigualdades de Bell. Encontrar una violación de una desigualdad de Bell le dice que el sistema no es clásico (nota: no prueba que sea cuántico), por lo que debe comprender qué es lo clásico que el mundo no es.

Expongamos la variable aleatoria CHSH que nos interesa:

S = A_{1} B_{1} + A_{1} B_{2} + A_{2} B_{1} - A_{2} B_{2},

$S=A_1B_1+A_1B_2+A_2B_1-A_2B_2,$ donde cada uno de

A_{1}, A_{2}, B_{1}, B_{2}

$A_1,A_2,B_1,B_2$ son variables aleatorias con valores de

\pm 1

$\pm1$ . La suposición clave para la estrategia clásica es que para cada ejecución del experimento, las cuatro variables tienen un valor fijo(aunque solo descubramos dos de los valores). Las variables ocultas son esencialmente irrelevantes aquí: permiten que dos partes distantes coordinen cuáles serán esos valores fijos sin tener que comunicarse en el momento, pero no pueden cambiar esta suposición básica.

¿Cuales son las consecuencias de esto? Reescribe $S$ como

S = A_{1} (B_{1} + B_{2}) + A_{2} (B_{1} - B_{2}) .

$S=A_1(B_1+B_2)+A_2(B_1-B_2).$ Ahora, si

B_{1} \in {\pm 1}

$B_1\in\{\pm1\}$ y

B_{2} \in {\pm 1}

$B_2\in\{\pm1\}$ , entonces

B_{1} = B_{2}

$B_1=B_2$ , en cuyo caso

B_{1} - B_{2} = 0

$B_1-B_2=0$ y

B_{1} + B_{2} = \pm 2

$B_1+B_2=\pm 2$ , o

B_{1} = - B_{2}

$B_1=-B_2$ , de modo que

B_{1} + B_{2} = 0

$B_1+B_2=0$ y

B_{1} - B_{2} = \pm 2

$B_1-B_2=\pm 2$ . En cualquier caso,

S = \pm 2

$S=\pm 2$ . Finalmente, si, en cada ejecución del experimento,

S = \pm 2

$S=\pm 2$ , entonces el valor promedio

| ⟨ S ⟩ | \leq 2

$|\langle S\rangle|\leq 2$ .

Entonces, lo que se aprende de la violación de una desigualdad de Bell es que, cada vez que se ejecuta el experimento, no se determinaron todas las respuestas posibles. Clásicamente, esto es posible con la escapatoria de la localidad: si se conocen ambas preguntas, entonces una respuesta ganadora puede decidirse determinísticamente sin tener que especificar todos los demás resultados posibles. De lo contrario, hay algo de aleatoriedad inherente en el juego al elegir las respuestas.

En cuanto a dónde puede encontrar pruebas en la literatura, ¿por qué no hacer un seguimiento de las referencias en el artículo de Wikipedia ? Como digo, el límite clásico es el elemento central, por lo que debe estar en los documentos originales.

Pregunta adicional: en (1), afirmamos que la variable oculta local se puede escribir como una cadena de bits; ¿Hay una razón simple por la cual este es el caso?

Cualquier información puede escribirse como una cadena de bits.

DaftWullie
fuente

Estoy interesado en la justificación de por qué las cuatro variables tienen un valor fijo: esta es una afirmación de que todas las estrategias clásicas deben ser necesariamente deterministas, pero, por supuesto, podemos inyectar el no determinismo a través de un lanzamiento de moneda. No es que crea que las estrategias no deterministas serían más poderosas, pero estoy interesado en una justificación de por qué no se incluyen en el análisis.

ahelwer

No se trata de determinismo o indeterminismo. Puede tener un proceso en segundo plano que determine aleatoriamente los valores de los resultados cada vez que ejecute el experimento, en función del conocimiento local de las opciones de medición, y tal vez algo de aleatoriedad que se compartió por adelantado. Sin embargo, la condición es que cuando se realiza esa elección aleatoria, el resultado debe ser qué respuestas se darían para todos los ajustes de medición, incluso si solo se dan las respuestas específicas para las mediciones elegidas.

DaftWullie

Una forma de probar esto es caracterizar el conjunto de todas las estrategias posibles que Alice & Bob pueden adoptar. Por "estrategia" me refiero a una posible relación entre entradas y salidas, codificada en el conjunto de cuatro números binarios $A_0,A_1,B_0,B_1$ .

Vale la pena señalar que no importa si estamos considerando protocolos deterministas o probabilísticos aquí. La diferencia entre estos dos enfoques está en la forma en que avanzan los pasos del protocolo, pero si uno considera solo la entrada y la salida del protocolo, sin importar cómo se obtiene realmente la salida, entonces caracteriza el conjunto de todas las posibles relaciones de entrada-salida y mostrando que ninguna de estas combinaciones da una probabilidad de ganar mayor al $75\%$ es suficiente. En otras palabras, el uso de un enfoque probabilístico no expande el número de posibles resultados / estrategias, sino que solo proporciona una forma diferente de llegar a ellos. Debido a que solo estamos interesados en la probabilidad ganadora final y, por lo tanto, en la estrategia general, no necesitamos tener en cuenta los casos deterministas y probabilísticos por separado.

Tenga en cuenta que, dada una estrategia $\mathcal S\equiv\{A_0,A_1,B_0,B_1\}$ , podemos escribir el número de combinaciones de entrada para las cuales esta estrategia da el resultado incorrecto como

\begin{matrix} (1) & P_{S} \equiv A_{0} \oplus B_{0} + A_{0} \oplus B_{1} + A_{1} \oplus B_{0} + (1 - A_{1} \oplus B_{1}), \end{matrix}

$P_{\mathcal S}\equiv A_0\oplus B_0 + A_0\oplus B_1 + A_1\oplus B_0 + (1-A_1\oplus B_1),\tag1$ donde

a \oplus b

$a\oplus b$ denota el módulo de suma 2.

Nuestro problema es encontrar la estrategia $\mathcal S$ que minimice $P_{\mathcal S}$ .

Ahora, hay varias formas de hacer esto.

Fuerza bruta

La manera más simple, si el menos elegante, consiste en calcular el valor de $P_{\mathcal S}$ para todas las posibles estrategias de $\mathcal S$ . Hay 16 de estos, así que esto no es tan malo. Con unas pocas líneas de código puede obtener la siguiente tabla

(\begin{array}{ccccc} A_{0} & A_{1} & B_{0} & B_{1} & P_{S} \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 1 & 3 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 3 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 3 \\ 1 & 0 & 0 & 0 & 3 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 3 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 3 \\ 1 & 1 & 0 & 1 & 3 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{array})

$\left( \begin{array}{ccccc} A_0 & A_1 & B_0 & B_1 & P_{\mathcal S} \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 1 & 3 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 3 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 3 \\ 1 & 0 & 0 & 0 & 3 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 3 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 3 \\ 1 & 1 & 0 & 1 & 3 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \right)$ lo que confirma que, de hecho, todas las estrategias posibles hacen que el juego se pierda por al menos una combinación de entrada (es decir, en sus palabras, una probabilidad de éxito no mayor al

75 %

$75\%$ ).

Pero ahora, por supuesto, esta no es una forma muy satisfactoria de resolver el problema (al menos para mí). Sería mucho mejor tener una forma de demostrar la optimización sin tener que comprobar todas las posibilidades. El principal obstáculo a superar es que la ecuación. (1) contiene sumas modulares y sumas regulares, lo que hace que la manipulación sea un poco incómoda, ya que no podemos escribir algo como $A_0\oplus B_0+A_0\oplus B_1=A_0(B_0\oplus B_1)$ .

Puedo ver dos formas de evitar esto, la segunda de las cuales también arroja luz sobre las similitudes entre este formalismo y la prueba regular de las desigualdades CHSH.

Primer metodo

Una forma de evitar este problema es de notar que podemos expresar sumas modulares usando sumas y productos regulares, como siguiente

A \oplus B = (1 - A) B + A (1 - B) = A + B - 2 A B .

$A\oplus B=(1-A)B+A(1-B)=A+B-2AB.$

A_{0} \oplus B_{0} + A_{0} \oplus B_{1} = 2 A_{0} (1 - (B_{0} + B_{1})) + (B_{0} + B_{1}), A_{1} \oplus B_{0} + (1 - A_{1} \oplus B_{1}) = 1 + (2 A_{1} - 1) (B_{1} - B_{0}),

$A_0\oplus B_0+A_0\oplus B_1=2A_0(1-(B_0+B_1))+(B_0+B_1),\\ A_1\oplus B_0+(1-A_1\oplus B_1)=1+(2A_1-1)(B_1-B_0),$

P_{S} = 1 + 2 {B_{0} + A_{0} [1 - (B_{0} + B_{1})] + A_{1} (B_{1} - B_{0})} .

$P_{\mathcal S}=1+2\{B_0+A_0[1-(B_0+B_1)]+A_1(B_1-B_0)\}.$

$B_0=B_1$ $P_{\mathcal S}=1+2A_0\oplus B_0$ $B_0+B_1=1$ $P_{\mathcal S}=1+2A_1\oplus B_0$

$P_{\mathcal S}$

P_{S} = (1 - 2 B_{0}) (B_{1} - B_{0}) [1 + 2 A_{1} \oplus B_{0}] + [1 - (B_{0} + B_{1})] (1 - 2 B_{0}) [1 + 2 A_{0} \oplus B_{0}] + B_{0} (1 - B_{0}) (. . .),

$P_{\mathcal S}=(1-2B_0)(B_1-B_0)[1+2A_1\oplus B_0] + [1-(B_0+B_1)](1-2B_0)[1+2A_0\oplus B_0]+ B_0(1-B_0)(...),$

B_{0} \in {0, 1}

$B_0\in\{0,1\}$

B_{0} = B_{1}

$B_0=B_1$

B_{0} = - B_{1}

$B_0=-B_1$

(1 - 2 B_{0}) (B_{1} - B_{0}) = 1

$(1-2B_0)(B_1-B_0)=1$ iff

B_{0} = - B_{1}

$B_0=-B_1$ , and

(1 - 2 B_{0}) (1 - B_{0} - B_{1}) = 1

$(1-2B_0)(1-B_0-B_1)=1$ iff

B_{0} = B_{1}

$B_0=B_1$ .

Second method

This involves showing that this formalism is equivalent to the one commonly used in the context of deriving the CHSH inequalities.

Denote with $\tilde A_x\equiv 1-2A_x$ the number obtained by replacing $0,1$ in $A_x$ with $+1,-1$ , respectively, and similarly for $\tilde B_y$ . For example, $A_x=0$ gives $\tilde A_x=+1$ . Note that, under this mapping, we have the identities

A_{x} \oplus B_{y} = (1 - {\tilde{A}}_{x} {\tilde{B}}_{y}) / 2.

$A_x\oplus B_y=(1-\tilde A_x\tilde B_y)/2.$ We can then write

P_{S} = \frac{1}{2} [4 - {\tilde{A}}_{0} {\tilde{B}}_{0} - {\tilde{A}}_{0} {\tilde{B}}_{1} - {\tilde{A}}_{1} {\tilde{B}}_{0} + {\tilde{A}}_{1} {\tilde{B}}_{1}] = 2 - S / 2,

$P_{\mathcal S}=\frac{1}{2}\left[4-\tilde A_0\tilde B_0-\tilde A_0\tilde B_1-\tilde A_1\tilde B_0+\tilde A_1\tilde B_1\right] =2 - S/2,$ where we defined

S \equiv {\tilde{A}}_{0} {\tilde{B}}_{0} + {\tilde{A}}_{0} {\tilde{B}}_{1} + {\tilde{A}}_{1} {\tilde{B}}_{0} - {\tilde{A}}_{1} {\tilde{B}}_{1},

$S\equiv \tilde A_0\tilde B_0+\tilde A_0\tilde B_1+\tilde A_1\tilde B_0-\tilde A_1\tilde B_1,$ which you might recognise as equivalent to the operator

\hat{S}

$\hat S$ used when discussing the CHSH inequalities.

Standard arguments now give you $S=\pm 2$ , and thus $\lvert S\rvert\le 2$ , and finally $P_{\mathcal S}\ge1$ (or more precisely $P_{\mathcal S}\in\{1,3\}$ ).

glS
fuente

For "mixing a number of these strategies with some randomness certainly cannot give a better result" is this because we can just pre-generate a random string of bits and give that as input to the process, and it is computationally equivalent to generating a random string while the process is running?

ahelwer

@ahelwer I'm not sure what you mean. I think it is simply that you have only a small number of possible "strategies" in this scenario, "strategy" here meaning relations between inputs and outputs. The locality condition prevents communication between Alice and Bob, therefore these strategies reduce to combinations of local strategies. There is really nothing fancy to be done in such a restrictive situation. A & B look at their inputs and produce outputs. If any produced output is sometimes wrong, how can producing a nondeterministic outcome change this?

glS

I don't believe a nondeterministic outcome would change things, but I'm interested in some proof/justification of that.

ahelwer

that's what I've been trying to prove I believe. I think your confusion might arise from thinking in terms of how efficiently a given strategy might be achieved. This is however not what is considered here. We do not care how A&B might go about implementing an actual strategy (though the "implementation" is quite trivial in this case), we are only considering the winning probability of each strategy. Because we are exploring every single strategy A&B might employ, there is really no room for further improvement. There are literally only 16 ways to play this game

glS

I don't think I'm confused, I'm just interested in a justification of why we can reduce the analysis to the deterministic case (the 16 ways to play the game) and ignore all nondeterministic strategies. Again, I don't believe it will change things, but I want to know the proof of that.

ahelwer

In the CHSH game we have 2 players Alice and Bob. Can we proof in the form of a noncommunication pair of TMs which takes as input independant random bits x and y plus an arbitrary shared bitstring, that ALice and Bob win the CHSH game with probability greater than 75%.

We ask Alice and Bob questions x and y with probability p(xy) they give answers a and b. The rules of the game are denoted using $V(a,b|x,y)$ wich takes the value "1" if a and b are the winning answers. The probability that Alice and Bob win the game is maximized over all possible strategies $P_{win} = max_{strategy} \sum_{x,y} p(x,y) | \sum_{a,b} V(a,b|x,y) p(a,b|x,y).$ Where $p(a,b|x,y)$ is the probability that Alice and Bob produce answers a and b given x and y.

In terms of probabilities there is an distinction between a classical deterministic prob and a classical shared ramdoness probability. A deterministic classical stratey is given by the functions $f_{A}(x) = a$ and $f_{B}(y) = b$ that take the questions x and y.

If we have shared randomness another string r is used with a sharing probability $p(r)$ . Classicaly Alice and Bob can only apply functions $a = f_{A}(x,r)$ and $b = f_{b}(y,r)$ This gives $p(a,b|x,y) = \sum_{x,y}^{} (p(r)) p(a,b|x,y,r)$ In this case the pobability of winning the game is

$P_{win} = max_{strategy} \sum_{x,y} p(x,y) \sum_{a,b} V(a,b|x,y)\sum_{r}p(r)p(a,b|x,y,r)$ . In this case of shared randomnes we have an extra term with the string r. Alice and Bob can fix the best possible r given a deterministic strategy for a and b. So it is possible to run an algorithm on a Turing machine using a string r according to the test setup in the picture. Problem how do we find the best possible string r?

Another way to look at it is to say that the string r as a shared randomness is referred to as a hidden variabele in physics. So the Hidden Variabele Theory is equivalent to using a string r in a turing machine. Therefore we might just as well make use of a proof of the CHSH inequality. Furthermore we can compare an arbitrary HVT (dashed line ) and QM results for a photonic experiment.

A compact proof of the CHSH inequality based on a hidden variabele can be found in the article Entangled photons, nonlocality and Bell inequalities in the undergraduate laboratory.

Bram
fuente