Defesa de Tese de Doutorado: Quantum Walk Search and Simulation

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

Banca Examinadora:
Renato Portugal - Laboratório Nacional de Computação Científica - LNCC (presidente)
Marcos Garcia Todorov - Laboratório Nacional de Computação Científica - LNCC
Marcos Cesar de Oliveira - Universidade Estadual de Campinas - UNICAMP
Carlos Felipe Lardizabal Rodrigues - Universidade Federal do Rio Grande do Sul - UFRGS

Suplentes:
Fabio Pereira dos Santos - Universidade Federal do Rio de Janeiro - UFRJ
Carlile Campos Lavor - Universidade Estadual de Campinas - IMECC/UNICAMP

Resumo:

Este trabalho explora os algoritmos quânticos de contagem e de busca, além de simulações de passeios quânticos. Estendemos o algoritm o quântico de contagem substituindo o operador de evolução de Grover por um passeio quântico em um grafo bipartido completo, demonstrando que seus autovalores codificam o número de vértices marcados e podem ser estimados usando o algoritmo de estimativa de fase, com uma complexidade semelhante à do algoritmo de contagem original. Para a busca quântica, desenvolvemos uma abordagem para grafos e multigrafos bipartidos, utilizando versões adaptadas do passeio de Szegedy e do passeio escalonado, respectivamente. Obtivemos uma aceleração quadrática em relação aos métodos clássicos baseados em cadeias de Markov e generalizamos o algoritmo de Ambainis, Gilyén, Jeffery e Kokainis. Além disso, apresentamos o Hiperwalk, um pacote Python que usa computação de alto desempenho para simulação de passeios quânticos, usando processamento paralelo para cálculos de álgebra linear. Essas contribuições impulsionam a computação quântica ao aprimorar as técnicas de busca e contagem, ao mesmo tempo que fo rnecem ferramentas práticas para simulações de passeios