EVENTO
Algoritmo de Contagem Quântico Aplicado ao Grafo Bipartido Completo
Tipo de evento: Defesa de Dissertação de Mestrado
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 𝑂( 𝑁/𝑘) 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 . −𝑡)8/π² Para assistir acesse: https://us02web.zoom.us/j/88487299596?pwd=VDZEUHhzU3F6dW9YR3hqR3pUY2hYZz09
Data Início: 02/09/2021 Hora: 09:00 Data Fim: 02/09/2021 Hora: 12:30
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Webinar
Aluno: Gustavo Alves Bezerra - - LNCC
Orientador: Raqueline Azevedo Medeiros Santos - University of Latvia - Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Franklin de Lima Marquezino - Universidade Federal do Rio de Janeiro - UFRJ/COPPE Paulo César Marques Vieira - Laboratório Nacional de Computação Científica - LNCC Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
