Finalmente, um problema que somente os computadores quânticos serão capazes de resolver
Os
cientistas da computação têm procurado há anos por um tipo de problema
que um computador quântico pode resolver, mas que qualquer possível
computador clássico do futuro não pode. Agora eles encontraram um.
No início do estudo dos computadores quânticos, os cientistas da computação colocaram uma questão cuja resposta, eles sabiam, revelaria algo profundo sobre o poder dessas máquinas futuristas. Vinte e cinco anos depois, tudo está resolvido. Em um artigo publicado on-line no final de maio, os cientistas da computação Ran Raz e Avishay Tal fornecem fortes evidências de que os computadores quânticos possuem capacidade computacional além de qualquer coisa que os computadores clássicos possam alcançar.
Raz, professor da Universidade de Princeton e do Weizmann Institute of Science, e Tal, um pós-doutorado na Universidade de Stanford, definem um tipo específico de problema computacional. Eles provam, com uma certa ressalva, que os computadores quânticos poderiam lidar com o problema de maneira eficiente, enquanto os computadores tradicionais ficariam para sempre tentando resolvê-lo. Cientistas da computação têm procurado por esse problema desde 1993, quando definiram pela primeira vez uma classe de problemas conhecida como “BQP”, que abrange todos os problemas que os computadores quânticos podem resolver.
O resultado não eleva computadores quânticos sobre computadores clássicos em qualquer sentido prático. Por um lado, cientistas da computação teórica já sabiam que os computadores quânticos podem resolver qualquer problema que os computadores clássicos possam ter. E os engenheiros ainda estão lutando para construir uma máquina quântica útil. Mas o artigo de Raz e Tal demonstra que os computadores quânticos e clássicos realmente são uma categoria à parte — que mesmo em um mundo onde os computadores clássicos têm sucesso além de todos os sonhos realistas, os computadores quânticos ainda estariam além deles.
Cientistas da computação descobriram um algoritmo eficiente, por exemplo, para testar se um número é primo. Eles não conseguiram, no entanto, encontrar um algoritmo eficiente para identificar os fatores primos de grandes números. Portanto, os cientistas da computação acreditam (mas não foram capazes de provar) que esses dois problemas pertencem a classes de complexidade diferentes.
As duas classes de complexidade mais famosas são “P” e “NP”. P são todos os problemas que um computador clássico pode resolver rapidamente. (“Este número é primo?” Pertence a P.) NP é todo o problema que os computadores clássicos não conseguem resolver rapidamente, mas para os quais eles podem rapidamente verificar uma resposta, se apresentada com um. (“Quais são os seus principais fatores?” Pertence ao NP.) Cientistas da computação acreditam que P e NP são classes distintas, mas na verdade provam que a distinção é o problema aberto mais difícil e mais importante no campo.
Em 1993, os cientistas da computação Ethan Bernstein e Umesh Vazirani definiram uma nova classe de complexidade que chamaram de BQP, por “tempo polinomial quântico de erro limitado”. Eles definiram essa classe para conter todos os problemas de decisão — problemas com uma resposta sim ou não— onde os computadores quânticos podem resolver de forma eficiente. Na mesma época, eles também provaram que os computadores quânticos podem resolver todos os problemas que os computadores clássicos podem resolver. Ou seja, o BQP contém todos os problemas que estão no P.
Mas eles não puderam determinar se o BQP contém problemas não encontrados em outra importante classe de problemas conhecida como “PH”, que significa “hierarquia polinomial”. PH é uma generalização de NP. Isso significa que ele contém todos os problemas que você obtém se começar com um problema no NP e torná-lo mais complexo colocando instruções qualificadoras como “existe” e “para todos”. Computadores clássicos hoje não conseguem resolver a maioria dos problemas no PH , mas você pode pensar em PH como a classe de todos os problemas que os computadores clássicos poderiam resolver se P se mostrasse igual a NP. Em outras palavras, comparar o BQP e o PH é determinar se os computadores quânticos têm uma vantagem sobre os computadores clássicos que sobreviveriam mesmo se os computadores clássicos pudessem (inesperadamente) resolver muitos mais problemas do que podem hoje.
A melhor maneira de distinguir entre duas classes de complexidade é encontrar um problema que seja comprovadamente em um e não no outro. No entanto, devido a uma combinação de obstáculos fundamentais e técnicos, encontrar esse problema tem sido um desafio.
Se você quer um problema que está no BQP, mas não no PH, você tem que identificar algo que “por definição, um computador clássico não poderia verificar eficientemente a resposta, muito menos encontrá-la”, disse Aaronson. "Isso exclui muitos dos problemas em que pensamos na ciência da computação."
O que Raz e Tal fizeram, em um sentido particular. O artigo deles alcança o que é chamado de separação “oráculo” (ou “caixa preta”) entre BQP e PH. Esse é um tipo comum de resultado em ciência da computação e que os pesquisadores recorrem quando a coisa que realmente gostariam de provar está além de seu alcance.
A melhor maneira de distinguir entre classes de complexidade como BQP e PH é medir o tempo computacional necessário para resolver um problema em cada um. Mas os cientistas da computação "não têm um entendimento muito sofisticado ou a capacidade de medir o tempo real de computação", disse Henry Yuen, cientista da computação da Universidade de Toronto.
Em vez disso, os cientistas da computação avaliam outra coisa que esperam fornecer informações sobre os tempos de computação que não podem medir: eles calculam o número de vezes que um computador precisa consultar um "oráculo" para voltar com uma resposta. Um oráculo é como um guru. Você não sabe como eles geram as suas dicas, mas você sabe que elas são confiáveis.
Se o seu problema é descobrir se dois geradores de números aleatórios estão secretamente relacionados, você pode fazer perguntas oráculo como “Qual é o sexto número de cada gerador?” Então você compara o poder computacional baseado no número de sugestões de cada tipo de computador para resolver o problema. O computador que precisa de mais dicas é mais lento.
“Em certo sentido, entendemos esse modelo muito melhor. Fala mais sobre informação do que computação ”, disse Tal.
O novo artigo de Raz e Tal prova que um computador quântico precisa de muito menos dicas do que um computador clássico para resolver o problema de correlação. Na verdade, um computador quântico precisa de apenas uma dica, enquanto, mesmo com dicas ilimitadas, não há algoritmo no PH que possa resolver o problema. "Isso significa que existe um algoritmo quântico muito eficiente que resolve esse problema", disse Raz. “Mas se você considerar apenas algoritmos clássicos, mesmo que você vá para classes muito altas de algoritmos clássicos, eles não podem.” Isso estabelece que com um oráculo a relação é um problema que está no BQP, mas não no PH.
Raz e Tal quase alcançaram este resultado há quase quatro anos, mas não conseguiram completar um passo em sua prova. Então, apenas um mês atrás, Tal ouviu uma palestra em um novo artigo sobre geradores de números pseudo-aleatórios e percebeu que as técnicas naquele papel eram exatamente o que ele e Raz precisavam para concluir seus próprios trabalhos. "Esta foi a peça que faltava", disse Tal.
A notícia da separação entre o BQP e o PH circulou rapidamente. "O mundo da complexidade quântica está em ascensão", escreveu Lance Fortnow, cientista da computação na Georgia Tech, no dia seguinte em que Raz e Tal postaram suas provas.
O trabalho fornece uma garantia sólida de que os computadores quânticos existem em um campo computacional diferente dos computadores clássicos (pelo menos em relação a um oráculo). Mesmo em um mundo onde P é igual a NP —em que o problema do caixeiro viajante é tão simples quanto encontrar uma linha de melhor ajuste em uma planilha— a prova de Raz e Tal demonstra que ainda haveria problemas que apenas computadores quânticos poderiam resolver.
"Mesmo se P fosse igual a NP, mesmo fazendo essa forte suposição", disse Fortnow, "isso não será suficiente para capturar a computação quântica".
Raz, professor da Universidade de Princeton e do Weizmann Institute of Science, e Tal, um pós-doutorado na Universidade de Stanford, definem um tipo específico de problema computacional. Eles provam, com uma certa ressalva, que os computadores quânticos poderiam lidar com o problema de maneira eficiente, enquanto os computadores tradicionais ficariam para sempre tentando resolvê-lo. Cientistas da computação têm procurado por esse problema desde 1993, quando definiram pela primeira vez uma classe de problemas conhecida como “BQP”, que abrange todos os problemas que os computadores quânticos podem resolver.
O resultado não eleva computadores quânticos sobre computadores clássicos em qualquer sentido prático. Por um lado, cientistas da computação teórica já sabiam que os computadores quânticos podem resolver qualquer problema que os computadores clássicos possam ter. E os engenheiros ainda estão lutando para construir uma máquina quântica útil. Mas o artigo de Raz e Tal demonstra que os computadores quânticos e clássicos realmente são uma categoria à parte — que mesmo em um mundo onde os computadores clássicos têm sucesso além de todos os sonhos realistas, os computadores quânticos ainda estariam além deles.
Classes Quânticas
Uma tarefa básica da Ciência da Computação Teórica é classificar os problemas em classes de complexidade. Uma classe de complexidade contém todos os problemas que podem ser resolvidos dentro de um determinado orçamento de recursos, em que o recurso é algo como tempo ou memória.Cientistas da computação descobriram um algoritmo eficiente, por exemplo, para testar se um número é primo. Eles não conseguiram, no entanto, encontrar um algoritmo eficiente para identificar os fatores primos de grandes números. Portanto, os cientistas da computação acreditam (mas não foram capazes de provar) que esses dois problemas pertencem a classes de complexidade diferentes.
As duas classes de complexidade mais famosas são “P” e “NP”. P são todos os problemas que um computador clássico pode resolver rapidamente. (“Este número é primo?” Pertence a P.) NP é todo o problema que os computadores clássicos não conseguem resolver rapidamente, mas para os quais eles podem rapidamente verificar uma resposta, se apresentada com um. (“Quais são os seus principais fatores?” Pertence ao NP.) Cientistas da computação acreditam que P e NP são classes distintas, mas na verdade provam que a distinção é o problema aberto mais difícil e mais importante no campo.
 |
