Seminários

Event

Title:: Eduardo Mucciolo: Computação paralela com muitos-corpos
When:: 28.06.2012 11.00 h
Where:: Matéria Condensada Teórica - Niterói
Category:: Seminários

Description

Computação paralela virtual via estados de muitos corpos matriciais: aplicação em algorítmos de procura

Eduardo Mucciolo (University of Central Florida, USA)

Neste seminário eu apresentarei a nossa proposta [1] de computação clássica paralela usando estados de muitos corpos codificados na forma de produtos matriciais. A paralelização é virtual e ocorre através da evolução simultânea de todos as possíveis configurações de entrada, sendo cada bit do circuito representado por um par de matrizes. Operações lógicas de um e dois bits são facilmente implementáveis nessa formulação. O resultado final é um vetor de estado a partir do qual se pode calcular as probabilidades de todas as possíveis saídas. Apresentarei uma aplicação desse método ao problema de procura (sorteio) em uma base de dados. Nossas estimativas indicam que o custo computacional desse algoritmo de procura está ligado ao número de operações lógicas de dois bits do circuito. Para um sistema de n bits, toda vez que o circuito contém menos do que O(n^2) operações lógicas de dois bits, o custo computacional é subexponencial. Portanto, nessas condições, o nosso algoritmo clássico é mais rápido do que o método de Grover baseado em computação quântica.

[1] C. Chamon and E. R. Mucciolo, arXiv:1202.1809