Há uma parábola famosa sobre um grupo de cegos que encontra um elefante pela primeira vez. O primeiro cego, que estava com a mão na lateral do elefante, disse que era como se fosse um muro enorme. O segundo cego, abraçando a perna do elefante, exclamou que certamente era um tronco de árvore gigantesco. O terceiro, apalpando o rabo do elefante, declarou que devia ser uma corda grossa. Segue-se um desentendimento veemente, mas depois de um tempo os cegos finalmente percebem que, embora cada pessoa estivesse parcialmente correta, há muito mais no elefante do que se pensava inicialmente.

No mês passado, Zhengfeng, Anand, Thomas, John e eu postamos PImáx* = RE para arXiv. O papel parece muito com o elefante da fábula – e não apenas por causa do número de páginas! Para um cientista da computação, o artigo trata ostensivamente da complexidade das provas interativas. Para um físico quântico, trata-se de modelos matemáticos de emaranhamento quântico. Para o matemático, existe uma alegada resolução para um problema antigo em álgebras de operadores. Tal como os cegos da parábola, cada um sente uma pequena parte de um novo fenómeno. Como a parede, o tronco da árvore e a corda se encaixam?

Tentarei traçar o contorno do elefante: ele começa com um mistério na teoria da complexidade quântica, percorre os fundamentos matemáticos da mecânica quântica e chega a uma questão profunda sobre álgebras de operadores.

Em 2004, os cientistas da computação Cleve, Hoyer, Toner e Watrous estavam pensando sobre uma coisa engraçada chamada jogos não-locais. Um jogo não local envolve três partes: dois jogadores cooperantes chamados Alice e Bob, e alguém chamado verificador. O verificador testa um par de perguntas aleatórias e envia para Alice (que responde com resposta ), E para Bob (que responde com resposta ). O verificador então usa alguma função isso diz a ela se os jogadores venceram, com base em suas perguntas e respostas.

Todas as três partes conhecem as regras do jogo antes de começar, e o objetivo de Alice e Bob é maximizar sua probabilidade de ganhar o jogo. Os jogadores não têm permissão para se comunicar uns com os outros durante o jogo, então não é uma tarefa trivial para eles coordenar uma estratégia ideal (ou seja, como eles devem responder individualmente às perguntas do verificador) antes do jogo começar.

O exemplo mais famoso de jogo não local é o jogo CHSH (que já fez várias aparições neste blog): neste jogo, o verificador envia um bit uniformemente aleatório para Alice (que responde com um pouco ) e um bit uniformemente aleatório para Bob (que responde com um pouco ). Os jogadores ganham se (em outras palavras, a soma de seus bits de resposta é igual ao produto dos bits de entrada módulo ).

Qual é a probabilidade máxima de vitória de Alice e Bob? Bem, depende do tipo de estratégia que eles usam. Se eles usarem uma estratégia que possa ser modelada por clássico física, então sua probabilidade de vitória não pode exceder (chamamos isso de valor clássico do CHSH). Por outro lado, se utilizarem uma estratégia baseada em quantum física, Alice e Bob podem fazer melhor compartilhando dois bits quânticos (qubits) que são enredada. Durante o jogo, cada jogador mede seu próprio qubit (onde a medição depende da pergunta recebida) para obter respostas que ganhem o jogo CHSH com probabilidade (chamamos isso de valor quântico do CHSH). Portanto, mesmo que os qubits emaranhados não permitam que Alice e Bob se comuniquem, o emaranhamento lhes dá uma maneira de vencer com maior probabilidade! Em termos técnicos, as suas respostas são mais correlacionado do que é possível classicamente.

O jogo CHSH vem da física e foi originalmente formulado não como um jogo envolvendo Alice e Bob, mas sim como um experimento envolvendo dois dispositivos espacialmente separados para testar se existem correlações mais fortes do que as clássicas na natureza. Esses experimentos são conhecidos como Testes de campainha, em homenagem a John Bell. Em 1964, ele provou que as correlações do emaranhamento quântico não podem ser explicadas por nenhuma “teoria das variáveis ​​ocultas locais” – em outras palavras, uma teoria clássica da física.¹ Ele então mostrou que um teste de Bell, como o jogo CHSH, fornece um teste estatístico simples para a presença de correlações não locais entre sistemas separados. Desde a década de 1960, numerosos testes de Bell foram conduzidos experimentalmente e o veredicto é claro: a natureza não se comporta de maneira clássica.

