👏🏽 💛 👉🏽 MIP * = RE: evidências de época do campo da ciência da computação que causaram o efeito dominó na física e na matemática 🚮 😧 😛

Os cientistas da computação alcançaram novas fronteiras na verificação de soluções para problemas por métodos computacionais. Ao mesmo tempo, eles encontraram respostas para as questões abertas mais importantes da mecânica quântica e da matemática pura.

Em 1935, Albert Einstein, trabalhando com Boris Podolsky e Nathan Rosen, investigou a possibilidade aberta pelas novas leis da física quântica: duas partículas podem estar em um estado emaranhado quando mesmo grandes distâncias não violam sua interconexão. No ano seguinte, Alan Turing formulou a primeira teoria geral da computação e provou que existem problemas que nunca podem ser resolvidos por computadores. Essas duas idéias revolucionaram os campos da ciência aos quais se relacionam. Além disso, parecia que eles não tinham nada a ver um com o outro. Mas agora a prova

MIP * = RE combinou-os, o que levou à solução de muitos problemas no campo da ciência da computação, física e matemática.

Computadores quânticos executam cálculos usando bits quânticos emaranhados (qubits), em vez de zeros e uns clássicos. Novas evidências indicam que esses computadores, teoricamente, podem ser usados para testar soluções para um grande número de problemas. A conexão entre o entrelaçamento quântico e a computação tradicional foi uma grande surpresa para muitos pesquisadores.

Miguel Navascués é um estudante de física quântica no Instituto de Ótica Quântica e Informação Quântica em Viena. "Foi uma surpresa completa", disse ele, comentando as evidências.

Os co-autores da evidência estabelecem o objetivo de definir os limites da abordagem para verificar soluções para problemas computacionais. Essa abordagem envolve emaranhamento quântico. Tendo descoberto essas fronteiras, os pesquisadores chegaram à solução de dois outros problemas, que eram quase um subproduto de seu trabalho. Estamos falando da hipótese de Zirelson na física sobre modelagem matemática do entrelaçamento quântico e o problema relacionado em matemática pura - o problema de Conn na teoria da álgebra de von Neumann (problema de incorporação de Conn).

Como resultado, os resultados da aplicação das evidências em matemática e física causaram algo como o efeito dominó.

“Todas as idéias pertencem ao mesmo período. É bom vê-los se reunindo novamente de uma maneira tão espetacular ”, diz Henry Yuen) da Universidade de Toronto - um dos co-autores da evidência. Além dele, neste trabalho participaram Chzhenfen Ji ( Zhengfeng of Ji ) da Universidade de Tecnologia de Sydney, John Wright ( John Wright ) da Universidade do Texas em Austin, Anand Natarajan ( Anand Natarajan ) e Thomas Vidic ( Thomas Vidick ) do California Institute of Technology. Todos os cinco cientistas trabalham no campo da ciência da computação.

Tarefas insolúveis

Turing, mesmo antes do advento dos computadores, lançou as bases sobre as quais as reflexões sobre a computação são construídas. E ele, ao mesmo tempo, mostrou que existe um certo problema que, que é comprovável, os computadores não conseguem resolver. Esse é o chamado problema de desligamento.

Normalmente, os programas de computador recebem algo na entrada e geram saída. Mas às vezes eles ficam presos em ciclos intermináveis, o que significa que nunca param. Quando isso acontece, há apenas uma maneira de sair dessa situação. De acordo com Henry Yuen, você precisa interromper o programa manualmente. Você só precisa pôr um fim ao trabalho dela.

Turing provou que não existe um algoritmo universal capaz de descobrir se um programa será interrompido. Para descobrir, você precisa executar o programa.

Henry Yuen, Thomas Widick, Zhengfeng Ji, Anand Natarajan, John Wright

“Você esperou um milhão de anos e o programa não parou. Talvez você só precise esperar 2 milhões de anos? Não há como contar com antecedência ", diz William Slofstra ( William Slofstra ), matemático da Universidade de Waterloo.

Turing, do ponto de vista técnico, provou que o problema do desligamento é insolúvel. Mesmo o computador mais poderoso que você pode imaginar não é capaz de lidar com isso.

