Analyzing the Computational Performance of Quantum Walk Based Algorithms on Structured Graphs
Coordenador do Projeto:
RENATO PORTUGAL
Data Início:
01/01/2014
Data Fim:
31/07/2017
Equipe:
Stefan Boettcher
Instituições Envolvidas:
Laboratório Nacional de Computação Científica - LNCC
Órgãos Financiadores:
CNPq
Resumo:
Temos como objetivo geral o estudo do desempenho de algoritmos de busca quântica e sua dependência na forma da estrutura. Ao contrário dos algoritmos clássicos, a interferência quântica e a necessidade de preservar a coerência em ambientes potencialmente irregulares e desordenados podem representar desafios significativos para um algoritmo quântico. Vamos analisar a interação entre a interferência quântica e o meio ambiente e seu efeito sobre a complexidade algorítmica usando tanto métodos analíticos quanto simulações. Em particular, nos aventuramos em explorar a eficácia de técnicas baseadas no grupo de renormalização (GR) para a análise de algoritmos quânticos. GR é uma ideia vencedora de prêmio Nobel de Física usado amplamente em Física Estatística para analisar fenômenos críticos de escala e é a chave para a noção física de universalidade. GR permite categorizar os processos com diversos detalhes microscópicos em classes de universalidade exibindo relações idênticas de escala macroscópica, semelhante à complexidade algorítmica.