Exame de Qualificação: Cadeias de Markov Quânticas em Multigrafos

Hora: 09h

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

Banca Examinadora:
José Karam Filho - Laboratório Nacional de Computação Científica - LNCC (presidente)
Marcos Garcia Todorov - Laboratório Nacional de Computação Científica - LNCC
Eduardo Inacio Duzzioni - Universidade Federal de Santa Catarina - UFSC

Suplentes:
Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC

Resumo:

PASSEIOS QUÂNTICOS SE DESTACAM COMO UMA ÁREA DE ESTUDO PROMISSORA, CULMINANDO NA CONCEPÇÃO DE VÁRIOS TIPOS DE PASSEIOS QUÂNTICOS. ALGORITMOS BASEADOS NOS MAIS DIVERSOS TIPOS DE PASSEIOS QUÂNTICOS TÊM SE MOSTRADO MAIS EFICIENTES QUE SUAS CONTRAPARTIDAS CLÁSSICAS. POR EXEMPLO, EXISTEM ALGORITMOS QUÂNTICOS DE BUSCA EM GRAFO S QUE POSSUEM UM GANHO QUADRÁTICO EM RELAÇÃO AO NÚMERO DE CONSULTAS A UM ORÁCULO. EM PARTICULAR, USANDO O MODELO DE SZEGEDY, É POSSÍVEL ENCONTRAR UM VÉRTICE MARCADO EM QUALQUER GRAFO ASSOCIADO A UMA CADEIA DE MARKOV REVERSÍVEL EM PASSOS 𝑂 ( 𝑁) (A MENOS DE UM FATOR LOGARÍTMICO) INDEPENDENTEMENTE DA QUANTIDADE DE VÉRTICES MARCADOS. NESSE TRABALHO, PROPÕE-SE GENERALIZAR ESSE RESULTADO USANDO O MODELO DE PASSEIO QUÂNTICO ESCALONADO; E APRESENTA-SE TODO O FERRAMENTAL TEÓRICO E COMPUTACIONAL JÁ ADQUIRIDO QUE DEVE POSSIBILITAR O DESENVOLVIMENTO DA GENERALIZAÇÃO.