Depois de Turing, os cientistas da computação começaram a classificar outras tarefas por sua complexidade. Tarefas mais complexas exigem mais poder de processamento - mais tempo e memória do processador. Este é um estudo da complexidade computacional dos algoritmos.

Como resultado, qualquer problema coloca duas grandes questões para os pesquisadores: “Quão difícil é resolvê-lo? Qual é a dificuldade de verificar se a solução resultante está correta? ”

Interrogatório da decisão através de interrogatório

Se as tarefas forem relativamente simples - suas soluções podem ser verificadas independentemente. Mas quando as tarefas se tornam mais complicadas, até a verificação dos resultados de sua solução pode ser incrivelmente difícil. Apesar disso, em 1985, os cientistas da computação decidiram que era possível construir confiança na exatidão da resposta, mesmo que não fosse possível confirmar isso por conta própria.

O método de verificação segue a lógica do interrogatório policial.

Se o suspeito contar uma história cuidadosamente pensada, o investigador provavelmente não será capaz de simplesmente pegar e encontrar a confirmação de cada um de seus detalhes. Mas, fazendo as perguntas certas, você pode pegar o suspeito em uma mentira ou confirmar a veracidade de sua história.

Em termos de ciência da computação, os dois lados do interrogatório são representados por dois computadores. O primeiro é um poderoso sistema de computação que oferece uma solução para o problema. Ele é chamado de testemunha. O segundo não é mais um dispositivo tão poderoso que faz perguntas ao testador para determinar se a resposta que ele oferece está correta. Este computador é chamado de verificador.

Considere um exemplo simples. Suponha que alguém (o verificador) sofra de daltonismo. Outra pessoa (a testemunha) afirma que as duas bolas são pintadas em cores diferentes e não são diferentes uma da outra. O verificador não pode verificar esta declaração em si. Mas, tendo construído o interrogatório de maneira inteligente, ele pode descobrir se é realmente assim.

Para fazer isso, você pode esconder as bolas atrás das costas e misturá-las. E então - pergunte ao provador sobre qual bola está em qual mão. Se eles são realmente diferentes, o provador deve sempre responder a essa pergunta corretamente. Mas, se tiverem a mesma cor, ou seja, parecerem exatamente iguais, metade das respostas do provador se revelará errada.

Thomas Widick diz que, se mais da metade das respostas do depoimento estiverem corretas, você pode ter certeza de que as bolas têm cores diferentes.

Ao fazer as perguntas do provador, você pode verificar as soluções de uma classe mais ampla de problemas do que você mesmo.

Em 1988, cientistas da computação examinaram uma situação em que existem dois provadores oferecendo soluções para o mesmo problema. No final, se houver dois suspeitos que possam ser interrogados, isso simplificará a divulgação do crime ou - a verificação da decisão, pois eles podem ser forçados a jogar um contra o outro.

Segundo Thomas Widick, isso dá ao verificador mais influência. Ele interroga, faz perguntas relacionadas, verifica as respostas. Se os suspeitos estão dizendo a verdade, suas respostas devem coincidir na maior parte do tempo. Se eles mentem, suas respostas frequentemente divergem.

Da mesma forma, os pesquisadores mostraram que, interrogando duas testemunhas separadamente, fazendo perguntas sobre as soluções encontradas, é possível verificar rapidamente as soluções de uma classe de problemas ainda mais extensa do que quando trabalham com um provador.

Os estudos da complexidade computacional dos algoritmos podem parecer puramente teóricos, mas estão intimamente relacionados ao mundo real. Os recursos que os computadores precisam para resolver problemas e verificar soluções - tempo e memória - são recursos físicos. Por esse motivo, novas descobertas na física podem mudar a abordagem do estudo da complexidade computacional.

Anand Natarajan diz que, se nos afastarmos da base física clássica das computações e escolhermos algo completamente diferente, como mecanismos quânticos, também obteremos uma nova teoria da complexidade computacional.

A nova evidência é o resultado final de uma colisão de cientistas da computação do século XXI com uma das idéias mais estranhas da física do século passado - com a idéia de entrelaçamento quântico.

Problema de Conn

