Algoritmo de contagem quântico aplicado ao grafo bipartido completo

• Ano de defesa: 2021
• Autor(a) principal: Bezerra, Gustavo Alves
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Laboratório Nacional de Computação Científica; Coordenação de Pós-Graduação e Aperfeiçoamento (COPGA); Brasil; LNCC; Programa de Pós-Graduação em Modelagem Computacional
• Palavras-chave em Português: Computação quântica; Algoritmos (Computação); Teoria dos grafos; Fourier, Transformações de; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
• Link de acesso: https://tede.lncc.br/handle/tede/341

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. Um exemplo desses algoritmos é o algoritmo de Grover, capaz de encontrar k elementos (marcados) num banco de dados desordenado com N elementos em O (√ N/k) passos. O algoritmo de Grover também pode ser interpretado como um passeio quântico num grafo completo (com laços) 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 quântico resulta numa estimativa do valor k com erro da ordem de O (√k) e em O (√N ) passos. Neste trabalho, analisa-se o problema de usar o algoritmo de contagem quântico 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 proposto no máximo t vezes, é possível obter uma estimativa de k com erro da ordem de O (√k) em O ( t√N ) passos e probabilidade de sucesso maior ou igual a (1 − 2−t) 8/π2.