♋️ 🙋 👷 Prova significativa do teorema da ciência da computação captura a física com a matemática 🥡 👩🏿‍💼 ☕️

Especialistas em ciência da computação identificaram novas fronteiras no conhecimento verificado através da computação. E, ao mesmo tempo, resolveram problemas significativos da mecânica quântica e da matemática pura.

Em 1935, Albert Einstein, juntamente com Boris Podolsky e Nathan Rosen, tentou lidar com a oportunidade que se abriu com as novas leis da física quântica: o "entrelaçamento" de duas partículas, que neste caso podem ser separadas por uma grande distância.

No ano seguinte, Alan Turing formulou a primeira teoria generalizada da computação e provou a existência de problemas, em princípio não sujeitos a computadores.

Essas duas idéias revolucionaram seus respectivos campos. Além disso, parecia que eles não tinham nada a ver um com o outro. No entanto, agora uma prova significativa os uniu, resolvendo simultaneamente muitos problemas da ciência da computação, física e matemática.

A nova evidência sugere que computadores quânticos que realizam cálculos usando bits quânticos, ou "qubits", em vez de zeros e outros clássicos, podem teoricamente ser usados para confirmar soluções para uma enorme variedade de problemas. A conexão entre emaranhamento quântico e tecnologia de computador foi um choque para muitos pesquisadores.

"Foi completamente inesperado", disse Miguel Navazquezestudando física quântica no Instituto de Ótica Quântica e Informação Quântica em Viena.

Os co-autores da prova decidiram determinar os limites das possibilidades de confirmação de soluções para problemas computacionais. Sua abordagem usa confusão. Tendo encontrado essas fronteiras, os pesquisadores, ao mesmo tempo, quase como um efeito colateral, responderam a duas outras perguntas: o problema de Zirelson na física, com relação à modelagem matemática de entrelaçamentos, e o problema relacionado à matemática pura, a hipótese de Conn sobre aninhamento.

Os resultados acabaram caindo como dominós.

“Todas as idéias originais nasceram na mesma época. É conveniente que todos tenham se reunido de uma maneira tão incrível ", disse Henry Ewanda Universidade de Toronto, um dos autores da evidência. Outros autores: Zhengfeng Ji, da Universidade de Tecnologia de Sydney, Anand Natarajan e Thomas Widick, do Instituto de Tecnologia da Califórnia, e John Wright, da Universidade do Texas em Austin. Todos os cinco são cientistas da computação.

Problemas insolúveis

Turing identificou a principal plataforma para o estudo da computação antes mesmo do surgimento dos próprios computadores. E, literalmente, imediatamente ele mostrou que os computadores, em princípio, não podiam resolver certos problemas - e que isso podia ser provado. A questão é se o programa que resolve um problema específico termina seu trabalho.

Normalmente, os programas de computador recebem dados de entrada e, após algum tempo, produzem dados de saída. Mas, às vezes, eles ficam presos em ciclos intermináveis, o que faz suas engrenagens girarem para sempre. Quando isso acontece com você, você tem apenas uma opção.

“Eu tenho que pregar manualmente o programa. Apenas pare com ela - disse Ewan.

Turing provou que não há algoritmo geral que possa determinar se um programa concluirá a execução ou funcionará para sempre. Para descobrir, você deve executar o próprio programa.

Ewan, Vidik, Ji, Natarajan e Wright

“Você esperou um milhão de anos e o programa não terminou de trabalhar. Você precisa esperar mais um milhão de anos? Não há resposta para essa pergunta ”, disse William Slofstra , matemático da Universidade de Waterloo.

Tecnicamente falando, a tarefa de interromper um programa é insolúvel - mesmo o computador mais poderoso que você pode imaginar não pode resolvê-lo.

Depois de Turing, os cientistas da computação começaram a classificar outras tarefas de acordo com sua complexidade. Tarefas mais complexas exigem mais recursos de computação para serem resolvidas - mais tempo para trabalhar, mais memória. Portanto, estude a complexidade computacional das tarefas.

Como resultado, você pode fazer duas perguntas sobre cada tarefa: “Quão difícil é resolvê-lo?” e "Quão difícil é verificar a resposta correta?"

Interrogatório para confirmação

No caso de tarefas simples, a resposta pode ser verificada independentemente. Mas, à medida que se tornam mais complicadas, até verificar a resposta pode se tornar uma tarefa impossível. No entanto, em 1985, os cientistas da computação perceberam que era possível verificar a exatidão da resposta, mesmo que fosse impossível confirmá-la.

