Seminário de Avaliação - Série A: Análise assintótica de passeios quânticos para algoritmos de busca com múltiplos marcados

Orientadores:
Renato Portugal - Laboratório Nacional de Computação Científica - LNCC

Banca Examinadora:
Renato Portugal - Laboratório Nacional de Computação Científica - LNCC (presidente)
Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC
Gabriel Coutinho - Universidade Federal de Minas Gerais - UFMG

Suplentes:
Marcos Garcia Todorov - Laboratório Nacional de Computação Científica - LNCC

Resumo:

Dado um grafo qualquer, obtém-se uma matriz de adjacência e é possível definir um operador que representa a evolução de estados respeitando a localidade do grafo. A busca quântica, representada por uma pequena perturbação em alguns nós neste operador de evolução pa ra marcá-los, se baseia em evoluir o estado quântico por um determinado número de passos até que a probabilidade de encontrar um dos nós marcados seja máxima. Encontrar o número de passos e a probabilidade de sucesso final em grafos de interesse com um número qualquer de marcados é o principal objetivo deste trabalho. Para tal, desenvolvemos um método analítico que obtém uma expressão assintótica no número de nós para as quantidades desejadas a partir da análise de dois autovetores da matriz de evolução. O método foi desenvolvido para o caso de passeios discretos e contínuos, com exemplos na malha bidimensional e em grafos de Johnson, respectivamente e ambos com dois elementos marcados. Para um exemplo mais geral no número de marcados é apresentada a análise de passeios contínuos em t-designs, uma abstração matemática que nos gera diferentes grafos bipartidos. Neste último caso obtemos expressões analíticas dependendo não apenas dos parâmetros do grafo, como também do número de marc ados em determinadas configurações. Os exemplos estudados são casos onde não há uma teoria tão precisa a respeito da probabilidade de sucesso e tempo ótimo de passeios quânticos, além de mostrarem o potencial do método desenvolvido para lidar com problemas mais gerais.