Lucy Reading-Ikkanda/Quanta Magazine
|
Em 1993, os cientistas da computação Ethan Bernstein e Umesh Vazirani definiram uma nova classe de complexidade que chamaram de BQP, por “tempo polinomial quântico de erro limitado”. Eles definiram essa classe para conter todos os problemas de decisão — problemas com uma resposta sim ou não— onde os computadores quânticos podem resolver de forma eficiente. Na mesma época, eles também provaram que os computadores quânticos podem resolver todos os problemas que os computadores clássicos podem resolver. Ou seja, o BQP contém todos os problemas que estão no P.
Mas eles não puderam determinar se o BQP contém problemas não encontrados em outra importante classe de problemas conhecida como “PH”, que significa “hierarquia polinomial”. PH é uma generalização de NP. Isso significa que ele contém todos os problemas que você obtém se começar com um problema no NP e torná-lo mais complexo colocando instruções qualificadoras como “existe” e “para todos”. Computadores clássicos hoje não conseguem resolver a maioria dos problemas no PH , mas você pode pensar em PH como a classe de todos os problemas que os computadores clássicos poderiam resolver se P se mostrasse igual a NP. Em outras palavras, comparar o BQP e o PH é determinar se os computadores quânticos têm uma vantagem sobre os computadores clássicos que sobreviveriam mesmo se os computadores clássicos pudessem (inesperadamente) resolver muitos mais problemas do que podem hoje.
Ao pensar em classes de complexidade, os exemplos ajudam. O "problema do caixeiro viajante" pergunta se há um caminho através de algumas cidades que são mais curtas do que algumas determinadas distâncias. Está no NP. Um problema mais complexo pergunta se o caminho mais curto através dessas cidades é exatamente essa distância. Esse problema está no PH."PH é uma das classes de complexidade clássica mais básicas que existem", disse Scott Aaronson, um cientista da computação da Universidade do Texas em Austin. "Então, nós meio que queremos saber, onde a computação quântica se encaixa no mundo da teoria da complexidade clássica?"
A melhor maneira de distinguir entre duas classes de complexidade é encontrar um problema que seja comprovadamente em um e não no outro. No entanto, devido a uma combinação de obstáculos fundamentais e técnicos, encontrar esse problema tem sido um desafio.
Se você quer um problema que está no BQP, mas não no PH, você tem que identificar algo que “por definição, um computador clássico não poderia verificar eficientemente a resposta, muito menos encontrá-la”, disse Aaronson. "Isso exclui muitos dos problemas em que pensamos na ciência da computação."
Pergunte ao Oráculo
Aqui está o problema. Imagine que você tenha dois geradores de números aleatórios, cada um produzindo uma sequência de dígitos. A questão para o seu computador é esta: as duas seqüências são completamente independentes umas das outras, ou estão relacionadas de maneira oculta (onde uma sequência é a “transformada de Fourier” da outra)? Aaronson introduziu este problema de "relação" em 2009 e provou que ele pertence ao BQP. Isso deixou o segundo passo mais difícil — provar que o Forrelation não está no PH.O que Raz e Tal fizeram, em um sentido particular. O artigo deles alcança o que é chamado de separação “oráculo” (ou “caixa preta”) entre BQP e PH. Esse é um tipo comum de resultado em ciência da computação e que os pesquisadores recorrem quando a coisa que realmente gostariam de provar está além de seu alcance.
A melhor maneira de distinguir entre classes de complexidade como BQP e PH é medir o tempo computacional necessário para resolver um problema em cada um. Mas os cientistas da computação "não têm um entendimento muito sofisticado ou a capacidade de medir o tempo real de computação", disse Henry Yuen, cientista da computação da Universidade de Toronto.
Em vez disso, os cientistas da computação avaliam outra coisa que esperam fornecer informações sobre os tempos de computação que não podem medir: eles calculam o número de vezes que um computador precisa consultar um "oráculo" para voltar com uma resposta. Um oráculo é como um guru. Você não sabe como eles geram as suas dicas, mas você sabe que elas são confiáveis.
Se o seu problema é descobrir se dois geradores de números aleatórios estão secretamente relacionados, você pode fazer perguntas oráculo como “Qual é o sexto número de cada gerador?” Então você compara o poder computacional baseado no número de sugestões de cada tipo de computador para resolver o problema. O computador que precisa de mais dicas é mais lento.
“Em certo sentido, entendemos esse modelo muito melhor. Fala mais sobre informação do que computação ”, disse Tal.
O novo artigo de Raz e Tal prova que um computador quântico precisa de muito menos dicas do que um computador clássico para resolver o problema de correlação. Na verdade, um computador quântico precisa de apenas uma dica, enquanto, mesmo com dicas ilimitadas, não há algoritmo no PH que possa resolver o problema. "Isso significa que existe um algoritmo quântico muito eficiente que resolve esse problema", disse Raz. “Mas se você considerar apenas algoritmos clássicos, mesmo que você vá para classes muito altas de algoritmos clássicos, eles não podem.” Isso estabelece que com um oráculo a relação é um problema que está no BQP, mas não no PH.
Raz e Tal quase alcançaram este resultado há quase quatro anos, mas não conseguiram completar um passo em sua prova. Então, apenas um mês atrás, Tal ouviu uma palestra em um novo artigo sobre geradores de números pseudo-aleatórios e percebeu que as técnicas naquele papel eram exatamente o que ele e Raz precisavam para concluir seus próprios trabalhos. "Esta foi a peça que faltava", disse Tal.
A notícia da separação entre o BQP e o PH circulou rapidamente. "O mundo da complexidade quântica está em ascensão", escreveu Lance Fortnow, cientista da computação na Georgia Tech, no dia seguinte em que Raz e Tal postaram suas provas.
O trabalho fornece uma garantia sólida de que os computadores quânticos existem em um campo computacional diferente dos computadores clássicos (pelo menos em relação a um oráculo). Mesmo em um mundo onde P é igual a NP —em que o problema do caixeiro viajante é tão simples quanto encontrar uma linha de melhor ajuste em uma planilha— a prova de Raz e Tal demonstra que ainda haveria problemas que apenas computadores quânticos poderiam resolver.
"Mesmo se P fosse igual a NP, mesmo fazendo essa forte suposição", disse Fortnow, "isso não será suficiente para capturar a computação quântica".
Comentários
Postar um comentário