Quando duas partículas são emaranhadas, elas de fato não se afetam. Não há relação causal entre suas ações. Einstein e seus co-autores trabalharam nessa idéia em um artigo de 1935. Posteriormente, físicos e matemáticos tentaram chegar a uma maneira matemática de descrever o que realmente significa emaranhamento quântico.

No entanto, esses esforços levaram a resultados mistos. Os cientistas criaram dois modelos matemáticos diferentes de emaranhamento. No entanto, não ficou claro se esses modelos são equivalentes entre si.

A presença de tal dissonância potencial, de maneira indireta, levou ao aparecimento de um problema importante no campo da matemática pura. Este é o problema de Conn na teoria das álgebras de von Neumann. No final, desempenhou o papel de algum tipo de “pista” da qual cinco cientistas da computação se aproveitaram na derivação de suas evidências.

A primeira maneira de modelar o emaranhamento quântico era perceber partículas como objetos espacialmente isolados um do outro. Suponha que uma dessas partículas esteja na Terra e a outra em Marte. A distância entre eles é algo que exclui uma relação causal entre eles (eles são causalmente separados). Isso é chamado de modelo de produto tensorial.

Mas em algumas situações, a separação causal de entidades não é totalmente óbvia. Como resultado, os matemáticos chegaram a uma segunda maneira mais geral de descrever a independência causal.

Quando a ordem na qual duas operações são executadas não afeta o resultado, a operação é chamada comutativa: 3x2 é o mesmo que 2x3. Neste segundo modelo, as partículas são emaranhadas quando suas propriedades são correlacionadas, mas a ordem na qual as medidas são feitas não importa. Pode-se fazer medições na partícula A para prever o momento da partícula B e vice-versa. De qualquer forma, o resultado será o mesmo. Isso é chamado de modelo de emaranhamento do operador de comutação.

Ambas as descrições de emaranhamento usam matrizes de números chamadas matrizes. Matrizes consistem em linhas e colunas. O modelo de produto tensorial utiliza matrizes com um número finito de linhas e colunas. O modelo do operador de comutação usa objetos mais gerais que funcionam como matrizes com um número infinito de linhas e colunas.

Com o tempo, os matemáticos começaram a estudar essas matrizes como objetos de interesse independente, não relacionados de maneira alguma ao mundo físico. De acordo com este trabalho, o matemático Alain Connes sugeriu em 1976 que deveria ser possível aproximar muitas matrizes de dimensão infinita usando matrizes de dimensão finita. Essa é uma das consequências do problema de Conn na teoria das álgebras de von Neumann.

Na década seguinte, o físico Boris Tsirelson formulou uma nova versão deste problema, que novamente o devolveu ao campo da física. Zirelson sugeriu que os modelos do produto tensorial e do operador pendular são aproximadamente equivalentes entre si. Essa afirmação faz sentido, uma vez que ambos os modelos, teoricamente, são duas maneiras diferentes de descrever o mesmo fenômeno físico. Trabalhos subseqüentes mostraram que, devido à conexão entre matrizes e modelos físicos, os problemas de Conn e Zirelson são indiretamente relacionados: se um for resolvido, o outro será resolvido.

Mas a solução para esses dois problemas veio de um lugar completamente inesperado.

Física dos jogos

Na década de 1960, o físico John Bell apresentou um teste para determinar se o entrelaçamento quântico é um fenômeno físico real, não um conceito teórico. O teste usou algo como um jogo, cujos resultados tornaram possível descobrir se certos mecanismos que não estão relacionados à física comum funcionam durante o jogo.

Mais tarde, os cientistas da computação perceberam que esse teste relacionado ao entrelaçamento quântico também pode ser usado como uma ferramenta para verificar soluções para problemas muito complexos.

Mas antes de prosseguir, vamos falar sobre o jogo. Imagine que existem dois jogadores: Alice e Bob, e também um campo de jogo 3x3. O apresentador atribui uma linha a Alice e solicita que ela insira 0 ou 1 em cada célula, para que sua soma dê um número ímpar. Bob recebe uma coluna que precisa ser preenchida com zeros e uns, para que a soma desse número. Eles vencerão se colocarem o mesmo número no local onde a linha e a coluna se cruzam. É impossível se comunicar com ele.