Cleve, Hoyer, Toner e Watrous notaram que jogos não locais/testes de Bell podem ser vistos como uma espécie de prova interativa multiprovadora. Na teoria da complexidade, as provas interativas são protocolos onde alguns provadores estão tentando convencer um verificador de uma solução para um cálculo longo e difícil, e o verificador está tentando determinar com eficiência se a solução está correta. Num teste de Bell, pode-se pensar nos provadores como se estivessem tentando convencer o verificador de uma declaração física: que eles possuem emaranhamento quântico.

Com as lentes computacionais firmemente focadas em jogos não locais, torna-se natural perguntar sobre o complexidade de jogos não locais. Especificamente, qual é a complexidade de aproximar a probabilidade ótima de vitória em um determinado jogo não local? ? Na linguagem da complexidade, isso é formulado como uma questão sobre a caracterização da classe PIM* (pronuncia-se “estrela M-I-P”). Esta também é uma questão bem motivada para um experimentalista conduzindo testes de Bell: no mínimo, eles gostariam de determinar se (a) os jogadores quânticos podem se sair melhor do que os jogadores clássicos e (b) qual pode ser a melhor estratégia quântica possível. alcançar?

Estudar esta questão no caso de jogadores clássicos levou a alguns dos resultados mais importantes na teoria da complexidade, tais como PImáx = NEXP e os votos de Teorema PCP. Na verdade, o Teorema PCP diz que é NP-difícil aproximar o valor clássico de um jogo não local (ou seja, a probabilidade máxima de vitória dos jogadores clássicos) com uma precisão aditiva constante (digamos ). Assim, supondo que P não é igual a NP, não devemos esperar um algoritmo de tempo polinomial para isso. No entanto, é fácil perceber que existe um algoritmo de “força bruta” para este problema: tomando tempo exponencial para enumerar todas as estratégias determinísticas possíveis dos jogadores, pode-se calcular com exatidão o valor clássico dos jogos não locais.

Ao considerar jogos com jogadores emaranhados, no entanto, nem sequer fica claro se existe um algoritmo de “força bruta” semelhante que resolva isso. qualquer quantidade de tempo — esqueça o tempo polinomial; mesmo se nos permitirmos uma quantidade de tempo exponencial, duplamente exponencial, da função de Ackermann, ainda não sabemos como resolver este problema de aproximação de valor quântico. O problema é que não existe um limite superior conhecido para o quantidade de emaranhamento que é necessário para os jogadores jogarem um jogo não-local. Por exemplo, para um determinado jogo , uma estratégia quântica ideal requer um qubit, dez qubits ou qubits de emaranhamento? Sem qualquer limite superior, um algoritmo de “força bruta” não saberia o tamanho da estratégia quântica a ser pesquisada – ele continuaria enumerando estratégias cada vez maiores na esperança de encontrar uma melhor.

Assim, aproximar o valor quântico pode nem mesmo ser solucionável em princípio! Mas poderia clientes ser incomputável? Talvez simplesmente não tenhamos encontrado a ferramenta matemática certa para fornecer um limite superior para a dimensão - talvez apenas precisemos de encontrar alguma variante inteligente de, digamos, Johnson-Lindenstrauss ou alguma outra técnica de redução de dimensão.²

Em 2008, houve um progresso promissor em direção a uma solução algorítmica para este problema. Dois artigos [DLTW, NPA] (aparecendo no arXiv no mesmo dia!) mostrou que um algoritmo baseado em programação semidefinida pode produzir uma sequência de números que convergem para algo chamado valor do operador de comutação de um jogo não local.³ Se alguém pudesse mostrar que o valor do operador comutado e o valor quântico de um jogo não local coincidem, então isso produziria um algoritmo para resolver este problema de aproximação!

Perguntar se este operador comutado e os valores quânticos são os mesmos, no entanto, leva-nos imediatamente ao precipício de alguns mistérios profundos na física matemática e nas álgebras de operadores, muito distantes da ciência da computação e da teoria da complexidade. Isso nos leva à próxima parte do elefante.

