Uma descoberta muito recente na área da computação quântica me surpreendeu muito (e surpreendeu a comunidade científica).

Ewin Tang, uma aluna de 18 anos da Universidade do Texas, provou recentemente que os computadores clássicos podem resolver o “problema de recomendação” (um problema difícil, NP-completo, com apelo prático, usado, por exemplo, nos sistemas Netflix e outros) tão rapidamente quanto computadores quânticos.. Este é um resultado muito significativo, porque o “problema de recomendação” foi considerado o melhor exemplo de aceleração quântica, isto é, de um algoritmo que os computadores quânticos poderiam resolver em muito menos tempo que os algoritmos padrão. Sua prova reverte a expectativa sobre a utilidade absoluta dos computadores quânticos.

Como Scott Aaronson, seu orientador no trabalho de pós-graduação explica,
dada uma matriz com m usuários e n produtos representando dados incompletos sobre opiniões de usuários (de uma a cinco estrelas) sobre filmes ou produtos, organizados em uma estrutura conveniente de dados de árvores binárias, o problema é separar filmes ou produtos que um determinado usuário provavelmente vai querer comprar ou assistir. Este é (de forma abstrata) o problema que a Amazon e a Netflix precisam resolver toda vez que sugerem quais livros ou filmes você “pode gostar”.

Aqui está o link para o artigo de Tang em ECCC – TR18-128. Ela foi capaz de mostrar que o “problema de recomendação” pode ser resolvido exponencialmente mais rápido do que qualquer outra solução anteriormente conhecida. O que é impressionante é que ela resolveu esse problema modificando um algoritmo quântico, desenvolvido para um computador quântico, e o fez rodar em um computador clássico. O que é importante agora é saber se outros algoritmos quânticos poderiam ser modificados de maneira análoga. Pode ser que os computadores quânticos não sejam assim tão revolucionários como temos pensado até agora…

Publicidade