Prova de otimização da estratégia clássica de jogos CHSH

Estou ciente de que a otimização da estratégia quântica para o jogo CHSH é dada pelos limites de Tsirelson , mas todas as apresentações pulam a prova (reconhecidamente muito menos interessante) da otimização da estratégia clássica.

No jogo CHSH, temos dois jogadores: Alice e Bob. Eles são administrados em separado bits aleatórios independentes e como entrada, e sem comunicação deve bits de saída da sua própria ( e ), com o objectivo de tornar verdadeira a fórmula lógica . A estratégia clássica ideal alegada é que Alice e Bob sempre produzam , o que resulta em uma vitória em 75% das vezes: $X$ $Y$ $A$ $B$ $X \cdot Y = A \oplus B$ $0$

$\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}$

A estratégia quântica (que abordarei aqui ) resulta em uma vitória ~ 85% das vezes. Você pode usar isso como prova da insuficiência de variáveis ocultas locais para explicar o emaranhamento da seguinte maneira:

Suponha que os qbits decidam no momento do emaranhado como eles entrarão em colapso (e não no momento da medição); isso significa que eles devem levar consigo algumas informações (a variável oculta local), e essas informações podem ser escritas como uma sequência de bits.
Como as informações são suficientes para descrever completamente a maneira como os qbits emaranhados entram em colapso, Alice e Bob poderiam, se tiverem acesso à mesma sequência de bits clássicos, simular o comportamento de um par compartilhado de qbits emaranhados.
Se Alice e Bob pudessem simular o comportamento de um par compartilhado de qbits emaranhados, eles poderiam implementar a estratégia quântica com métodos clássicos locais usando a sequência pré-compartilhada de bits clássicos. Portanto, deve existir alguma estratégia clássica que dê uma taxa de sucesso de 85% com uma sequência de bits como entrada.
No entanto, não existe uma sequência de bits que permita uma estratégia clássica com taxa de sucesso acima de 75%.
Por contradição, o comportamento de partículas emaranhadas não é redutível a uma sequência de bits (variável oculta local) e, portanto, as partículas emaranhadas devem afetar instantaneamente uma à outra no momento da medição.

Estou interessado na prova de (4). Imagino que essa prova assuma a forma de um par não comunicativo de máquinas de Turing que recebem como entrada os bits aleatórios independentes e mais uma sequência de bits compartilhada arbitrária, que vence o jogo CHSH com probabilidade superior a 75%; presumivelmente, isso resulta em alguma contradição que demonstra a inexistência de tais MTs. Então, o que é essa prova? $X$ $Y$

Secundariamente, quais trabalhos apresentaram uma prova da otimização da estratégia clássica?

Pergunta bônus: em (1), afirmamos que a variável oculta local pode ser escrita como uma sequência de bits; existe uma razão simples para que esse seja o caso?

games ahelwer
fonte

Respostas:

Eu argumentaria que esta é a questão crítica a entender para as desigualdades de Bell. Encontrar uma violação de uma desigualdade de Bell diz a você que o sistema não é clássico (nota: não prova que é quântico); portanto, você precisa entender o que é clássico que o mundo não é.

Vamos indicar a variável aleatória CHSH em que estamos interessados: que cada um de são variáveis aleatórias com valores . O principal pressuposto para a estratégia clássica é que, para cada execução do experimento, todas as quatro variáveis tenham um valor fixo (mesmo que apenas encontremos dois valores). As variáveis ocultas são essencialmente irrelevantes aqui - elas permitem que duas partes distantes coordenem o que esses valores fixos serão sem ter que se comunicar no momento, mas não podem alterar essa suposição básica.

S = {UMA}_{1} B_{1} + {UMA}_{1} B_{2} + {UMA}_{2} B_{1} - {UMA}_{2} B_{2},

$S=A_1B_1+A_1B_2+A_2B_1-A_2B_2,$

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

$A_1,A_2,B_1,B_2$

\pm 1

$\pm1$

Quais são as consequências disso? Reescreva como Agora, se e , então ; nesse caso, e ou , de modo que e . Nos dois casos, . Finalmente, se, em todas as execuções do experimento, , então o valor médio . $S$

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

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

B_{1} \in {\pm 1}

$B_1\in\{\pm1\}$

B_{2} \in {\pm 1}

$B_2\in\{\pm1\}$

B_{1} = B_{2}

$B_1=B_2$

B_{1} - B_{2} = 0

$B_1-B_2=0$

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

$B_1+B_2=\pm 2$

B_{1} = - B_{2}