O mistério sobre o valor quântico versus o valor do operador comutado de jogos não locais tem a ver com duas maneiras diferentes de modelar Alice e Bob na mecânica quântica. Como mencionei anteriormente, a física quântica prevê que a probabilidade máxima de vitória, digamos, no jogo CHSH, quando Alice e Bob compartilham o emaranhamento, é de aproximadamente 85%. Como acontece com qualquer teoria física, essas previsões são feitas usando alguma estrutura matemática – regras formais para modelar experimentos físicos como o jogo CHSH.

Em uma típica teoria da informação quântica livro didático, os jogadores no jogo CHSH são geralmente modelados da seguinte maneira: o dispositivo de Alice é descrito como espaço de estado (todos os estados possíveis em que o dispositivo pode estar), um determinado estado da , e um conjunto de operadores de medição (operações que podem ser realizadas pelo dispositivo). Não é necessário saber formalmente o que são essas coisas; a característica importante é que essas três coisas são suficientes para fazer qualquer previsão sobre o dispositivo de Alice – pelo menos quando tratadas isoladamente. Da mesma forma, o dispositivo de Bob pode ser descrito usando seu próprio espaço de estados , Estado e operadores de medição .

No entanto, no jogo CHSH, queremos fazer previsões sobre os dispositivos de Alice e Bob. juntos. Aqui os livros didáticos dizem que Alice e Bob são descritos em conjunto pelo produto tensorial formalismo, que é uma forma matemática natural de “juntar espaços separados”. Seu espaço de estado é denotado por . O estado conjunto a descrição dos dispositivos vem deste espaço de produto tensorial. Quando Alice e Bob fazem suas medições locais independentemente, isso é descrito por um operador de medição do produto tensorial dos operadores de e . As estranhas correlações da mecânica quântica surgem quando o seu estado conjunto is enredada, ou seja, não pode ser escrito como um estado bem definido do lado de Alice combinado com um estado bem definido do lado de Bob (mesmo que o espaço de estados em si seja dois espaços independentes combinados!)

O modelo de produto tensorial funciona bem; ele satisfaz as propriedades naturais que você deseja do experimento CHSH, como a restrição de que Alice e Bob não podem sinalizar instantaneamente um para o outro. Além disso, as previsões feitas neste modelo correspondem com muita precisão aos resultados experimentais!

Esta não é toda a história, no entanto. O formalismo do produto tensorial funciona muito bem em mecânica quântica não relativística, onde as coisas se movem lentamente e as energias são baixas. Para descrever cenários físicos mais extremos – como quando partículas são esmagadas umas contra as outras a velocidades próximas da da luz no Grande Colisor de Hádrons – os físicos recorrem aos mais poderosos teoria quântica de campos. No entanto, a noção de separação espaço-temporal em cenários relativísticos fica especialmente complicado. Em particular, ao tentar descrever sistemas de mecânica quântica, não é mais evidente como atribuir a Alice e Bob seus próprios espaços de estados independentes e, portanto, não está claro como colocar Alice e Bob relativísticos na estrutura do produto tensorial!

Na teoria quântica de campos, a localidade é descrita usando o modelo de operador pendular. Em vez de atribuir a Alice e Bob seus próprios espaços de estado individuais e depois tensioná-los juntos para obter um espaço combinado, o modelo do operador comutado estipula que há apenas um solteiro espaço monolítico para Alice e Bob. Seu estado conjunto é descrito usando um vetor da , e os operadores de medição de Alice e Bob atuam sobre . A restrição de que eles não conseguem se comunicar é capturada pelo fato de que os operadores de medição de Alice comutar com os operadores de Bob. Em outras palavras, a ordem em que os jogadores realizam suas medições no sistema não importa: Alice medindo antes de Bob, ou Bob medindo antes de Alice, ambos produzem os mesmos resultados estatísticos. A localidade é imposta por meio da comutatividade.

A estrutura do operador comutado contém a estrutura do produto tensorial como um caso especial⁴, então é mais geral. O modelo do operador comutado poderia permitir correlações que não podem ser capturadas pelo modelo de produto tensorial, mesmo aproximadamente⁵⁶? Esta questão é conhecida como O problema de Tsirelson, em homenagem ao falecido matemático Boris Tsirelson.