Em circunstâncias normais, o melhor que podem fazer é ganhar 89% do tempo. Mas se você levar em conta o fator de emaranhamento quântico, suas chances serão melhoradas.

Imagine que Alice e Bob tenham entrelaçado partículas quânticas. Eles fazem medições de suas partículas e usam os resultados para indicar o que escrever em cada célula - 0 ou 1. Como as partículas estão emaranhadas, os resultados da medição se correlacionam. E isso também significa que as ações dos jogadores serão interconectadas. Como resultado, acontece que eles sempre poderão ganhar o jogo.

Se houver números diferentes na célula onde a linha e a coluna se cruzam, o jogo será perdido. Se eles são os mesmos - ganhou.Portanto

, se dois jogadores tiverem surpreendentemente sucesso em jogar este jogo, podemos concluir que eles estão usando algo diferente do que a física clássica pode dar. Esses experimentos de "Bell" hoje são chamados de jogos "não locais", referindo-se à separação de jogadores. Os físicos, de fato, conduzem jogos semelhantes em laboratórios.

Henry Yuen diz que, ao longo dos anos, os cientistas realizaram experimentos para provar a realidade desses fenômenos assustadores.

Como na análise de qualquer jogo, você pode precisar descobrir com que frequência os jogadores podem vencer em um jogo não local, já que jogam da melhor maneira possível. Por exemplo, no caso de paciência, você pode calcular a frequência de vitórias possíveis de quem joga perfeitamente.

Mas em 2016, William Slofstra provou que não há algoritmo geral para calcular a probabilidade máxima exata de vitória para todos os jogos não locais. Como resultado, os pesquisadores fizeram a pergunta: é possível calcular pelo menos aproximadamente a porcentagem máxima de ganhos?

Os cientistas da computação chegaram à resposta usando os dois modelos de entrelaçamento quântico descritos acima. O algoritmo que usa o modelo de produto tensorial define o valor mínimo para o cálculo aproximado da probabilidade máxima de vitória para todos os jogos não locais. Outro algoritmo que usa o modelo do operador de comutação define o valor máximo.

A resposta dada pelas implementações desses algoritmos, quanto mais precisa, mais tempo o programa é executado. Se a hipótese de Zirelson for verdadeira, e esses dois modelos forem equivalentes, os limites inferior e superior devem se aproximar, transformando-se em um único valor que representa a probabilidade máxima aproximada de vitória.

Mas se a hipótese de Zirelson não for verdadeira e os dois modelos não forem equivalentes, então, de acordo com Henry Yuen, os limites superior e inferior sempre serão separados. E não haverá como calcular nem mesmo a porcentagem aproximada de ganhos para jogos não locais.

Cinco pesquisadores em seu novo trabalho aproveitaram o argumento sobre se os limites superior e inferior convergem e se a hipótese de Zirelson é verdadeira ou falsa. Eles fizeram isso com o objetivo de encontrar a resposta para a pergunta de em quais situações é possível verificar soluções para problemas computacionais.

Ajuda complexa

No início dos dois milésimos mil cientistas da computação, eles começaram a se perguntar como a gama de tarefas mudaria, cujas soluções podem ser verificadas “interrogando” dois provadores que possuem partículas intricadas.

Muitos cientistas pensam que a confusão prejudica a verificação. No final, será mais fácil para os dois "suspeitos" conciliarem testemunhos falsos se tiverem alguma maneira de coordenar as respostas.

Mas, nos anos seguintes, ficou claro que a afirmação oposta era verdadeira: "interrogando" provadores que possuem partículas intricadas, uma classe muito mais ampla de problemas pode ser verificada do que quando se trabalha com provadores que não possuem essas partículas.

Thomas Widick diz que o emaranhamento é uma maneira de criar correlações que parecem ajudar as testemunhas a mentir. Mas, de fato, esse fenômeno pode ser usado em proveito próprio.

Para entender como usá-lo, primeiro você precisa lidar com a escala quase sobrenatural de tarefas cujas soluções podem ser verificadas graças a este procedimento interativo.

