EVENTO
Passeios Quânticos sem Moeda
Tipo de evento: Exame de Qualificação
Os passeios quânticos desempenham um papel importante no desenvolvimento de algoritmos quânticos eficientes, especialmente para problemas de busca espacial em grafos. Atualmente, há pelo menos três versões de passeios quânticos a tempo discreto sendo estudados, sendo que duas dessas versões não fazem uso de um espaço interno adicional para determinar a direção da partícula e por isso são conhecidos como passeios quânticos sem moeda. Um deles é o passeio quântico proposto por Szegedy, que quantiza os passeios aleatórios clássicos em grafos bipartidos; e o outro, ainda pouco explorado, utiliza um operador de evolução, que é obtido através de operadores de reflexão, e depende de uma determinada tesselagem do grafo, conhecido como Staggered Quantum Walk. O objetivo deste trabalho é avaliar a equivalência entre os modelos de Szegedy e Staggered Quantum Walk; e desenvolver novos algoritmos para o problema de busca espacial em grafos que apresentam estrutura fractal, por apresentarem uma estrutura recursiva a análise dos mesmo será feita usando técnicas do grupo de renormalização.BIBLIOGRAFIA: Y. Aharonov, L. Davidovich, and N. Zagury. Quantum random walks. Physical Review A, 48(2):16871690, 1993.R. Portugal. Quantum Walks and Search Algorithms. Springer, New York, 2013.A. Patel, K.S. Raghunathan, and P. Rungta. Quantum random walks do not need a coin toss. Physical Review A, 71:032347, 2005.D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani.Quantum walks on graphs. In Proceedings of the 33rd ACM Symposium on Theory of computing, pages 5059, 2000.N. Shenvi, J. Kempe, and K. B. Whaley. Quantum random-walk search algorithm. Physical Review A, 67:052307, 2003.M. Falk. Quantum search on the spatial grid. arXiv:1303.4127, 2013.D.A. Meyer.From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics, 85(5-6):551574, 1996.R. Portugal, R.A.M. Santos, T.D. Fernandes, D.N. Gonçalves.The Staggered Quantum Walk Model. arXiv:1505.04761, 2015.M. Szegedy. Quantum speed-up of markov chain based algorithms. In Proceedings of the 45th Symposium on Foundations of Computer Science, pages 3241, 2004.R. Portugal, S. Boettcher, and S. Falkner. One-dimensional coinless quantum walks. Physical Review A, 91:052319, May 2015.A. Ambainis.Quantum walk algorithm for element distinctness. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004.L.K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79:325328, 1997.S. Boettcher, S. Falkner, and R. Portugal. Renormalization group for quantum walks, Journal of Physics: Conference Series 473 (2013), no. 1, 012018.Wilson, K. (1979). Problems in Physics with Many Scales of Length. Scientific American, 241, 158179.S. Redner. A guide to first-passage processes. Cambridge University Press, Cambridge, 2001.
Data Início: 09/11/2015 Hora: 10:00 Data Fim: 09/11/2015 Hora: 14:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio B
Aluno: Tharso Dominisini Fernandes - Laboratório Nacional de Computação Científica - LNCC
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Artur Ziviani - Laboratório Nacional de Computação Científica - LNCC Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC Jack Baczynski - Laboratório Nacional de Computação Científica - LNCC