Existe uma maneira simples, mas útil, de formular essa questão usando jogos não locais. O que chamamos de “valor quântico” de um jogo não local (denotado por ) realmente se refere ao supremo de probabilidades de sucesso sobre estratégias de produto tensorial para Alice e Bob. Se eles usarem estratégias do modelo mais geral de operadores pendulares, então chamaremos sua probabilidade máxima de sucesso de valor do operador de comutação of (denotado por ). Como as estratégias de produto tensorial são um caso especial de estratégias de operadores comutadores, temos a relação para todos os jogos não locais .

Poderia haver um jogo não local cujo valor do produto tensorial é diferente do valor do operador de comutação? Com ironia: existe um jogo que Alice e Bob poderiam ter mais sucesso se usassem o emaranhamento quântico em velocidades próximas à da luz? É difícil encontrar até mesmo um jogo candidato plausível para o qual os valores dos operadores quântico e comutado possam diferir. O jogo CHSH, por exemplo, tem o mesmo valor de operador quântico e de comutação; isso foi provou por Tsirelson.

Se o produto tensorial e os modelos do operador comutado forem os mesmos (ou seja, a resolução “positiva” do problema de Tsirelson), então, como mencionei anteriormente, isso teria ramificações inesperadas: haveria um algoritmo para aproximar o valor quântico de jogos não locais.

Como funciona esse algoritmo? Ele vem em duas partes: um procedimento para pesquise abaixo, e um para pesquisar de cima. O algoritmo “busca por baixo” calcula uma sequência de números onde é (aproximadamente) a melhor probabilidade de vitória quando Alice e Bob usam um estratégia de produto tensor -qubit. Para fixo , o número pode ser calculado enumerando (uma discretização) o espaço de todos os possíveis estratégias -qubit. Isso leva um duplamente exponencial quantidade de tempo em - mas pelo menos este ainda é um tempo finito! Esse algoritmo ingênuo de “força bruta” avançará lentamente, calculando uma sequência de probabilidades de vitória cada vez melhores. Temos a garantia de que no limite como vai para o infinito, a sequência converge para o valor quântico . É claro que a questão é que o procedimento de “busca por baixo” nunca sabe quão próximo está do verdadeiro valor quântico.

É aqui que entra a “busca de cima”. Este é um algoritmo que calcula uma sequência diferente de números onde cada é um limite superior no valor do operador de comutação , e além disso como vai para o infinito, eventualmente converge para . Além disso, cada pode ser calculado por uma técnica conhecida como otimização semidefinida; isso foi mostrado pelo dois papéis Eu mencionei.

Vamos juntar as peças. Se os valores do operador quântico e comutado de um jogo coincidem (ou seja, ), então podemos executar os procedimentos “busca por baixo” e “pesquisa por cima” em paralelo, intercalando o cálculo do e . Como é garantido que ambos convergirão para o valor quântico, em algum ponto o limite superior chegará dentro de alguns para o limite inferior , e assim teríamos nos concentrado em (uma aproximação de) . Aí está: um algoritmo para aproximar o valor quântico dos jogos.

Tudo o que resta a fazer, certamente, é resolver o problema de Tsirelson afirmativamente (que as correlações de operadores comutados podem ser aproximadas por correlações de produto tensorial), e então poderíamos colocar esta questão incómoda sobre o valor quântico de lado. Certo?

No final da década de 1920, o extraordinário polímata John von Neumann formulou o primeiro quadro matemático rigoroso para a mecânica quântica recentemente desenvolvida. Esta estrutura, agora familiar aos físicos e teóricos da informação quântica em todo o mundo, postula que os estados quânticos são vetores num espaço de Hilbert, e as medições são operadores lineares que atuam nesses espaços. Não demorou muito para que von Neumann percebesse que havia uma teoria muito mais profunda de operadores nos espaços de Hilbert esperando para ser descoberta. Com Francis Murray, na década de 1930, ele começou a desenvolver uma teoria de “anéis de operadores” – hoje eles são chamados Álgebras de von Neumann.