Este método segue a lógica de uma investigação policial. Se o suspeito contar uma história confusa, talvez você não consiga verificar todos os detalhes. Mas, fazendo as perguntas certas, você pode pegar o suspeito em uma mentira ou pode ter certeza da verdade da história.

Em termos de informática, o interrogatório contém um computador poderoso que oferece uma solução para o problema - conhecido como “provador” - e um computador menos poderoso que pede ao provador as perguntas para determinar a exatidão da resposta, conhecido como “teste”.

Um exemplo simples: imagine que você não faz distinção entre cores, e a outra pessoa - o provador - afirma que duas de algumas bolas têm uma cor diferente. Você não pode verificar esta declaração por conta própria, mas, através de interrogatórios engenhosos, ainda pode verificar se é verdadeira.

Coloque as bolas para trás e misture. Peça ao provador que lhe diga qual tem qual cor. Se eles são realmente de cores diferentes, o provador deve constantemente responder corretamente à pergunta. Se eles são da mesma cor - ou seja, têm a mesma aparência - na metade dos casos o provador expressará o palpite errado.

“Se vejo que você obteve muito mais sucesso do que na metade dos casos, terei quase certeza de que eles não são da mesma cor”, disse Vidik.

Ao fazer as perguntas do provador, você pode confirmar a correção das soluções para uma ampla gama de tarefas do que você mesmo poderia resolver.

Em 1988, os cientistas da computação pensaram no que aconteceria se dois provadores sugerissem soluções para o mesmo problema. Afinal, se você tiver a oportunidade de interrogar dois suspeitos, será ainda mais fácil solucionar o crime ou confirmar a exatidão da decisão - eles podem ser comparados entre si.

“Para quem checa, dá mais espaço para pressão. Você interroga, faz perguntas relacionadas ao caso, verifica as respostas ”, disse Vidik. Se os suspeitos estão dizendo a verdade, suas respostas devem coincidir na maior parte do tempo. Se eles mentirem, haverá mais contradições.

Da mesma forma, os pesquisadores mostraram que, ao interrogar separadamente os dois provadores sobre suas respostas, você pode rapidamente confirmar a correção da solução para uma classe de problemas ainda mais ampla, em comparação com a que você pode abordar com apenas um provador.

A complexidade computacional pode lhe parecer uma idéia puramente teórica, mas, no entanto, está intimamente relacionada ao mundo real. Os recursos que os computadores precisam para resolver problemas e confirmar decisões - tempo e memória - são fundamentalmente físicos. Portanto, novas descobertas na física podem mudar a complexidade computacional.

"Se você escolher um conjunto diferente de leis físicas, por exemplo, o mundo quântico em vez do mundo clássico, então outra teoria da complexidade poderá ser deduzida", disse Natarajan.

A nova evidência é o resultado final do confronto entre um cientista da computação do século XXI e uma das idéias mais estranhas da física do século XX: emaranhamento.

Hipótese de aninhamento de Conn

Quando duas partículas se enredam, elas não se afetam - elas não têm relação causal. Einstein et al., Revelaram essa ideia em um artigo de 1935. Depois disso, físicos e matemáticos tentaram criar uma maneira matemática de descrever o que realmente significa confusão.

No entanto, houve alguma confusão. Os cientistas criaram dois modelos matemáticos diferentes de entrelaçamento - e o fato de serem equivalentes entre si não era de todo óbvio.

Indiretamente, essa dissonância potencial influenciou o surgimento de um problema importante do campo da matemática pura, a hipótese de ninho de Conn. E no final, também serviu como cisma, da qual cinco cientistas da computação se aproveitaram em suas novas evidências.

A primeira maneira de modelar o emaranhamento é imaginar partículas isoladas espacialmente. Um deles, por exemplo, está na Terra e o outro em Marte; a distância entre eles exclui uma relação causal. Isso é chamado de modelo de produto tensorial.

Mas em algumas situações, não está totalmente claro se dois objetos são realmente isolados causalmente um do outro. Portanto, os matemáticos criaram uma maneira mais geral de descrever a independência causal.

Quando a sequência de operações nos objetos não importa, a operação é considerada comutada: 3 x 2 dará o mesmo que 2 x 3. No segundo modelo, as partículas são emaranhadas quando suas propriedades se correlacionam, mas a sequência de medições não importa. Meça a partícula A para prever o momento da partícula B ou vice-versa. De qualquer forma, a resposta será a mesma. Isso é chamado de modelo de emaranhamento de operador comutado.

