Yuvin Tan, de 18 anos, provou que os computadores clássicos podem resolver o "problema de recomendação" quase tão rápido quanto os computadores quânticos. Este resultado invalida um dos melhores exemplos de aceleração quântica de cálculos.
Um adolescente do Texas sitiou o desenvolvimento da computação quântica. Em um artigo publicado este mês na Internet
, Yuvin Tan
, de 18 anos, provou que computadores comuns podem resolver um importante problema computacional a uma velocidade
potencialmente comparável a computadores quânticos.
Na sua forma mais prática, o problema da recomendação está relacionado a como serviços como Amazon e Netflix determinam quais produtos você pode gostar. Os cientistas da computação consideraram
um dos melhores exemplos de tarefas que seriam resolvidas exponencialmente mais rapidamente em computadores quânticos - o que enfatizava as
capacidades potenciais dessas máquinas futuristas. E agora Tan refutou essa opinião.
"Foi um dos exemplos definidores de aceleração quântica - e agora desapareceu", diz Tang, que se formou na Universidade do Texas em Austin na primavera e está iniciando seus estudos de doutorado no outono na Universidade de Washington.
Em 2014, aos 14 anos, Tang passou pelas séries 4, 5 e 6 e entrou na Universidade do Texas, onde se formou em matemática e ciências da computação. Na primavera de 2017, Tan fez um curso de informações quânticas, ministrado por
Scott Aaronson , um conhecido pesquisador no campo da computação quântica. Aaronson reconheceu um aluno extraordinariamente talentoso em Tan e o convidou para se tornar seu orientador em um projeto de pesquisa independente. Aaronson deu a Tan várias tarefas para escolher, incluindo a questão das recomendações. Tan a escolheu com certa relutância.
"Hesitei porque parecia bastante complicado, mas foi a mais simples de todas as tarefas que ele me propôs", disse Tan.
O objetivo das recomendações é fornecer recomendações sobre produtos de que o usuário possa gostar. Considere o Netflix. Ele sabe quais filmes você assistiu. Ele sabe o que milhões de usuários assistiram. Com essas informações, é possível descobrir o que você deseja procurar mais?
Esses dados podem ser representados na forma de uma grade enorme, ou matriz, sobre a qual todos os filmes estão listados, ao lado são todos os usuários e, dentro, existem valores que medem o quanto cada um dos usuários gostou de cada filme. Um bom algoritmo produzirá uma lista de recomendações, detectando com rapidez e precisão as semelhanças entre filmes e usuários e preenchendo as células vazias da matriz.
Em 2016, os cientistas da computação
Iordanis Kerenidis e
Anupam Prakash publicaram um
algoritmo quântico que resolveu o problema de recomendação exponencialmente mais rápido do que qualquer um dos algoritmos clássicos conhecidos. Eles receberam tal aceleração quântica, em particular, devido à simplificação do problema. Em vez de preencher toda a matriz e determinar o único melhor produto a recomendar, eles criaram uma maneira de dividir os usuários em um pequeno número de categorias - eles gostam de blockbusters ou cinema independente? - e processe os dados existentes de forma a dar uma recomendação que seria simplesmente muito boa.
Quando o trabalho de Kerenidis e Prakash apareceu, havia muito poucos exemplos de problemas que os computadores quânticos deveriam resolver exponencialmente mais rápido que os clássicos. Na maioria das vezes, essas tarefas eram especializadas - problemas estreitos projetados especificamente para tirar proveito dos pontos fortes dos computadores quânticos (incluindo o problema de "
correlação " sobre o qual já escrevemos). O trabalho de Kerenidis e Prakash foi interessante porque destacou um problema real, importante para as pessoas, no qual os computadores quânticos superavam os clássicos.
"Do meu ponto de vista, esse foi um dos primeiros exemplos de aprendizado de máquina e processamento de big data, nos quais mostramos que computadores quânticos podem fazer algo que ainda não sabemos como usar métodos clássicos", disse Kerenidis, especialista em ciência da computação do Instituto de Paris para Pesquisa em Ciência da Computação.
Kerenidis e Prakash provaram que um computador quântico pode resolver o problema de recomendações exponencialmente mais rápido que qualquer um dos algoritmos conhecidos, mas eles não provaram que não há algoritmo clássico rápido. Portanto, quando Aaronson começou a trabalhar com Tan em 2017, ele colocou exatamente essa tarefa - provar a ausência de um algoritmo clássico rápido, confirmando a aceleração quântica de Kerenidis e Prakash.
"Pareceu-me que este seria um ponto importante que definiremos para completar esta história", disse Aaronson, que na época acreditava que não existe um algoritmo clássico rápido.
Tang começou a trabalhar neste outono de 2017, esperando que a tarefa das recomendações fosse objeto de sua dissertação. Por vários meses, Tan tentou provar a impossibilidade da existência de um algoritmo clássico. O tempo passou e Tan começou a pensar que talvez esse algoritmo existisse.
"Comecei a acreditar na existência do algoritmo clássico, mas não consegui me convencer disso, porque Scott pensava que ele não existia e era uma autoridade para mim", disse Tan.
Finalmente, quando o prazo para a dissertação já estava acabando, Tan escreveu uma carta para Aaronson, onde confessou suas crescentes suspeitas. "Tan basicamente escreveu o seguinte para mim: acho que existe um algoritmo clássico rápido", disse Aaronson.
Durante a primavera, Tang anotou os resultados e trabalhou com Aaronson para esclarecer algumas etapas da prova. Descoberto por Tan, o algoritmo clássico rápido foi inspirado no algoritmo quântico rápido encontrado por Kerenidis e Prakash dois anos antes. Tan demonstrou que a amostragem quântica usada em seu algoritmo pode ser reproduzida em condições clássicas. O algoritmo Tan, como o algoritmo Kerenidis e Prakash, foi executado em tempo polilogarítmico - ou seja, o tempo de cálculo foi estimado pelo logaritmo de parâmetros como o número de usuários e produtos - e foi exponencialmente mais rápido que qualquer outro algoritmo clássico conhecido anteriormente.
Após a conclusão do algoritmo por Tan, Aaronson queria ter certeza de que estava correto antes da publicação. "Eu ainda estava nervoso com o fato de que, se após a publicação do trabalho de Tan, ele estiver incorreto, então o primeiro grande trabalho na carreira de Tan será zilch", disse Aaronson.
Aaronson planejava participar de um workshop de computação quântica na Universidade da Califórnia em Berkeley em junho. Os luminares desta área deveriam se reunir lá, incluindo Kerenidis e Prakash. Aaronson convidou Than com ele para Berkeley, a fim de apresentar informalmente seu algoritmo após a parte oficial da conferência.
Na manhã de 18 e na manhã de 19 de junho, Tan deu duas palestras, respondendo a perguntas da platéia. Após quatro horas, chegou-se a um consenso: o algoritmo Tan clássico parece o correto. O que muitos dos presentes não entenderam foi como Tan era jovem. "Eu não sabia que Yuvin tinha 18 anos e certamente não me pareceu com os resultados das conversas. Pareceu-me que Juvin estava tendo uma conversa como um homem adulto ", disse Kerenidis. Agora, o algoritmo terá uma revisão por pares formal antes de ser publicada.
Para a computação quântica, o resultado do Tan é um passo atrás. Ou não Tang eliminou um dos exemplos mais compreensíveis e melhores de vantagem quântica. Ao mesmo tempo, o trabalho de Tan é outra evidência da existência de uma
interação frutífera entre estudos de algoritmos clássicos e quânticos.
“Tang elimina a aceleração quântica de Kerenidis e Prakash, mas em outro sentido, Tang contribui para grandes melhorias e é baseado em seu trabalho. Tang nunca teria inventado seu algoritmo clássico se não tivessem publicado seu quantum ”, disse Aaronson.