Prova matemática pode ter resolvido problemas de décadas na matemática, na física e na ciência da computação

Você entra em uma caverna. No final de um corredor escuro, você encontra um par de câmaras fechadas. Dentro de cada câmara existe um mago onisciente. A profecia diz que, com a ajuda desses oráculos, você pode aprender as respostas para problemas não respondidos. Mas há um problema: os oráculos nem sempre dizem a verdade. E embora eles não possam se comunicar, suas respostas aparentemente aleatórias às suas perguntas são realmente conectadas pelo próprio tecido do universo. Para obter a resposta que você procura, você deve primeiro elaborar… as perguntas.

Os cientistas da computação estão comentando sobre uma nova prova matemática que propõe um sistema quanticamente emaranhado como o descrito acima. Ao que tudo indica, ela pode refutar uma e detalhar uma máquina teórica capaz de resolver o famoso problema da parada, que diz que um computador não pode determinar se será capaz de resolver um problema que está atualmente tentando resolver.

A , intitulada simplesmente “MIP*=RE”, trata do assunto esotérico da complexidade computacional. Se passar pelas verificações, ela demonstra uma profunda conexão entre a física quântica, a computação e a matemática. Isso mostra que uma classe teórica de dispositivos de computação — um verificador que interroga os oráculos quanticamente emaranhados — pode verificar alguns dos problemas mais complexos que se possa imaginar. E isso tem implicações importantes para os físicos quânticos.

• Um problema matemático de décadas envolvendo o número 42 foi finalmente resolvido
• Se você resolver este problema de matemática, você pode roubar todos os Bitcoins do mundo
• A maior prova matemática do mundo consiste em 200 TB de dados

No lado esquerdo do sinal de igual, fica a classe de computação teórica MIP*. Pesquisadores desde os anos 80 analisaram uma classe de problemas chamada IP, ou tempo polinomial interativo, uma lista de problemas solucionáveis ​​por provas interativas. Esse é um tipo de prova na qual um verificador (um computador comum que basicamente resolve problemas tirando cara ou coroa, ou seja, usando bits) está tentando verificar se uma resposta está correta. Para fazer isso, ele pode fazer perguntas a um observador onisciente, mas não necessariamente honesto, chamado de provador.

O Science News do que é esse tipo de prova.

Imagine, por exemplo, que você tem um amigo que afirma ter deduzido como diferenciar Pepsi e Coca-Cola, mesmo que você não consiga distinguir entre os dois. Para confirmar esta afirmação, você — o verificador — pode preparar uma xícara de Pepsi ou Coca-Cola e consultar seu amigo — o provador — sobre qual é. Se seu amigo sempre fornecer a resposta certa para essas perguntas, você estará convencido de que o problema de identificação de refrigerantes foi resolvido.

Se você conhece as classes de complexidade, pode ter ouvido falar de P, uma categoria de problemas solucionáveis ​​em tempo polinomial, o que significa uma quantidade de tempo igual ao tamanho da entrada gerada para um expoente constante (qualquer número).

