Departamento de Informática (UM)

Computação Quântica

14915 [ME80ME8002006771]

[Mestrado em Engenharia Física - Física da Informação]

S1

Luís Manuel Dias Coelho Soares Barbosa

Objetivos

O modelo computacional subjacente à computação quântica dispõe de características que o distinguem consideravelmente dos restantes modelos computacionais (ditos clássicos). A unidade curricular inicia-se assim com uma breve apresentação de aspectos do modelo computacional clássico que se pretendem contrapor com o modelo quântico. Segue-se a apresentação dos modelos de computação quântica em diferentes níveis de abstração: máquinas de Turing quânticas e lambda calculus. Neste ponto da matéria, os alunos deverão ter adquirido competências relativas aos dois primeiros objectivos da unidade curricular. Segue-se o estudo de algoritmosquânticos representativos de técnicas que permitem ganhos de eficiência significativos relativamente aos correspondentes algoritmos clássicos, suportado por forte prática laboratorial em programação quântica. Após este estudo, o aluno deverá ficar habilitado a responder aos três últimos objectivos enunciados.

Programa

1. Revisão de noções de computabilidade. Máquinas de Turing. Lambda-calculus
2. Modelos para a computação quântica: Máquinas de Turing quânticas; Lambda-calculus quântico
3. Complexidade computacional dos programas quânticos
4. Algoritmia quântica: Princípios básicos; classes de algoritmos. Algoritmo de Deutsh-Jozsa
5. Algoritmos de pesquisa: Grover e variantes
6. Transformada de Fourier Quântica: algoritmos de estimação de fase; Problema do hidden subgroup; Algoritmo de Shor
7. Técnicas de simulação quântica
8. Programação quântica: linguagens Quipper e Qiskit. Prática laboratorial

Bibliografia

Principal
1. Nielsen, M. A., Chuang, I. L. (2010). Quantum computation and quantum information. Cambridge University Press.

2. Kaye, P., Laflamme, R., Mosca, M. (2007). An Introduction to Quantum Computing. Oxford University Press.

3. Rieffel, E., Polak, W. (2011). Quantum computing: A gentle introduction. MIT Press.

4. Peter Selinger, Benoît Valiron. Quantum lambda-calculus. In S. Gay & I. Mackie (Eds.), Semantic Techniques in Quantum Computation (pp. 135-172). Cambridge: Cambridge University Press, 2009.

Complementar
1. Ying, M. (2016). Foundations of quantum programming. Elsevier, 2016.

2. Aaronson, S. (2013). Quantum computing since Democritus. Cambridge University Press.

Resultados da aprendizagem

A UC introduz a computação quântica, explorando fenómenos de natureza quântica como recursos computacionais. Iniciando-se nos modelos clássicos de computação, eg máquinas de Turing e lambda-calculus, a UC foca-se nos modelos de computação quântica, nomeadamente os circuitos quânticos. Definido o quadro conceptual, os algoritmos quânticos são introduzidos como estratégias para tirar partido dos efeitos quânticos, eg sobreposição e entrelaçamento, de modo a obter soluções computacionais eficientes para problemas muito difíceis de resolver classicamente.
No final os alunos serão capazes de:
1. compreender como os efeitos quânticos podem ser explorados na resolução de problemas computacionais
2. analisar o comportamento de circuitos quânticos
3. aplicar um conhecimento operativo dos princípios, modelos e técnicas da algoritmia quântica
4. simular circuitos quânticos em computadores clássicos
5. desenvolver algoritmos quânticos em linguagens de programação dedicadas

Método de avaliação

• de um trabalho prático de projecto em grupo (20%)
• desempenho nas aulas teórica-práticas (15%)
• teste escrito (70%)

Funcionamento

Turno: T 1; Docente: Luís Manuel Dias Coelho Soares Barbosa; Dep.: DI; Horas: 30.
Turno: TP 1; Docente: Ana Isabel Carvalho Neri; Dep.: DI; Horas: 30.