Disciplina
Computação, Informação e Lógica Quânticas
Área
Área Científica de Lógica e Computação > Lógica e Computação
Activa nos planos curriculares
DEASegInf2021 > DEASegInf2021 > 3º Ciclo > Matemática > Lógica e Computação > Computação, Informação e Lógica Quânticas
DEAEEC2006 > DEAEEC2006 > 3º Ciclo > Computação, Informação e Lógica Quânticas
DEASegInf2007 > DEASegInf2007 > 3º Ciclo > Matemática > Lógica e Computação > Computação, Informação e Lógica Quânticas
DEAEIC2006 > DEAEIC2006 > 3º Ciclo > Computação, Informação e Lógica Quânticas
DEAMat2006 > DEAMat2006 > 3º Ciclo > Lógica e Computação > Computação, Informação e Lógica Quânticas
MMA 2006 > MMA 2006 > 2º Ciclo > Opções Avançadas - Doutoramento > Opções de Lógica e Computação > Computação, Informação e Lógica Quânticas
Nível
Exercícios (60%) e exame final (40%).
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
4.0 h/semana
154.0 h/semestre
Objectivos
Dominar os conceitos, resultados e técnicas emergentes da computação e informação quânticas, com ênfase no desenvolvimento e análise de correcção e complexidade de algoritmos e protocolos quânticos.
Programa
Revisão dos conceitos e resultados relevantes de álgebra linear e teoria de operadores. Notação de Dirac. Postulados da mecânica quântica. Lógica exógena quântica proposicional: concepção a partir dos postulados, sintaxe, semântica, sistema dedutivo de Hilbert, decidibilidade e completude fraca. Comparação com as lógicas de Birkhoff e von Neumann. Autómatos e sistemas de transições quânticos. Lógica dinâmica quântica. Circuitos quânticos e conjuntos completos de portas quânticas. Classes de complexidade computacional quântica. Algoritmo de Deutsch-Jozsa. Tranformada de Fourier quântica. Algoritmo de Shor. Pesquisa quântica: algoritmo de Grover, aceleração canónica de algoritmos de pesquisa. Passeios quânticos. Aceleração exponencial - algoritmo de Childs et al. Entropia de von Neumann, majoração de Holevo. Entrelaçamento e desigualdades de Bell. Comunicação sobre canais quânticos. Correcção quântica de erros. Teorema da impossibilidade da clonagem. Criptografia quântica: distribuição de chave, partilha de chave, autenticação, sistemas de prova de conhecimento nulo com adversário quântico, computação segura quântica.
Metodologia de avaliação
Exercícios (60%) e exame final (40%).
Pré-requisitos
Componente Laboratorial
Princípios Éticos
Componente de Programação e Computação
Componente de Competências Transversais
Bibliografia
Principal
C. Cohen-Tannoudji, B. Diu e F. Laloë
John Wiley, (volumes One and Two)
Springer-Verlag, (Second Edition).
Quantum Computation and Quantum Information
Secundária
Quantum cryptography: Public key distribution and coin tossing
Proceedings of IEEE, nternational Conference on Computers, Systems and Signal Processing, 175--179
Quantum mechanics helps in searching for a needle in a haystack
Physical Review Letters, 79(2):325
Weakly complete axiomatization of exogenous quantum propositional logic
Information and Computation, to appear.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
SIAM Journal of Computing, 26(5):1484--1509