Existem problemas de NP, aqueles em que não está claro quanto tempo levará para resolver o problema, mas, dada uma solução em potencial, leva apenas um tempo polinomial para verificar essa solução. Um exemplo famoso de um problema de NP é o . Dada uma série de pontos conectados por linhas (que os matemáticos chamam de grafo), como você usa três cores para pintar os pontos de modo que nenhuma cor se toque? Pesquisadores da década de 1980 e início da década de 1990 mostraram que essas provas interativas podem verificar todos os problemas de NP, bem como um conjunto de problemas pelo menos tão complicados que podem ser resolvidos usando uma quantidade polinomial de memória. Outros pesquisadores expandiram ainda mais a classe de problemas que podem ser resolvidos com uma prova interativa. É a classe MIP: e se o verificador fosse capaz de fazer perguntas a um par de provadores oniscientes, mas não necessariamente honestos, como se eles fossem um par de suspeitos criminais separados em salas com isolamento acústico? Esse sistema pode verificar com eficiência problemas ainda mais difíceis, aqueles que a quantidade de tempo necessário para a verificação aumenta exponencialmente com o tamanho da entrada, como um grafo de três cores ficando exponencialmente maior. Agora, os pesquisadores estão explorando uma classe ainda mais poderosa, chamada MIP*. Nesse caso, imagine o mesmo par de oráculos oniscientes sentados em salas separadas — mas eles são emaranhados através das regras da mecânica quântica. A mecânica quântica é o sistema matemático que descreve a maneira como as partículas subatômicas interagem, mas sua matemática parece uma versão mais complexa da probabilidade. Emaranhar os provadores significa que, embora eles estejam separados, coisas que podem parecer aleatórias quando você está conversando com apenas um único provador estão, de fato, correlacionadas entre os dois. Ufa. Vamos então revisar. O MIP é um tipo de sistema hipotético de prova em que um computador comum faz perguntas a um par de “oráculos” oniscientes, mas não necessariamente honestos, que não podem se comunicar. Esse tipo de sistema de prova pode verificar com eficiência as respostas para problemas extremamente complexos. Agora, os cientistas estão tentando entender o quão poderoso esse método de prova seria quando expandissem o MIP para MIP* — os oráculos ainda não conseguem se comunicar, mas agora estão emaranhados quanticamente, de modo que as respostas que eles fornecem são mais correlacionadas do que seriam de outra maneira. Um pesquisador da CalTech, Anand Natarajan, ouviu o cientista da computação Scott Aaronson dando palestras sobre o MIP* e percebeu que havia muito pouco conhecimento sobre a classe. “Foi uma daquelas raras situações na teoria da complexidade em que você tem uma enorme variedade de possibilidades do que realmente pode ser a verdade”, disse Natarajan, um dos autores do estudo, ao Gizmodo. John Wright, pesquisador do MIT, explicou ao Gizmodo que já havia definições para IP e MIP — e agora cabia a eles descobrir o MIP*. No ano passado, Wright e Natarajan elaboraram uma mostrando que a esquisita conexão na classe MIP* dá ao verificador que interroga os provadores quanticamente emaranhados o poder de verificar problemas ainda mais difíceis, aqueles cuja complexidade aumenta duas vezes exponencialmente com o tamanho da entrada. O entrelaçamento quântico dá mais conhecimento ao verificador para fazer perguntas melhores aos provadores (os oráculos). Enquanto isso, outro princípio da mecânica quântica, o princípio da incerteza, embaralha as medições dos provadores cada vez que o verificador pergunta sobre uma das duas propriedades complementares, tornando mais difícil iludir o verificador. Este trabalho de Wright, Natarajan, Zhengfeng Ji da Universidade de Tecnologia de Sydney, Thomas Vidick da CalTech e Henry Yuen da Universidade de Toronto provou que o poder da classe MIP* diminui a prova do ano passado. Eles afirmam que a MIP* poderia verificar com eficiência todos os problemas da “classe recursivamente enumerável” ou RE, basicamente todos os problemas para os quais levaria um tempo finito para calcular se a resposta era “sim”; uma resposta “não” poderia levar uma quantidade infinita de tempo para calcular. Portanto, MIP*=RE. Basicamente, esse dispositivo MIP* teórico pode resolver muitos problemas muito complexos, incluindo o famoso problema da parada, em que um computador é perguntado se um programa atualmente em execução será encerrado em algum momento, disse Wright. A prova MIP*=RE tem implicações importantes em matemática e física. “Em resumo, acho que é um resultado notável”, disse Bill Gefferman, professor assistente de ciência da computação da Universidade de Chicago que não participou do estudo. Ele falou com o Gizmodo por e-mail. “Esse resultado é um ótimo exemplo de como as ferramentas da comunidade de informação quântica podem ser úteis em amplas áreas da ciência e levar a soluções nas áreas que parecem ser completamente separadas. É por isso que estou mais empolgado com esse resultado.” A prova por si só faz uma declaração importante sobre o quanto você pode saber em mecânica quântica, disse ao Gizmodo Stephanie Wehner, professora de informações quânticas da Universidade de Tecnologia de Delft. Os cientistas se perguntaram o quão forte a correlação entre sistemas quânticos emaranhados pode ser no sentido mais geral. Mas, como efeito colateral da maquinaria da prova e da relação entre os oráculos e o verificador, verifica-se que essa questão é incalculável. “Esta é uma afirmação fundamental de que, de fato, não podemos realmente saber a resposta para certas coisas”, disse Wehner ao Gizmodo. “Isso é o que eu acho pessoalmente interessante nessa prova.”

Amazing development: The Connes Embedding Conjecture, open since the 1970s, seems to have been refuted using quantum information tools, by Ji, Natarajan, Vidick, Wright, and Yuen. — John Preskill (@preskill)

Tradução do tweet: Revelação impressionante: a Conjectura de Incorporação de Connes, em aberto desde os anos 1970, parece ter sido refutada usando ferramentas quânticas de informação por Ji, Natarajan, Vidick, Wright e Yuen.

Como subproduto dessa incalculabilidade, essa prova gigantesca refuta uma conjectura de 44 anos em álgebra abstrata denominada conjectura de incorporação de Connes, uma afirmação matemática esotérica que se descobriu logicamente equivalente a outras afirmações em outros tópicos matemáticos e físicos. Muitas pessoas esperam que a conjectura de Connes seja verdadeira, disse o físico do MIT Aram Harrow ao Gizmodo, pois isso provaria uma série de fatos e ferramentas úteis para matemáticos em todo o campo. Para os físicos especificamente, provar que a conjectura de incorporação de Connes está errada significa que dois objetos matemáticos separados antes considerados equivalentes em como eles podem explicar a medição de sistemas emaranhados não são, de fato, equivalentes. Certas aproximações de sistemas infinitos a finitos não funcionam mais, como os físicos supuseram que poderia ser. Ou seja, algumas aproximações finitas não replicam esses sistemas infinitos Este não é um dispositivo real que jamais existirá — você não pode conectar oráculos oniscientes, e um oráculo onisciente não pode nem ao menos existir. Mas os pesquisadores usam esses cenários abstratos para entender os verdadeiros limites do que os computadores podem ou não fazer. Talvez versões reduzidas dos oráculos, como computadores quanticamente emaranhados, dependentes da matemática da mecânica quântica para realizar seus cálculos, possam ter um poder além do que os físicos esperavam anteriormente. Wright alertou que os revisores ainda não tentaram verificar o trabalho apresentado na prova, e que ainda há um longo processo de revisão por outros matemáticos. Eles esperam que esteja tudo certo.