Imagine um gráfico - um conjunto de pontos (vértices) conectados por linhas (faces). Você precisa descobrir se, usando três cores, é possível pintar os vértices, para que não haja dois vértices no gráfico conectados por uma face e ao mesmo tempo pintados na mesma cor. Se possível, esse gráfico é "tricolor".

Se você der a um par de evidências um gráfico muito grande, e eles disserem que é "tricolor", poderá se perguntar se há uma maneira de verificar a resposta deles.

No caso de gráficos muito grandes, seria impossível verificar a resposta diretamente. Em vez disso, você pode perguntar a cada um dos testadores qual a cor de um dos dois vértices conectados. Se cada um deles relatar cores diferentes e fornecer respostas semelhantes sempre que for solicitado, teremos confiança de que o gráfico é realmente "tricolor".

Mas mesmo essa estratégia de interrogação não funcionará em grandes gráficos com mais faces e vértices do que átomos no universo. Mesmo fazendo uma pergunta específica ("Diga-me a cor do vértice XYZ") se torna um problema insuportável para alguém que tenta verificar uma solução para um problema. A quantidade de dados necessária para simplesmente especificar o nome de um vértice específico é maior do que o verificador pode armazenar na memória disponível para ele.

Mas o entrelaçamento quântico possibilita um esquema de trabalho, na aplicação em que os próprios testadores formulam as perguntas.

“O verificador não precisa fazer perguntas. O verificador força os proponentes a formular essas perguntas de forma independente e respondê-las ”, diz John Wright.

O verificador precisa que os provadores relatem as cores dos vértices conectados. Se os vértices não estiverem conectados, as respostas às perguntas não informarão se o gráfico é "tricolor" ou não. Em outras palavras, o verificador precisa de testadores para fazer perguntas relacionadas. Um dos provadores pergunta sobre o topo do ABC e o segundo sobre o topo do XYZ. Supõe-se que os dois picos estejam conectados, apesar de nenhuma das provas saber em qual delas o outro “pensa”. (É semelhante à maneira como Alice e Bob esperam escrever o mesmo número na mesma célula, apesar de nenhum deles saber sobre com qual linha ou coluna da tabela a outra trabalha.)

Se dois provadores formulassem essas perguntas de maneira completamente independente, não haveria mecanismo para forçá-los a selecionar vértices conectados (correlacionados), fazendo-o de forma a permitir que o verificador verifique suas respostas. Mas essa correlação é exatamente o que o entrelaçamento quântico pode alcançar.

Thomas Widick diz que eles vão usar meandros para encaminhar praticamente todos os casos às testemunhas. Os cientistas fazem os testadores escolherem suas próprias perguntas.

No final deste procedimento, cada um dos provadores relata uma cor de vértice. O verificador verifica se essas cores são diferentes ou não. Se o gráfico é realmente "tricolor", os testadores nunca devem relatar a mesma cor.

De acordo com Henry Yuen, se o gráfico for "tricolor", os testadores poderão convencer o pesquisador de que isso é verdade.

Como se viu, esse procedimento de verificação é outro exemplo de jogo não local. Os revisores “vencem” se convencerem o pesquisador de que sua decisão está correta.

Em 2012, Thomas Widik e Tsuyoshi Ito) provou que é possível jogar uma grande variedade de jogos não locais usando provadores intrincados para testar soluções. Isso se aplica, no mínimo, ao mesmo número de tarefas que podem ser verificadas interrogando dois computadores clássicos. Assim, o uso de evidências confusas não prejudica a verificação. No ano passado, Anand Natarajan e John Wright provaram que a interação com testemunhas complexas realmente amplia a classe de problemas cujas soluções podem ser verificadas.

Mas os cientistas da computação não conheciam toda a gama de tarefas cujas soluções podem ser verificadas usando essa abordagem. Agora eles sabem disso.

efeito dominó

Em seu novo trabalho, cinco cientistas provaram que o "interrogatório" de testemunhas confusas torna possível verificar soluções para problemas insolúveis, incluindo a solução de um problema de desligamento.

Henry Yuen diz que modelos desse tipo têm recursos de verificação inimagináveis.

Mas a tarefa de parar é insolúvel. E esse fato foi a força motriz que levou à prova final.

