Encontraram possível solução para problema de computação aparentemente impossível

Por , em 18.01.2020

É assunto entre os cientistas nova prova que propõe um sistema de emaranhamento quântico. Ela dá detalhes da teoria sobre uma máquina capaz de resolver o famoso problema da parada, de acordo com o qual, um programa não pode determinar quando conseguirá resolver um problema em que está trabalhando no momento. Seria indecidível determinar se uma máquina para ou não quando roda sobre uma dada entrada.

O artigo sobre o assunto foi publicado no arXiv. Se passar pelo exame cuidadoso dos pares, a prova publicada demonstra conexão profunda entre física quântica, computação e matemática.

O trabalho foi realizado pelo pesquisador do MIT, John Wright, pelo pesquisador do CalTech, Anand Natarajan, Zhengfeng Ji da Universidade de Tecnologia de Sidney, Thomas Vidick do CalTech e Henry Yuen da Universidade de Toronto.

Os pesquisadores acreditam que o MIP* poderia resolver os problemas para os quais é possível obter a resposta “sim” em tempo finito, aqueles da classe recursivamente numerável ou RE. Uma resposta negativa poderia levar tempo infinito para ser obtida. Por isso o título do artigo: MIP*=RE.

Os problemas IP

Desde os anos 1980, os pesquisadores analisam uma classe de problemas chamados tempo Polinomial Interativo (IP, da sigla em inlgês), problemas que podem ser resolvidos por provas interativas. Há um tipo de prova realizada por um computador verificador que tenta conferir quando uma resposta está correta. Para isso, o computador pode fazer perguntas para um observador onisciente, mas não necessariamente honesto, o provador.

Há uma categoria de problemas solúveis em tempo polinomial, com duração igual ao tamanho da entrada gerada para um expoente constante. Há outros problemas para os quais não se sabe quanto tempo será necessário até chegar a uma solução.

Mas se for apresentada uma solução em potencial, é possível fazer a verificação no tempo polinomial. Essa solução para os problemas foi explorada pelos pesquisadores nos anos 1980 e início da década seguinte.

Outros pesquisadores aumentaram a variedade de problemas que poderiam ser resolvidos com uma prova interativa na classe MIP. Nesse caso o verificador poderia fazer perguntas para uma dupla não necessariamente honesta, mas que sabe de tudo e não pode trocar informações.

Resolver problemas mais complexos

O que os pesquisadores exploram agora é uma classe ainda mais poderosa, chamada MIP*. Nesse caso os mesmos dois fornecedores de respostas, sem contato entre si, estão emaranhados de acordo com as regras da mecânica quântica.

Dessa forma, aquilo que pode parecer aleatório quando se fala com apenas um dos provadores está, na realidade, correlacionado entre os dois. Agora o que os cientistas querem entender é qual será o poder desse método de prova quando fizerem a expansão do MIP para o MIP*.

O emaranhamento confere mais conhecimento ao verificador para fazer perguntas melhores aos provadores. Outro princípio da mecânica quântica faz com que seja mais difícil enganar os verificadores. Isso porque o princípio da incerteza deixa as provas desordenadas sempre que o verificador pergunta sobre duas propriedades complementares.

Esses “oráculos” provadores oniscientes são apenas teóricos. Mas os pesquisadores usam esse cenário abstrato para compreender os limites do que os computadores podem ou não podem fazer. Ainda assim, talvez, computadores emaranhados possam com uso da matemática da mecânica quântica realizar cálculos com poder superior ao previsto pelos experimentos anteriores dos físicos. [Gizmodo, arXiv]

Deixe seu comentário!