EVENTO
Análise assintótica de passeios quânticos para algoritmos de busca com múltiplos marcados
Tipo de evento: Defesa de Tese de Doutorado
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 para 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 marcados 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.Para assistir acesse:meet.google.com/txj-ybav-gts
Data Início: 13/12/2023 Hora: 14:00 Data Fim: 13/12/2023 Hora: 17:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Videoconferência
Aluno: Pedro Henrique Gasparetto Lugão - - LNCC
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Gabriel Coutinho - Universidade Federal de Minas Gerais - UFMG Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC Marcos Cesar de Oliveira - Universidade Estadual de Campinas - UNICAMP Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Suplente Banca Examinadora: Carlile Campos Lavor - Universidade Estadual de Campinas - IMECC/UNICAMP Marcos Garcia Todorov - Laboratório Nacional de Computação Científica - LNCC