Ambas as descrições de emaranhamento usam matrizes de números organizadas em colunas e linhas - matrizes. O modelo de produto tensorial utiliza matrizes com um número finito de colunas e linhas. O modelo de emaranhamento do operador de comutação usa um objeto mais geral que funciona como uma matriz, mas possui um número infinito de linhas e colunas.

Com o tempo, os matemáticos começaram a explorar essas matrizes por conta própria, separadamente de sua conexão com a física. No contexto deste trabalho, o matemático Alain Conn, em 1976, hipotetizou que muitas matrizes de dimensão infinita podem ser aproximadas por matrizes de dimensão finita. Essa foi uma das conclusões da hipótese de Conn de aninhamento.

Na próxima década, o físico soviético [no físico original, mas na Wikipedia é listado como matemático / aprox. translis.] Boris Tsirelson propôs sua própria versão deste problema, que novamente se associou à física. Zirelson sugeriu que o produto tensorial e os modelos de operador comutativo que descrevem o emaranhamento são aproximadamente equivalentes. Isso faz sentido, pois teoricamente essas são duas maneiras diferentes de descrever o mesmo fenômeno físico. Trabalhos subseqüentes mostraram que, devido à conexão das matrizes e dos modelos físicos que as utilizam, a hipótese de Conn sobre aninhamento e o problema de Zirelson segue uma da outra: resolva uma e você resolve a outra.

No entanto, a solução para ambos os problemas surgiu em uma direção completamente diferente.

Física e jogos

Na década de 1960, o físico John Bell criou um teste para determinar se o emaranhamento é um fenômeno físico real ou apenas uma idéia teórica. Algo como um jogo participou do teste, cujo resultado relatou se algo diferente da física não-quântica comum teve um papel no experimento.

Mais tarde, os cientistas da computação perceberão que esse teste de emaranhamento também pode ser usado como uma ferramenta para validar soluções para problemas muito complexos.

Mas primeiro, para entender como esses jogos funcionam, imagine dois jogadores, Alice e Bob, e uma caixa 3x3. O juiz dá a Alice uma linha e sugere que ela coloque 0 ou 1 linhas em cada uma das células, para que a soma dos números seja ímpar. Bob recebe uma coluna e precisa preencher todas as células para que a soma dos números seja uniforme. Eles vencem se colocarem o mesmo número na mesma célula - onde a linha e a coluna selecionadas se cruzam. Mas, ao mesmo tempo, eles não podem se comunicar.

Em condições normais, o melhor de que os jogadores são capazes é vencer em 89% dos casos. Mas no mundo quântico, eles podem melhorar esse resultado.

Suponha que Alice e Bob compartilhem um par de partículas emaranhadas. Cada um deles mede sua partícula e usa os resultados para determinar se deve escrever 0 ou 1. Em cada célula.Como as partículas são emaranhadas, os resultados de suas medições se correlacionam entre si, o que significa que suas respostas também se correlacionam - o que significa , eles poderão vencer em 100% dos casos.

Portanto, se você vir dois jogadores vencendo o jogo inesperadamente com frequência, poderá concluir que eles usam algo fora da física clássica. Agora, os experimentos de Bell são chamados de jogos "não locais", referindo-se à separação de jogadores. E os físicos realmente fazem esses experimentos em laboratórios.

"As pessoas fazem essas experiências há anos, e decorre delas que esse efeito assustador realmente existe", disse Ewan.

Ao analisar qualquer jogo, você pode precisar de informações sobre a frequência com que os jogadores vencem um jogo não local, se tentarem jogar da melhor maneira possível. Por exemplo, se você usar o Solitaire Solitaire, poderá calcular a probabilidade com que o jogador que joga perfeitamente conseguirá vencer.

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

Os cientistas da computação buscaram uma resposta usando dois modelos que descrevem os meandros. O algoritmo que usa o modelo de produto tensorial determinou o limite inferior ou o valor mínimo da probabilidade máxima aproximada de vitória para todos os jogos não locais. Outro algoritmo que usou o modelo de entrelaçamento com um operador dial-up determinou seu limite superior.

Quanto mais tempo esses algoritmos funcionarem, mais preciso será o resultado que eles produzem. Se a previsão de Zirelson for verdadeira, e esses dois modelos forem realmente equivalentes, os limites inferior e superior deverão se aproximar gradualmente, convergindo para um valor único da probabilidade máxima aproximada de vitória.

Mas se a previsão de Cirelson estiver errada e os dois modelos não forem equivalentes, "os limites inferior e superior permanecerão para sempre separados", disse Ewan. Será impossível calcular até o valor aproximado da probabilidade máxima de ganhar em jogos não locais.

