Durante anos, os cientistas da computação têm procurado tarefas de um certo tipo que apenas um computador quântico seria capaz de resolver, mas não um computador clássico, mesmo das gerações futuras. E então eles encontraram um deles.
Nas fases iniciais do estudo dos computadores quânticos, os cientistas da computação fizeram uma pergunta, cuja resposta, em sua opinião, deveria revelar alguma verdade profunda sobre as capacidades dessas máquinas futuristas. 25 anos depois, uma resposta foi encontrada. Em um
artigo publicado em maio de 2018, os cientistas da computação
Ren Rez e
Avishai Tal ofereceram evidências convincentes de que o poder computacional dos computadores quânticos supera qualquer coisa que os computadores clássicos possam alcançar.
Rez, um professor da Universidade de Princeton e do Wiseman Institute of Science, bem como Tal, um pós-doutorado da Universidade de Stanford, identificaram um tipo específico de problema computacional. Eles provaram, com uma ressalva, que os computadores quânticos poderiam efetivamente resolver o problema, e os computadores tradicionais ficariam presos para sempre, tentando fazê-lo. Os cientistas da computação procuram esse problema desde 1993, quando identificaram
pela primeira vez
a classe de tarefas BQP , que inclui todas as tarefas que um computador quântico pode resolver.
Desde então, eles esperavam contrastar a classe de tarefas BQP conhecida como PH, que inclui todas as tarefas que podem ser executadas em qualquer computador clássico, mesmo o incrivelmente avançado desenvolvido por alguma civilização do futuro. A possibilidade de tal contraste dependia de encontrar um problema que pertencia à classe BQP, mas não à classe PH. E agora Rez e Tal fizeram isso.
Esse resultado não torna os computadores quânticos melhores do que os clássicos do ponto de vista prático. Primeiro, os cientistas teóricos da computação já sabem que os computadores quânticos são capazes de resolver quaisquer tarefas das quais os clássicos são capazes. E os engenheiros estão lutando para resolver o problema de criar uma máquina quântica útil. Mas o trabalho de Reza e Tal demonstra a diferença nas categorias em que os computadores quânticos e clássicos estão localizados - e que mesmo em um mundo em que os computadores clássicos excederam os limites de qualquer sonho, os computadores quânticos ainda podem superá-los.
Classes quânticas
A tarefa básica da informática teórica é dividir tarefas em classes de complexidade. A classe de complexidade contém todas as tarefas que podem ser resolvidas com um recurso específico, como tempo ou memória.
Os cientistas, por exemplo, descobriram um algoritmo eficaz que verifica se um número é primo. No entanto, eles não conseguiram encontrar um algoritmo eficaz para encontrar fatores primos de grandes números. Portanto, eles acreditam (embora não possam provar isso) que esses dois problemas pertencem a diferentes classes de complexidade.
Duas classes de dificuldade famosas são P e NP. P é todas as tarefas que um computador clássico pode resolver rapidamente. (O problema “é o número primo?” Pertence a P). O NP inclui todas as tarefas que um computador clássico não necessariamente resolve rapidamente, mas a correção da solução existente, que pode ser verificada rapidamente. (“Quais são os principais fatores de um número?” Pertence a NP). Os cientistas acreditam que as classes P e NP são diferentes, mas a tarefa de provar essa diferença é o mais difícil e o mais importante dos problemas em aberto nessa área.
Um PH contém um NP que contém P. O BQP é uma classe separada do PH?Em 1993, os cientistas da computação Ethan Bernstein e
Umesh Wazirani definiram uma nova classe de complexidade, que eles chamaram de BQP, ou "tempo polinomial quântico com limitação de probabilidade de erro". Eles definiram a classe como contendo todas as tarefas de tomada de decisão - tarefas com a resposta "sim" ou "não" - que os computadores quânticos são capazes de resolver de maneira eficaz. Na mesma época, eles provaram que os computadores quânticos são capazes de resolver todas as tarefas das quais os clássicos são capazes. Ou seja, o BQP contém todas as tarefas contidas em P.
Outro exemplo de classes de tarefas individuais. O problema do vendedor pergunta se um caminho que passa por certas cidades é menor que uma determinada distância. Tal tarefa está no NP. Uma tarefa mais difícil pergunta se essa distância é o caminho mais curto por essas cidades. Tal tarefa está no PH.
No entanto, eles não conseguiram determinar se o BQP contém tarefas que não estão em outra classe importante de tarefas, conhecida como PH ou "hierarquia polinomial". PH é uma generalização de NP. Ele contém todas as tarefas que podem ser obtidas iniciando com uma tarefa do NP e complicando-a, adicionando declarações esclarecedoras como "se" e "para todos". Os computadores clássicos ainda não conseguem resolver a maioria dos problemas do PH, mas essa classe pode ser considerada uma classe de problemas que os computadores clássicos poderiam resolver se descobrisse que P é equivalente a NP. Em outras palavras, para comparar BQP e PH, é necessário determinar se os computadores quânticos têm uma vantagem sobre os computadores clássicos, que permanecerão mesmo que os computadores clássicos aprendam repentinamente a resolver muito mais problemas do que podem resolver hoje.
"O PH é uma das classes mais simples de complexidade que existe", disse
Scott Aaronson , especialista em TI da Universidade do Texas em Austin. "Então, nós meio que queremos conhecer o lugar da computação quântica em um mundo de complexidade clássica".
A melhor maneira de separar as duas classes de dificuldade é encontrar um problema comprovadamente incluído em uma delas e não incluído na outra. No entanto, devido a uma combinação de obstáculos fundamentais e técnicos, essa tarefa foi muito difícil de encontrar.
Para encontrar uma tarefa que pertence ao BQP, mas não ao PH, você precisa definir algo para o qual "um computador clássico, por definição, não conseguiu verificar efetivamente a resposta, sem mencionar a localização", disse Aaronson. "Isso elimina as muitas tarefas com as quais trabalhamos em ciência da computação".
Ask oracle
Desafio. Suponha que tenhamos dois geradores de números aleatórios, cada um dos quais produz uma sequência de dígitos. Pergunta ao computador: essas duas sequências são completamente independentes uma da outra ou estão de alguma forma imperceptivelmente conectadas (por exemplo, uma sequência é obtida pela
transformação de Fourier da outra)? Aaronson introduziu essa tarefa de "furrelation" em 2009 e provou que ela pertence ao BQP. O segundo passo, mais difícil, permanece - provar que a relação não está incluída no PH.
Ran rezEm certo sentido, foi exatamente isso que Resu e Talu fizeram. Seu trabalho separa BQP e PH com a ajuda dos chamados "
oracle " ou "black box". Esse é um resultado comum na ciência da computação, ao qual os pesquisadores recorrem quando o que eles querem provar não lhes é dado de forma alguma.
A melhor maneira de separar as classes de complexidade BQP e PH é medir o tempo computacional necessário para resolver problemas de cada classe. Mas a ciência da computação não tem "uma compreensão profunda do tempo real da computação ou a capacidade de medi-lo", disse Henry Youn, cientista da computação da Universidade de Toronto.
Em vez disso, algo mais está sendo medido na ciência da computação, que é pensado para fornecer uma compreensão do tempo computacional que não pode ser medido diretamente. Os cientistas calculam o número de chamadas de computador para o "oráculo" para dar uma resposta à pergunta. O oráculo parece dar pistas. Não sabemos como ele os recebe, mas sabemos que eles são confiáveis.
Se sua tarefa é descobrir se existe uma conexão secreta entre dois geradores de números aleatórios, você pode fazer perguntas ao oráculo como "qual será o sexto número de cada gerador?" Em seguida, você precisa comparar o poder da computação com base no número de solicitações necessárias para cada computador para resolver o problema. Um computador que precisa de mais dicas fica mais lento.
“De certa forma, entendemos esse modelo muito melhor. Ela fala mais sobre informações do que sobre computação ”, disse Tal.
Avishai TalO novo trabalho de Reza e Tal prova que um computador quântico precisará de muito menos pistas para resolver um problema de relacionamento do que o clássico. Além disso, um computador quântico precisa de apenas uma dica, apesar do PH não possuir um algoritmo para resolver esse problema, mesmo com um número ilimitado de dicas. "Isso significa que existe um algoritmo quântico extremamente eficiente que resolve esse problema", disse Rez. "Mas se considerarmos apenas algoritmos clássicos, mesmo que cheguemos às classes mais altas dos algoritmos clássicos, eles não serão capazes de lidar com isso". Isso prova que, com o oráculo, a relação refere-se a tarefas pertencentes ao BQP, mas não ao PH.
Rez e Tal quase alcançaram esse resultado há cerca de quatro anos, mas não conseguiram dar um passo na prova futura. E então, apenas um mês antes da publicação, Tal ouviu falar de um novo
trabalho sobre geradores de números pseudo-aleatórios e percebeu que as tecnologias desse artigo apenas davam o que ele e Rez precisavam para terminar seus próprios. "Era uma peça que faltava", disse Tal.
As notícias da separação das classes BQP e PH se espalharam rapidamente. "O mundo da complexidade quântica está movimentado",
escreveu Lance Fortnau, especialista em TI da Universidade de Tecnologia da Geórgia no dia seguinte à publicação do trabalho.
O trabalho dá uma forte confiança de que os computadores quânticos existem em um mundo separado da computação dos clássicos (pelo menos por definição no oráculo). Mesmo em um mundo onde P é equivalente a NP - onde resolver o problema do vendedor ambulante é tão simples quanto encontrar a linha mais adequada na planilha - a prova de Reza e Tal mostra que existem problemas que apenas um computador quântico pode resolver.
"Mesmo que P fosse equivalente a NP, mesmo com uma suposição tão forte", disse Fortnau, "os computadores quânticos ainda não alcançam".