Imagine que você entregou o programa a duas testemunhas confusas. Você perguntou a eles se esse programa nunca iria parar. Você está pronto para verificar suas respostas através de algum tipo de jogo não local. Os revisores geram perguntas e "vencem" com base na coordenação de suas respostas.

Se o programa realmente parar, os proponentes deverão poder vencer o jogo em 100% dos casos. Isso é semelhante a um exemplo de gráfico - se for realmente "tricolor", os provadores complicados nunca devem reportar a mesma cor para os vértices conectados. Se o programa nunca parar, os testadores devem vencer apenas por acaso - em 50% dos casos.

Isso significa que, se alguém solicitar que você determine a probabilidade máxima aproximada de ganhar para um jogo não local específico, primeiro você terá que resolver o problema de parada. Mas resolver este problema é impossível. Isso significa que é impossível encontrar o nível máximo aproximado de probabilidade de vitória para jogos não locais e também para o problema de parada.

E isso, por sua vez, significa que a hipótese de Tsirelson é falsa: os dois modelos de entrelaçamento quântico não são equivalentes. Se fossem equivalentes, seria possível reduzir os limites inferior e superior para o mesmo valor e calcular a probabilidade máxima aproximada de vitória.

David Pérez-García, da Universidade Complutense de Madri, diz que tal algoritmo não pode existir, como resultado, os dois [modelos] devem ser diferentes.

O novo trabalho prova que a classe de problemas cujas soluções podem ser verificadas com a ajuda de intrincados revisores quânticos, uma classe chamada MIP *, é exatamente igual à classe de problemas que não são mais complicados que o problema de parada - a classe RE. O título do artigo contém uma indicação concisa disso: “MIP * = RE”.

No decorrer da prova de que as duas classes de complexidade são iguais, os cientistas provaram que a hipótese de Tsirelson é falsa, o que, graças ao trabalho anterior, significa que a hipótese de Conn também é falsa.

Os pesquisadores que trabalham em seus respectivos campos ficaram surpresos com o fato de que soluções para esses problemas de larga escala foram obtidas graças a evidências do campo da ciência da computação, que, ao que parece, não estão relacionadas à matemática e à física.

Miguel Navazquez diz que, se visse um artigo com o título MIP * = RE, ele não pensaria que ela tinha algo em comum com o trabalho dele. Ele foi co-autor de um trabalho anterior que ligava as hipóteses de Zirelson e Conn. Para ele, foi uma surpresa completa.

Físicos e matemáticos quânticos estão apenas começando a dominar uma nova prova. Antes disso, os matemáticos estavam interessados na questão de saber se podem aproximar matrizes de dimensão infinita, usando grandes matrizes de dimensão finita. Agora, graças ao fato de a hipótese de Conn ter sido provada falsa, eles sabem que isso não pode ser feito.

"Seus resultados indicam que isso não é possível", disse William Slofstra.

Os cientistas da computação não procuraram analisar a hipótese de Conn. E, como resultado, eles não estão na melhor posição para explicar as possíveis conseqüências da solução desse problema.

“Pessoalmente, não sou matemático. "Não entendo muito bem a formulação inicial da hipótese Conn", diz Anand Natarajan.

Ele e seus co-autores esperam que os matemáticos traduzam novos resultados em seu próprio idioma. Em uma prova de relatório de publicação, Thomas Widick escreve: "Não tenho dúvidas de que, no final, a teoria da complexidade computacional não será necessária para obter resultados puramente matemáticos".

No entanto, quando outros pesquisadores se familiarizam com a prova, o caminho da pesquisa, graças ao qual foi possível alcançá-la, termina. Por mais de três décadas, os cientistas da computação simplesmente tentaram descobrir até onde a verificação interativa das soluções de problemas pode levá-las. Agora, diante deles, está a resposta, na forma de um longo artigo com uma manchete simples e com ecos das idéias de Turing.

“Existem muitos trabalhos cujos autores estão se perguntando quais são as possibilidades de um procedimento de verificação usando duas intrincadas provas quânticas. Agora sabemos o quão poderoso é esse procedimento. Essa história chegou ao fim ”, diz Anand Natarajan.

Queridos leitores! O que a prova MIP * = RE significa para a área em que você trabalha?