No novo trabalho, cinco pesquisadores usaram esse tópico - se os limites inferior e superior convergem e se a hipótese de Tsirelson é verdadeira - para resolver uma questão separada sobre a possibilidade de confirmar a correção da solução de um problema computacional.

Ajuda complexa

No início dos anos 2000, os cientistas da computação pensaram: como a gama de tarefas mudará, cujas soluções podem ser confirmadas entrevistando dois provadores com partículas intricadas?

A maioria decidiu que o emaranhamento jogaria contra a confirmação. De fato, será mais fácil para dois suspeitos construir uma mentira consistente se eles tiverem uma maneira de coordenar as respostas.

Mas, nos últimos anos, os cientistas da computação perceberam que é exatamente o contrário: interrogando provadores, dividindo pares de partículas emaranhadas, é possível confirmar soluções para uma gama muito maior de problemas do que sem emaranhamento.

"A confusão é uma maneira de obter uma correlação que parece ajudá-los a mentir e trapacear", disse Vidik. "Mas você pode realmente envolvê-lo a seu favor."

Para entender como isso é possível, primeiro você precisa avaliar a gama quase sobrenatural de tarefas cujas soluções você pode verificar com este procedimento interativo.

Imagine um gráfico - um conjunto de pontos (vértices) conectados por linhas (arestas). Você pode descobrir se é possível colorir os vértices com três cores, para que não haja pares de vértices da mesma cor, unidos por uma aresta comum.

Se você der a algumas pessoas provas de um gráfico muito grande e disserem que ele pode ser colorido em três cores, conforme descrito, você pensará: existe uma maneira de verificar esta resposta?

Gráficos muito grandes não podem ser verificados diretamente. Em vez disso, você pode pedir a cada fornecedor que relate a cor de dois vértices conectados por uma aresta. Se eles reportarem cores diferentes e, a cada vez, fornecerem cores diferentes durante a pesquisa sobre outros vértices, sua confiança em que a pintura em três cores funciona aumentará.

Mas essa estratégia de pesquisa também deixa de funcionar quando os gráficos se tornam realmente grandes - quando o número de arestas e vértices começa a exceder o número de átomos no Universo. Para o verificador, mesmo uma tarefa como colocar uma pergunta específica (“diga-me a cor do vértice XYZ”) se torna insuportável - a quantidade de dados necessários para nomear um vértice específico excede a memória de trabalho disponível para ele.

No entanto, a confusão permite que os provadores façam perguntas eles mesmos.

“O revisor não precisa descobrir as perguntas. O inspetor faz com que os provadores calculem as perguntas para ele ”, disse Wright.

O inspetor precisa que os provadores lhe digam as cores dos vértices conectados. Se os vértices não estiverem conectados, as respostas à pergunta não dirão nada sobre a possibilidade de colorir o gráfico em três cores. Em outras palavras, o examinador deseja que o provador faça perguntas relacionadas: um provador faz a pergunta sobre o vértice ABC e o outro sobre o vértice XYZ. E eu gostaria que esses dois picos fossem conectados, embora nenhum dos provadores saiba de qual pico o outro está falando. Da mesma maneira que Alice e Bob esperam colocar o mesmo número no mesmo quadrado, embora nenhum deles saiba com qual linha e coluna o outro trabalha.

Se cada um dos dois provedores fizesse uma pergunta completamente por conta própria, eles não poderiam ser forçados a selecionar picos conectados ou correlacionados, para que o examinador pudesse confirmar suas respostas. No entanto, o emaranhamento apenas permite criar uma correlação.

“Vamos usar a confusão para despejar todo o trabalho dos provadores. Vamos fazê-los escolher suas próprias perguntas ”, disse Vidik.

No final do procedimento, cada um dos provadores relata uma cor. O revisor verifica se há uma correspondência. Se um gráfico puder realmente ser colorido em três cores, os provadores nunca devem produzir a mesma cor.

"Se a contagem puder ser pintada em três cores, os provadores poderão convencê-lo disso", disse Ewan.

Acontece que esse procedimento de confirmação é outro exemplo de jogo não local. Os provadores "vencem" convencendo-o da exatidão de sua decisão.

Em 2012, Vidik e Tsiyoshi Ito provaram que é possível, jogando vários jogos não locais com evidências confusas, confirmar as respostas para pelo menos o mesmo número de tarefas que ao interrogar dois computadores clássicos. Ou seja, o uso de provadores confusos não prejudica a confirmação de seus ottetes. E no ano passado, Natarajan e Wright provaram que a interação com provadores complicados realmente amplia a classe de tarefas validadas.