$B_1=-B_2$

B_{1} + B_{2} = 0

$B_1+B_2=0$

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

$B_1-B_2=\pm 2$

S = \pm 2

$S=\pm 2$

S = \pm 2

$S=\pm 2$

| ⟨ S ⟩ | \leq 2

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

Portanto, o que você aprende com a violação de uma desigualdade de Bell é que, toda vez que o experimento é executado, nem todas as respostas possíveis foram determinadas. Classicamente, isso é possível com a brecha na localidade - se as duas perguntas são conhecidas, uma resposta vencedora pode ser decidida de forma determinística sem a necessidade de especificar todos os outros resultados possíveis. Caso contrário, há alguma aleatoriedade inerente em escolher as respostas.

Quanto a onde você pode encontrar provas na literatura, por que não acompanhar as referências no artigo da wikipedia ? Como eu disse, o limite clássico é o elemento central, portanto deve estar nos trabalhos originais.

Pergunta bônus: em (1), afirmamos que a variável oculta local pode ser escrita como uma sequência de bits; existe uma razão simples para que esse seja o caso?

Qualquer informação pode ser escrita como uma sequência de bits.

DaftWullie
fonte

Estou interessado na justificativa de por que todas as quatro variáveis têm um valor fixo - é uma afirmação de que todas as estratégias clássicas devem ser necessariamente determinísticas, mas é claro que podemos injetar o não-determinismo através de uma troca de moeda. Não que eu acredite que estratégias não determinísticas sejam mais poderosas, mas estou interessado em uma justificativa de por que elas não estão incluídas na análise.

precisa saber é

Não é uma questão sobre determinismo ou indeterminismo. Você pode ter algum processo em segundo plano que determine aleatoriamente os valores dos resultados toda vez que executar o experimento, com base no conhecimento local das opções de medição e, talvez, em alguma aleatoriedade compartilhada com antecedência. No entanto, a condição é que, quando essa escolha aleatória for feita, o resultado deve ser o que respostas seriam dadas para todas as configurações de medição, mesmo que apenas as respostas específicas para as medidas escolhidas sejam fornecidas.

precisa saber é o seguinte

Uma maneira de provar isso é caracterizar o conjunto de todas as estratégias possíveis que Alice & Bob podem adotar. Por "estratégia", quero dizer uma possível relação entre entradas e saídas, codificada no conjunto de quatro números binários . $A_0,A_1,B_0,B_1$

Vale a pena notar que não importa se estamos considerando protocolos determinísticos ou probabilísticos aqui. A diferença entre essas duas abordagens está na maneira como as etapas do protocolo prosseguem, mas se considerarmos apenas a entrada e a saída do protocolo, sem nos preocuparmos com como a saída é realmente obtida, então caracterizamos o conjunto de todas as relações possíveis de entrada e saída. e mostrando que nenhuma dessas combinações oferece uma probabilidade de vitória maior que $75\%$ basta. Em outras palavras, o uso de uma abordagem probabilística não expande o número de possíveis resultados / estratégias, mas apenas fornece uma maneira diferente de alcançá-los. Como estamos interessados apenas na probabilidade de vitória final e, portanto, na estratégia geral, não precisamos levar em consideração o caso determinístico e probabilístico separadamente.

Observe que, dada uma estratégia , podemos escrever o número de combinações de entradas para as quais essa estratégia fornece o resultado errado como que indica o módulo de adição 2. $\mathcal S\equiv\{A_0,A_1,B_0,B_1\}$

\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$

a \oplus b

$a\oplus b$

Nosso problema é encontrar a estratégia que minimize . $\mathcal S$ $P_{\mathcal S}$

Agora, existem várias maneiras de fazer isso.

Força bruta

A maneira mais simples, se a menos elegante, é calcular o valor de para todas as estratégias possíveis . Existem 16 deles, então isso não é tão ruim. Com algumas linhas de código, você pode obter a seguinte tabela $P_{\mathcal S}$ $\mathcal S$

