Cientistas nos Estados Unidos descobriram como testar problemas que ainda não estão disponíveis para os humanos. Os cientistas usam o mesmo método que os investigadores da polícia em seu diálogo com computadores que resolvem esses problemas. Eles "confundem" os interrogados, interrogam dois carros separadamente, etc. Até a mecânica quântica está sendo usada.
Imagine: um homem chega até você e diz que tem um adivinho, e que esse adivinho pode revelar os segredos incompreensíveis do universo. Você está intrigado, mas mal acredita nele. Definitivamente, você desejará ter certeza de que o adivinho está dizendo a verdade e, para isso, precisará de alguma forma ou método.
Essa é a essência de um dos principais problemas da informática. Algumas tarefas são muito difíceis de realizar em um prazo razoável. Mas sua solução é fácil de verificar. Por esta razão, os cientistas da computação querem saber: quão complexo pode ser um problema que tem uma solução verificável?
Acontece que a resposta é: pode ser incrivelmente complexo.
Em abril, dois cientistas da computação publicaram um trabalho de pesquisa que multiplicou o número de problemas difíceis de resolver, mas fáceis de verificar. Eles descreveram um método para testar soluções para problemas de complexidade quase incrível. “Parece loucura”, disse Thomas Vidick, um cientista da computação do Instituto de Tecnologia da Califórnia, que não estava envolvido neste novo trabalho.
A pesquisa envolve computadores quânticos que realizam cálculos de acordo com as regras contraditórias da mecânica quântica. Os computadores quânticos estão apenas começando a surgir, mas no futuro eles podem revolucionar a computação e a computação.
Na verdade, a nova pesquisa científica realizada nos dá a oportunidade de influenciar o adivinho descrito no início do artigo. Mesmo que ele prometa nos dar respostas para os problemas que nós mesmos não somos capazes de resolver, mesmo nessa situação aparentemente desesperadora, ainda teremos uma maneira de testar o adivinho e ter certeza de que ele está dizendo a verdade (ou enganando).
Vídeo promocional:
À MORTE DO UNIVERSO
Quando um problema é difícil de resolver, mas fácil de verificar, encontrar uma solução leva muito tempo, mas verificar a exatidão de uma determinada solução não.
Aqui está um exemplo. Imagine receber um desenho. É uma coleção de pontos (vértices) que são conectados por linhas (arestas). Você será questionado se é possível pintar esses pontos de uma forma com apenas três cores, de modo que os pontos conectados por linhas sejam de cores diferentes.
Este problema das “três cores” é difícil de resolver. Em geral, o tempo que leva para compor uma figura de três cores (ou para determinar que ela não pode existir) cresce exponencialmente à medida que a figura aumenta de tamanho. Por exemplo, se uma figura possui 20 pontos de conexão de linhas, então a solução do problema leva 3 à vigésima potência dos nanossegundos, ou seja, vários segundos em termos de unidades de tempo a que estamos acostumados. Mas se a figura estiver com 60 pontos, então a busca por uma solução levará 100 vezes mais do que nossa idade estimada do universo.
Mas vamos imaginar: alguém afirma ter feito uma figura de três cores. Demorará um pouco para verificar a veracidade de sua declaração. Vamos apenas começar a verificar os pontos de conexão das linhas um por um. Conforme a figura aumenta, o tempo de verificação também aumenta lentamente. Este é o chamado tempo polinomial. Como resultado, verifica-se que o computador não leva muito mais tempo para verificar uma figura tricolor com 60 vértices do que para verificar uma figura com 20 pontos de conexão.
"É muito fácil testar se esse circuito funciona, desde que seja uma figura real de três cores", disse o físico do MIT John Wright, que co-escreveu um novo artigo com Anand Natarajan do Caltech. …
Na década de 1970, os programadores identificaram uma classe de problemas que são fáceis de testar, embora às vezes difíceis de resolver. Eles deram a essa classe o nome de NPT - tempo polinomial não determinístico. Desde então, muitos cientistas da computação têm estudado esses problemas muito intensamente. Em particular, os cientistas querem saber como essa classe de problemas muda quando o inspetor tem novas maneiras de verificar a exatidão da solução.
PERGUNTAS CORRETAS
Antes do trabalho de Natarajan e Wright, duas descobertas importantes foram feitas para verificar a exatidão da solução. Eles aumentaram muito nossa capacidade de testar problemas superduros.
Para entender a essência da primeira descoberta inesperada, imagine que você seja daltônico. Dois cubos são colocados na mesa à sua frente e é perguntado se eles são da mesma cor ou diferentes. Essa tarefa é impossível para você. Além disso, você não está em posição de testar a decisão de outra pessoa.
Mas você tem permissão para questionar essa pessoa, a quem chamaremos de provador. Digamos que o provador diga que um par de cubos tem cores diferentes. Vamos designar o primeiro cubo com a letra "A", e o segundo com a letra "B". Você pega os cubos, esconde-os atrás das costas e os transfere de mão em mão várias vezes. Então você mostra os cubos e pede ao provador para mostrar o cubo A.
Se os cubos forem de cores diferentes, tudo é extremamente simples. O provador sabe que o cubo A é, digamos, vermelho, e ele o apontará corretamente todas as vezes.
Mas se os cubos são da mesma cor, ou seja, o provador mentiu, dizendo que a cor deles é diferente, ele só consegue adivinhar onde está o cubo. Por causa disso, ele indicará corretamente o dado A apenas 50% das vezes. Isso significa que, perguntando repetidamente ao provador sobre a solução, você pode verificar se ela está correta.
“O examinador pode fazer perguntas ao provador”, disse Wright. "E talvez no final da conversa a confiança do verificador aumente."
Em 1985, um trio de programadores provou que tais provas interativas podem ser usadas para testar soluções para problemas que são mais complexos do que a classe NIP. Como resultado de seu trabalho, uma nova classe de problemas chamada IPT apareceu - tempo polinomial interativo. O método usado para testar a cor de dois cubos pode ser usado para testar soluções para questões e problemas mais complexos.
O segundo grande passo foi dado na mesma década. Tudo aqui segue a lógica de uma investigação policial. Se você tiver dois suspeitos que acredita terem cometido um crime, não os interrogará juntos. Você vai interrogá-los em salas diferentes e depois comparar as respostas dadas por eles. Ao interrogar essas pessoas separadamente, você pode aprender mais verdade do que se tivesse apenas um suspeito.
“Os dois suspeitos não serão capazes de apresentar uma versão plausível e consistente porque eles simplesmente não saberão as respostas um do outro”, disse Wright.
Em 1988, um grupo de quatro cientistas da computação provou que, se dois computadores fossem solicitados a resolver o mesmo problema separadamente e depois interrogados separadamente sobre as respostas, uma classe ainda mais ampla de problemas poderia ser testada do que o IPV. Esta classe é chamada IDMD - prova interativa com muitos provadores.
Usando essa abordagem, pode-se, por exemplo, testar problemas "tricolor" em relação a uma sequência de formas que crescem em tamanho muito mais rápido do que as formas em tempo polinomial não determinístico. Em tempo polinomial não determinístico, o tamanho das formas aumenta linearmente - o número de pontos de conexão das linhas pode aumentar de 1 para 2, para 3, para 4 e assim por diante. Assim, nunca haverá uma grande disparidade no tamanho de uma figura com o tempo que leva para testar seu tricolor. Mas se estamos falando de uma prova interativa com muitos provadores, então aqui o número de pontos na figura aumenta exponencialmente.
Como resultado, esses números tornam-se muito grandes e não cabem na memória do computador de verificação, por isso ele não pode verificar sua tricolor percorrendo a lista de pontos de conexão. Mas ainda é possível verificar o tricolor perguntando aos dois provadores perguntas separadas, mas relacionadas.
Na classe de problema IDMD, o examinador tem memória suficiente para executar um programa para determinar se dois pontos em uma forma estão conectados por uma linha. O provador pode então pedir a cada provador para nomear um dos dois pontos conectados por uma linha, após o que ele pode facilmente comparar as respostas dos provadores para garantir que a figura de três cores está correta.
O aumento do nível de tarefas que são difíceis de resolver, mas fáceis de verificar, de NPV para IPV, e então para IDMD, pode ser alcançado por meio de computadores clássicos. Os computadores quânticos funcionam de maneira diferente. Durante décadas, não ficou claro como eles mudam o quadro, ou seja, se é mais difícil ou mais fácil verificar a solução com a ajuda deles.
O novo trabalho de Natarajan e Wright fornece uma resposta a essa pergunta.
DECEPÇÃO QUÂNTICA
Os computadores quânticos realizam computação manipulando bits quânticos (qubits). Eles têm uma propriedade estranha, cuja essência é que eles podem se confundir um com o outro. Quando dois qubits, ou mesmo grandes sistemas de qubits, ficam emaranhados um com o outro, isso significa que suas propriedades físicas os desempenham de uma determinada maneira.
Em seu novo trabalho, Natarajan e Wright consideram um cenário com dois computadores quânticos separados que compartilham qubits emaranhados comuns.
Parece que esse tipo de esquema funciona contra a validação. A capacidade de persuasão da prova interativa com muitos provadores é explicada precisamente pelo fato de que você pode interrogar dois provadores separadamente e então comparar suas respostas. Se essas respostas corresponderem, provavelmente estão corretas. Mas se dois provadores estiverem confusos, eles terão mais oportunidades de dar respostas erradas de maneira consistente e consistente.
De fato, quando um cenário com dois computadores quânticos emaranhados foi proposto pela primeira vez em 2003, os cientistas sugeriram que o emaranhamento enfraqueceria as capacidades de verificação. “Todos, inclusive eu, tiveram uma reação muito óbvia: agora os provadores terão mais força e persuasão”, disse Vidik. "Eles podem usar o emaranhamento para coordenar suas respostas."
Apesar desse pessimismo inicial, Vidic passou vários anos tentando provar o contrário. Em 2012, ele e Tsuyoshi Ito provaram que ainda é possível testar todos os problemas da classe IDMD usando computadores quânticos emaranhados.
Agora Natarajan e Wright provaram que a situação é ainda melhor. Uma classe mais ampla de problemas pode ser testada com emaranhamento do que sem ele. As conexões entre computadores quânticos emaranhados podem ser transformadas em benefício do examinador.
Para entender como, vamos relembrar o procedimento para testar figuras de três cores, cujo tamanho aumenta exponencialmente se uma prova interativa com muitos provadores for usada. O verificador não tem memória suficiente para armazenar a figura inteira, mas o suficiente para identificar dois pontos relacionados e perguntar aos provadores de que cor eles são.
Se falarmos sobre os problemas que Natarajan e Wright consideram - e eles pertencem à classe chamada de tempo exponencial duplo não determinístico (NDEW) - então o tamanho da figura neles aumenta ainda mais rápido do que no problema da classe IDMD. O número no NDEV está crescendo a uma taxa "dupla exponencial". Ou seja, é uma progressão geométrica dupla. O número aumenta não com a velocidade do 21º, 22º, 23º grau, mas "no grau de graus". Por causa disso, as formas crescem tão rapidamente que o examinador não consegue encontrar um único par de pontos conectados.
“São necessários 2n bits para marcar um ponto, que é exponencialmente maior do que a memória de trabalho do verificador”, diz Natarajan.
Mas Natarajan e Wright argumentam que é possível testar a coloração de três cores de uma figura duplamente exponencial sem ser capaz de determinar sobre quais pontos perguntar aos provadores. A questão é que os próprios provadores fazem perguntas.
Segundo os cientistas, a ideia de pedir aos computadores que verifiquem suas próprias decisões pelo método de votação é tão razoável quanto a ideia de pedir a suspeitos de um crime que se interroguem. Ou seja, isso é um absurdo completo. É verdade que Natarajan e Wright argumentam que esse não é o caso. O motivo é confusão.
“O estado entrelaçado é um recurso compartilhado”, diz Wright. "Todo o nosso protocolo visa compreender como usar este recurso compartilhado para preparar questões relacionadas."
Se os computadores quânticos estiverem confusos, sua escolha de pontos será interconectada e eles fornecerão o conjunto certo de perguntas para testar o tricolor.
Ao mesmo tempo, o examinador não precisa que os dois computadores quânticos estejam muito intimamente interconectados, uma vez que suas respostas a essas perguntas serão consistentes (isso é equivalente ao fato de que dois suspeitos concordam entre si quanto a um falso álibi). Outro recurso quântico estranho corrige esse problema. Na mecânica quântica, o princípio da incerteza nos impede de saber simultaneamente a posição de uma partícula e o momento de sua força. Se você medir um, destrua as informações sobre o outro. O princípio da incerteza limita severamente seu conhecimento de duas propriedades "complementares" de um sistema quântico.
Natarajan e Wright aproveitaram-se disso em seu trabalho. Para calcular a cor de um vértice, eles usam dois computadores quânticos que se complementam com medições. Cada computador calcula a cor de seus pontos e, ao fazer isso, destrói todas as informações sobre os pontos do outro computador. Em outras palavras, o emaranhamento permite que os computadores formulem perguntas inter-relacionadas, mas o princípio da incerteza os impede de conspirar para respondê-las.
“Precisamos fazer o provador esquecer [sobre a falsa versão dos eventos], e essa é a principal coisa que eles [Natarajan e Wright] fizeram em seu trabalho”, disse Vidik. "Eles forçam o provador a remover as informações ao fazer as medições."
Seu trabalho tem consequências enormes e muito importantes. Antes do surgimento deste trabalho, o limite da quantidade de conhecimento que poderíamos ter com total confiança era significativamente menor. Se tivéssemos uma resposta para o problema do IDMD, teríamos que aceitá-la com fé, já que não temos outra escolha. Mas Natarajan e Wright removeram essa limitação e tornaram possível validar respostas para muitos outros problemas computacionais.
Mas agora que eles fizeram isso, não está claro onde está o limite de validação.
"Isso poderia ir muito mais longe", disse Lance Fortnow, pesquisador de ciência da computação do Instituto de Tecnologia da Geórgia. "Eles deixam espaço para mais um passo."
Kevin Hartnett
