A classic algorithm that wins from its quantum rival !!

A very recent discovery in the area of quantum computing surprised me (and the community) a lot.

Ewin Tang, a 18 years-old female student at Texas University, recently proved that classical computers can solve the “recommendation problem” (an NP- hard problem with practical appeal, used e.g. In Netflix systems, and others) as fast as quantum computers. This is a very significant result, because the “recommendation problem” was taken to be the best example of quantum speedup, that is, of an algorithm that quantum computers could solve in much less tine than standard algorithms. Her proof reverts the expectation about the absolute usefulness of quantum computers.

As Scott Aaronson, her advisor for graduate degree explains, given a matrix with m users and n products representing incomplete data about users opinions (one to five stars) about movies or products, organized into a convenient binary tree data structure, the problem is to sample some movies or products that a given user is likely to want to buy or to see. This is (in abstract form) the problem that Amazon and Netflix need to solve every time they tell you which books or movies you “might enjoy.”

Here is a link for Tang’s paper at ECCC – TR18-128; she was able to show that “recommendation problem” can be solved exponentially faster than anything known before. What is stunning is that she solved this problem by modifying a quantum algorithm, developed for a quantum computer, and made it run on a classical computer. Of course, it is important to know whether. other quantum algorithms could be modified in analogous way. May be quantum computers are not so revolutionary as we have been thinking up to now…

Um algoritmo clássico que ganha do seu rival quântico!!

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

“Contradiction, from Consistency to Inconsistency”​ – Review

“Contradiction, from Consistency to Inconsistency”, reviewed by Pedro Merlussi, CLE- published at Studia Logica (2019).

PORTUGUÊS/ ENGLISH

Springer, Series:Trends in Logic, Vol. 47, 2018, 322pp ISBN 978-3-319-98796-5 (hardcover)

https://doi.org/10.1007/s11225-019-09852- Section Book Reviews

https://link.springer.com/article/10.1007%2Fs11225-019-09852-7#citeas

Excerpt:

“ ‘Contradictions, from Consistency to Inconsistency’ is a collection of interesting papers in the study of the notions of contradiction, inconsistency and triviality. The range of topics covered go from philosophical debates about whether there are true contradictions to the study of consistency and inconsistency from a formal point of view. There is no shortage of technical discussion to keep the scientifically-minded reader on the edge of her seat. While it might not be a book to be read from cover to cover, Carnielli and Malinowski have made it sure that a broad range of readerswill benefit from the close study of many of its chapters. “

Excerto:

“ ‘Contradictions, from Consistency to Inconsistency’ é uma coleção de artigos interessantes no estudo das noções de contradição, inconsistência e trivialidade. A gama de tópicos abordados vai de debates filosóficos sobre se há ou não verdadeiras contradições, até o estudo da consistência e inconsistência de um ponto de vista formal. Não há escassez de discussão técnica, de forma a manter o leitor cientificamente consciente sempre interessado. Embora possa não ser um livro para ser lido de capa a capa, Carnielli e Malinowski garantiram que uma ampla gama de leitores se beneficiará do estudo detalhado de muitos de seus capítulos. “