(\begin{array}{ccccc} A_{0 0} & {UMA}_{1} & B_{0 0} & B_{1} & P_{S} \\ 0 0 & 0 0 & 0 0 & 0 0 & 1 \\ 0 0 & 0 0 & 0 0 & 1 & 1 \\ 0 0 & 0 0 & 1 & 0 0 & 3 \\ 0 0 & 0 0 & 1 & 1 & 3 \\ 0 0 & 1 & 0 0 & 0 0 & 1 \\ 0 0 & 1 & 0 0 & 1 & 3 \\ 0 0 & 1 & 1 & 0 0 & 1 \\ 0 0 & 1 & 1 & 1 & 3 \\ 1 & 0 0 & 0 0 & 0 0 & 3 \\ 1 & 0 0 & 0 0 & 1 & 1 \\ 1 & 0 0 & 1 & 0 0 & 3 \\ 1 & 0 0 & 1 & 1 & 1 \\ 1 & 1 & 0 0 & 0 0 & 3 \\ 1 & 1 & 0 0 & 1 & 3 \\ 1 & 1 & 1 & 0 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)$ o que confirma que, de fato, todas as estratégias possíveis levam à perda do jogo por pelo menos uma combinação de entradas (ou seja, em suas palavras, uma probabilidade de sucesso não superior a ).

75 %

$75\%$

Mas agora, é claro, essa não é uma maneira muito satisfatória de resolver o problema (pelo menos para mim). Seria muito melhor ter uma maneira de provar a otimização sem ter que verificar todas as possibilidades. O principal obstáculo a superar é a Eq. (1) contém somas modulares e regulares, o que torna a manipulação um pouco estranha, pois não podemos escrever algo como . $A_0\oplus B_0+A_0\oplus B_1=A_0(B_0\oplus B_1)$

Eu posso ver duas maneiras de contornar isso, a segunda das quais também esclarece as semelhanças entre esse formalismo e a prova regular das desigualdades no CHSH.

Primeiro método

Uma maneira de contornar esse problema é notar que podemos expressar somas modulares usando somas e produtos regulares, como segue A manipulação algébrica simples nos permite escrever e finalmente,

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

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

{UMA}_{0 0} \oplus B_{0 0} + {UMA}_{0 0} \oplus B_{1} = 2 {UMA}_{0 0} (1 - (B_{0 0} + B_{1})) + (B_{0 0} + B_{1}), {UMA}_{1} \oplus B_{0 0} + (1 - {UMA}_{1} \oplus B_{1}) = 1 + (2 {UMA}_{1} - 1) (B_{1} - B_{0 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)\}.$

Agora você pode verificar se, se então , enquanto que se , . $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$

Equivalentemente, pode-se verificar que também pode ser escrito como que o último termo é sempre zero como . Observe que essa é apenas uma maneira de expressar algebricamente o que acontece nos dois casos e , como se e se . $P_{\mathcal S}$