Desde então, a teoria das álgebras de operadores floresceu em uma área rica e bela da matemática. Permanece inseparável da física matemática, mas estabeleceu conexões profundas com assuntos como a teoria dos nós e a teoria dos grupos. Um dos objetivos mais importantes em álgebras de operadores tem sido fornecer uma classificação das álgebras de von Neumann. Em sua série de artigos sobre o assunto, Murray e von Neumann mostraram pela primeira vez que classificar as álgebras de von Neumann se reduz à compreensão de suas fatores, os átomos a partir dos quais todas as álgebras de von Neumann são construídas. Então, eles mostraram que os fatores das álgebras de von Neumann vêm em uma de três espécies: tipo , Tipo , e digite . Tipo fatores foram completamente classificados por Murray e von Neumann, e eles fizeram muito progresso na caracterização de certos tipos fatores. No entanto, o progresso estagnou até à década de 1970, quando Alain Connes apresentou uma classificação do tipo fatores (trabalho pelo qual mais tarde receberia a Medalha Fields). No mesmo artigo de classificação de 1976, Connes faz uma observação casual sobre algo chamado tipo fatores⁷:

Construímos agora uma incorporação de para dentro . Aparentemente, tal incorporação deveria existir para todos fatores.

Esta linha, escrita de maneira quase descartável, acabou sendo chamada “Problema de incorporação de Connes”: faz todo separável fator incorporado em um ultrapoder do hiperfinito fator? Parece que Connes supõe que sim (e, portanto, isso também é chamado de “incorporação de Connes”. conjetura“). Desde 1976, este problema tornou-se uma questão central das álgebras de operadores, com numerosas formulações equivalentes e conseqüências em toda a matemática.

Em 2010, dois papéis (aparecendo novamente no arXiv no mesmo dia!) mostrou que o alcance da conjectura de incorporação de Connes remonta aos fundamentos da mecânica quântica. Se o problema de incorporação de Connes tiver uma resposta positiva (ou seja, existe uma incorporação), então o problema de Tsirelson (ou seja, se o operador de comutação pode ser aproximado por correlações de produto tensorial) tb tem uma resposta positiva! Mais tarde foi mostrando por Ozawa que o problema de incorporação de Connes é na verdade equivalente para o problema de Tsirelson.

Lembre-se de que a nossa abordagem para calcular o valor dos jogos não locais dependia da obtenção de uma resposta positiva ao problema de Tsirelson. A sequência de artigos [NPA, DLTW, Fritz, JNPPSW] juntos mostram que resolver - de uma forma ou de outra - se esse algoritmo de busca de baixo e de cima funciona basicamente resolveria a conjectura de incorporação de Connes. O que começou como uma pergunta engraçada na periferia da ciência da computação e da teoria da informação quântica se transformou em um ataque a um dos problemas centrais da álgebra de operadores.

Agora voltamos ao ponto de partida: a complexidade dos jogos não locais. Vamos dar um passo para trás e tentar entender o elefante.

Mesmo para um teórico da complexidade, “PImáx* = RE”pode parecer esotérico. As classes de complexidade PIM* e RE referem-se a um conjunto desconcertante de conceitos: há Alice, Bob, máquinas de Turing, verificadores, provas interativas, emaranhamento quântico. Qual é o significado da igualdade dessas duas classes?

Primeiro, diz que o O problema da parada tem uma prova interativa envolvendo provadores quânticos emaranhados. No problema da parada, você deseja decidir se uma máquina de Turing , se você começasse a executá-lo, acabaria terminando com uma resposta bem definida ou ficaria preso em um loop infinito. Alan Turing mostrou que esse problema é indecidível: não existe um algoritmo que possa resolver este problema em geral. Em termos gerais, a melhor coisa que você pode fazer é simplesmente ligar o botão liga / desliga para e espere para ver se ele eventualmente para. Se fica preso em um loop infinito - bem, você ficará esperando para sempre.

PImáx* = RE mostra com a ajuda dos todo-poderosos Alice e Bob, um verificador com tempo limitado pode executar uma prova interativa para “atalho” a espera. Dada a máquina de Turing descrição de (seu “código-fonte”), o verificador pode calcular com eficiência uma descrição de um jogo não local cujo comportamento reflete o de . Se eventualmente parar (o que poderia acontecer depois de um milhão de anos), então existe uma estratégia para Alice e Bob que faz com que o verificador aceite com probabilidade . Em outras palavras, . Se fica preso em um loop infinito, então não importa qual estratégia Alice e Bob usem, o verificador sempre rejeita com alta probabilidade, então está perto de .