No entanto, até este ponto, os cientistas da computação não imaginaram o tamanho de toda a gama de tarefas, cujas soluções podem ser confirmadas de maneira semelhante.

Cascata de consequências

No novo trabalho, cinco cientistas da computação provam que o interrogatório de provadores complicados pode confirmar soluções para problemas não resolvidos, incluindo o problema de parada.

"Os recursos de validação desse modelo são incríveis", disse Ewan.

No entanto, o problema de parada não pode ser resolvido. E esse fato se tornou essencial para concluir a prova.

Suponha que você dê um programa a alguns provadores confusos. Você pede que digam se a execução será interrompida. Você está pronto para testar sua resposta através de uma variedade de jogos não locais: os provadores fazem perguntas e vencem, dependendo da consistência de suas respostas.

Se o programa realmente parar, os provadores devem poder vencer este jogo em 100% dos casos - como no caso de um gráfico que pode ser colorido com três cores, quando os provadores complicados não precisam dar a mesma cor para dois vértices conectados. Se o programa não parar, os provadores devem vencer apenas por acaso - ou seja, 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 será necessário resolver o problema de parada. Mas é impossível resolver. O que significa que a tarefa de calcular a probabilidade máxima aproximada de vitória é insolúvel, assim como o problema de parar.

E isso, por sua vez, significa que a resposta para o problema de Zirelson é negativa - os dois modelos de emaranhamento não são equivalentes. Se fossem, seria possível reduzir os limites inferior e superior da pontuação juntos e calcular a probabilidade máxima aproximada de vitória.

"Não existe um algoritmo desse tipo; portanto, os dois modelos devem ser diferentes", disse David Perez-Garcia, da Universidade Complutense de Madri.

O novo trabalho prova que a classe de problemas cujas soluções podem ser confirmadas pela interação com provadores quânticos emaranhados, MIP *, é completamente equivalente à classe de problemas que não são mais complicados que o problema de parada, RE. O título do trabalho descreve brevemente sua essência: “MIP * = RE”.

No processo de busca de evidências da igualdade das duas classes de complexidade, os cientistas da computação provaram a falsidade da hipótese de Tsirelson, que, graças a trabalhos anteriores, significa a falsidade da hipótese de Conn sobre o aninhamento.

Foi um choque para os pesquisadores das áreas relevantes que as respostas para problemas tão complexos fossem identificadas no processo de evidências aparentemente não relacionadas do campo da ciência da computação.

"Tendo visto um trabalho chamado MIP * = RE, eu definitivamente não acho que tenha algo a ver com o meu trabalho", disse Navazquez, co-autor de um trabalho anterior que vincula a hipótese de Cirelson à hipótese de Conn sobre o aninhamento. "Foi uma surpresa completa para mim."

Especialistas em física quântica e matemática estão apenas começando a digerir essa informação. Anteriormente, os matemáticos estavam interessados em saber se podem aproximar matrizes de dimensão infinita por matrizes finitas grandes. Agora, conhecendo a falsidade da hipótese de ninho de Conn, eles sabem que não podem.

"Pelo resultado deles, é impossível", disse Slofstra.

Os próprios cientistas da computação não tentaram encontrar confirmação da hipótese de Conn sobre o aninhamento; portanto, outras pessoas deveriam explicar todas as consequências das respostas que encontraram.

“Eu mesmo não sou matemático. Não entendo muito bem a definição inicial da hipótese de Conn sobre o assentamento ”, disse Natarajan.

Eles e co-autores sugerem que os próprios matemáticos traduzirão o novo resultado no idioma de seu campo. Em um artigo que declara evidências, Vidik escreveu: "Não tenho dúvidas de que a teoria da complexidade não será mais necessária para obter resultados puramente matemáticos".

A evidência resultante interrompe a longa cadeia de pesquisa que a levou. Por mais de três décadas, os cientistas da computação tentam descobrir até onde a confirmação interativa levará. Agora eles têm uma resposta na forma de um longo trabalho com um cabeçalho simples e referências a Turing.

"Existe uma lista bastante grande de trabalhos que perguntaram sobre quais oportunidades poderiam ser" no procedimento de confirmação com a ajuda de dois provadores confusos, disse Natarajan. “Agora sabemos quais. A história acabou.

Prova significativa do teorema da ciência da computação captura a física com a matemática