P_{S} = (1 - 2 B_{0 0}) (B_{1} - B_{0 0}) [1 + 2 {UMA}_{1} \oplus B_{0 0}] + [1 - (B_{0 0} + B_{1})] (1 - 2 B_{0 0}) [1 + 2 {UMA}_{0 0} \oplus B_{0 0}] + B_{0 0} (1 - B_{0 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$

B_{0} = - B_{1}

$B_0=-B_1$

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

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

B_{0} = B_{1}

$B_0=B_1$

Segundo método

Isso implica mostrar que esse formalismo é equivalente ao comumente usado no contexto de derivação das desigualdades no CHSH.

Denote com o número obtido substituindo em por , respectivamente, e da mesma forma para . Por exemplo, fornece . Observe que, nesse mapeamento, temos as identidades Podemos escrever $\tilde A_x\equiv 1-2A_x$ $0,1$ $A_x$ $+1,-1$ $\tilde B_y$ $A_x=0$ $\tilde A_x=+1$

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

$A_x\oplus B_y=(1-\tilde A_x\tilde B_y)/2.$

P_{S} = \frac{1}{2} [4 - {\tilde{UMA}}_{0 0} {\tilde{B}}_{0 0} - {\tilde{UMA}}_{0 0} {\tilde{B}}_{1} - {\tilde{UMA}}_{1} {\tilde{B}}_{0 0} + {\tilde{UMA}}_{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,$ onde definimos que você pode reconhecer como equivalente ao operador usado ao discutir as desigualdades no CHSH.

S \equiv {\tilde{UMA}}_{0 0} {\tilde{B}}_{0 0} + {\tilde{UMA}}_{0 0} {\tilde{B}}_{1} + {\tilde{UMA}}_{1} {\tilde{B}}_{0 0} - {\tilde{UMA}}_{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,$

\hat{S}

$\hat S$

Os argumentos padrão agora fornecem e, portanto, e, finalmente, (ou mais precisamente ). $S=\pm 2$ $\lvert S\rvert\le 2$ $P_{\mathcal S}\ge1$ $P_{\mathcal S}\in\{1,3\}$

glS
fonte

Pois "misturar várias dessas estratégias com alguma aleatoriedade certamente não pode dar um resultado melhor" é isso porque podemos pré-gerar uma sequência aleatória de bits e fornecer isso como entrada para o processo, e é computacionalmente equivalente a gerar uma aleatória string enquanto o processo está em execução?

ahelwer 8/01/19

@ahelwer Não sei bem o que você quer dizer. Eu acho que é simplesmente que você tem apenas um pequeno número de "estratégias" possíveis neste cenário, "estratégia" aqui significando relações entre entradas e saídas. A condição de localidade impede a comunicação entre Alice e Bob, portanto, essas estratégias se reduzem a combinações de estratégias locais. Não há realmente nada que se possa fazer em uma situação tão restritiva. A & B examinam suas entradas e produzem saídas. Se alguma saída produzida às vezes está errada, como a produção de um resultado não determinístico pode mudar isso?

GLS

Não acredito que um resultado não determinístico possa mudar as coisas, mas estou interessado em alguma prova / justificativa disso.

ahelwer 9/01/19

é nisso que tenho tentado provar que acredito. Eu acho que sua confusão pode surgir ao pensar em termos de quão eficientemente uma determinada estratégia pode ser alcançada. Isto não é, contudo, o que é considerado aqui. Não nos importamos como a A&B possa implementar uma estratégia real (embora a "implementação" seja bastante trivial nesse caso), estamos apenas considerando a probabilidade de vitória de cada estratégia. Como estamos explorando todas as estratégias que a A&B pode empregar, não há realmente espaço para melhorias adicionais. Existem literalmente apenas 16 maneiras de jogar este jogo

glS

Acho que não estou confuso, apenas estou interessado em uma justificativa do porquê podemos reduzir a análise ao caso determinístico (as 16 maneiras de jogar o jogo) e ignorar todas as estratégias não determinísticas. Novamente, não acredito que isso mude as coisas, mas quero saber a prova disso.

ahelwer 15/01/19

No jogo CHSH, temos 2 jogadores Alice e Bob. Podemos provar, na forma de um par de TMs sem comunicação, que recebe como entrada os bits aleatórios independentes xey mais uma sequência de bits compartilhada arbitrariamente, que ALice e Bob vencem o jogo CHSH com probabilidade superior a 75%.

Fazemos as perguntas de Alice e Bob xey com probabilidade p (xy), elas dão as respostas aeb. As regras do jogo são indicadas usando que assume o valor "1" se aeb forem as respostas vencedoras. A probabilidade de Alice e Bob ganharem o jogo é maximizada em todas as estratégias possíveis Onde é a probabilidade de Alice e Bob produzirem respostas aeb dadas x e y. $V(a,b|x,y)$ $P_{win} = max_{strategy} \sum_{x,y} p(x,y) | \sum_{a,b} V(a,b|x,y) p(a,b|x,y).$ $p(a,b|x,y)$

Em termos de probabilidades, há uma distinção entre um prob determinístico clássico e uma probabilidade ramdoness compartilhada clássica. Um stratey clássica determinista é dada pelas funções e que tomar a perguntas x e y. $f_{A}(x) = a$ $f_{B}(y) = b$

Se compartilhamos a aleatoriedade, outra string r é usada com uma probabilidade de compartilhamento . Classicamente Alice e Bob só pode aplicar funções e Isto dá Nesse caso, a probabilidade de ganhar o jogo é $p(r)$ $a = f_{A}(x,r)$ $b = f_{b}(y,r)$ $p(a,b|x,y) = \sum_{x,y}^{} (p(r)) p(a,b|x,y,r)$

$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)$ . Nesse caso de randomnes compartilhados, temos um termo extra com a string r. Alice e Bob podem corrigir o melhor possível r dada uma estratégia determinística para a e b. Portanto, é possível executar um algoritmo em uma máquina de Turing usando uma string r de acordo com a configuração de teste na imagem. Problema: como encontramos a melhor string possível r?

Outra maneira de ver isso é dizer que a corda r como uma aleatoriedade compartilhada é referida como uma variável escondida na física. Portanto, a teoria da variável oculta é equivalente a usar uma corda r em uma máquina de turing. Portanto, é melhor usarmos uma prova da desigualdade de CHSH. Além disso, podemos comparar resultados arbitrários de HVT (linha tracejada) e QM para um experimento fotônico.

Uma prova compacta da desigualdade de CHSH baseada em uma variável oculta pode ser encontrada no artigo Fótons emaranhados, não-localidade e desigualdades de Bell no laboratório de graduação.

Bram
fonte