Ao jogar este jogo não-local, o verificador pode obter evidência estatística que é uma máquina de Turing que eventualmente termina. Se o verificador jogar e os provadores vencerem, então o verificador deverá acreditar que é provável que pára. Se perderem, o verificador conclui que não há provas suficientes de que pára⁸. O verificador nunca é realmente executado neste jogo; ela transferiu a tarefa para Alice e Bob, que podemos presumir serem deuses computacionais capaz de realizar cálculos de milhões de anos instantaneamente. Para eles, o desafio é, em vez disso, convencer o verificador de que se ela foram esperar milhões de anos, ela testemunharia o fim de . Incrivelmente, a quantidade de trabalho colocado pelo verificador na prova interativa é de treinadores em Entrevista Motivacional do tempo que leva para parar!

O fato de o problema da Halting ter uma prova interativa parece quase absurdo: se o problema da Halting é insolúvel, por que deveríamos esperar que ele fosse verificável? Embora a teoria da complexidade tenha nos ensinado que pode haver uma grande lacuna entre a complexidade da verificação e a da pesquisa, sempre houve uma diferença de eficiência: se as soluções para um problema podem ser verificadas de forma eficiente, então as soluções também podem ser encontradas (embora com um custo computacional drasticamente maior). PImáx* = RE mostra que, com o emaranhamento quântico, pode haver um abismo de computabilidade entre verificar soluções e encontrá-las.

Agora vamos nos voltar para as consequências de não complexidade de PImáx* = RE. O fato de podermos codificar o problema da parada em jogos não locais também nos diz imediatamente que não existe nenhum algoritmo para aproximar o valor quântico. Suponha que houvesse um algoritmo que pudesse aproximar . Então, usando a transformação das máquinas de Turing para jogos não locais mencionada acima, poderíamos usar esse algoritmo para resolver o problema da parada, o que é impossível.

Agora os dominós começam a cair. Isto significa que, em particular, o algoritmo proposto de “busca de baixo”/”pesquisa de cima” não podes conseguir aproximar . Deve haver um jogo , então, para o qual o valor quântico é diferente do valor do operador comutado. Mas isto implica que o problema de Tsirelson tem uma resposta negativa e, portanto, a conjectura de incorporação de Connes é falsa.

Nós apenas esboçamos os contornos mais básicos deste elefante, mas é bastante desafiador mantê-lo na mente de uma só vez.⁹. Esta história está entrelaçada com alguns dos desenvolvimentos mais fundamentais do século passado: a mecânica quântica moderna, as álgebras de operadores e a teoria da computabilidade nasceram na década de 1930. Einstein, Podolsky e Rosen escreveram seu artigo marcante questionando a natureza do emaranhamento quântico em 1935, e John Bell descobriu seu famoso teste e desigualdade em 1964. Connes formulou sua conjectura nos anos 70, Tsirelson fez suas contribuições para os fundamentos da mecânica quântica. nos anos 80, e mais ou menos na mesma época, os cientistas da computação inventavam a teoria das provas interativas e das provas verificáveis ​​probabilisticamente (PCPs).

Não dissemos nada sobre a prova de PImáx* = RE ainda (este pode ser o assunto de futuras postagens no blog), mas é inegavelmente um produto da teoria da complexidade. A linguagem das provas interativas e das máquinas de Turing não é apenas conveniente, mas necessária: em sua essência PImáx* = RE é o Teorema PCP clássico, com a ajuda do emaranhamento quântico, recorrido ao infinito.

O que está acontecendo nesta prova? Quais partes são fundamentais e quais partes são desnecessárias? Qual é o cerne disso que se relaciona com a conjectura de incorporação de Connes? Existem outras consequências deste resultado de incomputabilidade? Estas são questões a serem exploradas nos próximos dias e meses, e as respostas que encontraremos serão fascinantes.

Agradecimentos. Obrigado a William Slofstra e Thomas Vidick pelos comentários úteis sobre esta postagem.

Fonte: https://quantumfrontiers.com/2020/03/01/the-shape-of-mip-re/