Defesa de Dissertação de Mestrado: Algoritmo de Contagem Quântico Aplicado ao Grafo Bipartido Completo

Orientadores:
Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Raqueline Azevedo M. Santos - Laboratório Nacional de Computação Científica - LNCC

Banca Examinadora:
Renato Portugal - Laboratório Nacional de Computação Científica - LNCC (presidente)
Paulo César Marques Vieira - Laboratório Nacional de Computação Científica - LNCC
Franklin de Lima Marquezino - COPPE/UFRJ - UFRJ

Resumo:

Estudos na Computação Quântica têm avançado desde a década de 1980, numa busca incessante por algoritmos melhores que qualquer algoritmo clássico concebível. Exemplos desses algoritmos são o Algoritmo de Grover, capaz de encontrar k elementos (marcados) num banco de dados desordenado com N elementos em 𝑂( &# 119873;/𝑘) passos. O algoritmo de Grover também pode ser interpretado como um passeio quântico num grafo completo com N vértices dos quais k são marcados. Essa interpretação estimulou a análise de algoritmos de busca em outros tipos de grafo -- e.g. grafo bipartido completo, malha e hipercubo. Utilizando o operador linear que descreve o algoritmo de Grover, o algoritmo de contagem resulta numa estimativa do valor k com erro da ordem de 𝑂( 𝑘)e em 𝑂( 𝑁)passos. Neste trabalho, analisa-se se é possível utilizar o algoritmo de contagem para estimar a quantidade k de elementos marcados em outros tipos de grafos; em particular no grafo bipartido completo. De fato, conclui-se que para um subcaso desse tipo de grafo, ao executar o algoritmo de contagem no máximo t vezes, é possível obter uma estimativa de k com erro da ordem de 𝑂( 𝑘) em 𝑂( 𝑡𝑁) passos e probabilidade de sucesso maior ou igual a (1 − 2 . W 22;𝑡)8/π²