Colóquio conjunto de Física e Matemática ocorre no próximo dia 14/06/2017

Os Departamentos de Física e de Matemática da UFPE irão promover colóquio conjunto na quarta-feira (14), às 16h, no auditório do Departamento de Física, localizado no Centro de Ciências Exatas e da Natureza (CCEN). O colóquio tem como objetivo abrir uma porta para um estudo sistemático das classes do universo da complexidade computacional. O palestrante será Stefan Boettcher, do Departamento de Física da Emory University, da cidade de Atlanta, nos Estados Unidos. O título da palestra é “Determining the Efficiency of Quantum Search Algorithms with Renormalization”.

Resumo

Quantum walks provide another powerful demonstration of the effectiveness of the renormalization group (RG), here applied to explore the origin of the computational complexity of quantum search algorithms. Grover’s abstract quantum search provides in principle a quadratic speed-up over the best classical algorithm in locating an element in an unsorted list. Implementations for such a search with coined quantum walks have been suggested that can nearly satisfy the Grover speed-limit for as low as a two-dimensional geometry. For these, the RG reveals a competition between Grover’sabstractalgorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. It can be characterized in terms of the quantum walk dimension d^Q_w and the spatial (fractal) dimension d_f , even when translational invariance is broken. The analysis simultaneously determines the optimal time for a quantum measurement and the likelihood for successfully pin-pointing the sought-after element in the list. Our RG considers entire families of problems to be studied, thereby establishing a large universality class for quantum search. Thus, the methods we propose open the door to a systematic study of universality classes in computational complexity and how a class may be broken to modify and control search behavior.

Mais informações
Secretaria de Pós-Graduação
Departamento de Física – UFPE
(81) 2126.8449
posgrad@df.ufpe.br

Fonte: UFPE

Leave a Reply

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *