aula1

aula1


Disciplina<strong>computação Quantica</strong>5 materiais27 seguidores
Pré-visualização5 páginas
TÓPICOS ESPECIAIS EM 
ENGENHARIA DA 
COMPUTAÇÃO 
AULA 1 
 
 
 
 
 
 
 
 
 
Prof. Luciano Frontino de Medeiros
 
 
CONVERSA INICIAL 
Esta aula está estruturada de maneira a apresentar uma introdução à 
Computação Quântica, evidenciando o tijolo básico na construção de circuitos 
quânticos, o q-bit, bem como a combinação de q-bits necessários ao 
processamento de informação quântica. O fenômeno do emaranhamento 
quântico é explicado, mostrando que certos aspectos do mundo quântico não 
podem ser simulados em sistemas clássicos. Ao final, é apresentado um breve 
histórico da Física Quântica, que posicionará o aprendiz nos principais eventos 
que deram origem ao estudo da Mecânica Quântica, que originou, mais tarde, o 
campo da Computação Quântica. 
TEMA 1 \u2013 INTRODUÇÃO À COMPUTAÇÃO QUÂNTICA 
A Computação Quântica é o estudo das tarefas que podem ser realizadas 
pelo processamento da informação contida em sistemas quânticos (Nielsen; 
Chuang, 2005, p. 12). A Computação Quântica e a Informação Quântica 
nasceram por meio de uma convergência de vários conceitos, alguns referentes 
à possibilidade de simulações computacionais mais realísticas de experimentos 
físicos. Os computadores conseguiriam simular fielmente os experimentos 
físicos, por meio de modelos construídos que espelhem perfeitamente a 
realidade? Paul Benioff (1980) expressou as primeiras ideias relacionando a 
Mecânica Quântica à Computação, com referência a máquinas de Turing, que 
pudessem ser simuladas explorando modelos de hamiltonianos da Mecânica 
Quântica. Richard Feynman (1982), então, questionava se os computadores 
clássicos poderiam efetivamente simular os eventos físicos. 
Usualmente, os cientistas imitam o mundo clássico, descrevendo-o com 
base em soluções aproximadas de equações diferenciais. Porém, o mundo real 
é o da mecânica quântica. Se tal mundo pudesse ser simulado, ele teria de ser 
exatamente simulado. Para sistemas constituídos de uma partícula apenas, a 
simulação de probabilidades dada por uma equação de onda de Schröedinger 
pode ser muito bem executada de maneira trivial. O problema da simulação 
aumenta a complexidade quando se adicionam muitas partículas ao sistema 
quântico. A quantidade de variáveis a serem controladas acaba sendo 
demasiadamente grande, e um computador normal não pode simular a realidade 
 
 
3 
para tal conjunto. Para que isso acontecesse, o computador no qual seria feita a 
simulação deveria ser construído de acordo com as leis da mecânica quântica. 
Feynman vai mais além, afirmando que, mesmo que uma simulação não 
seja exata, porém probabilística, o computador clássico ainda não teria 
condições de fazer tal simulação quântica. Pode-se usar como justificativa o fato 
de haverem efeitos não-locais, que não podem ser simulados por um 
computador clássico local; e o problema de existirem variáveis ocultas, que não 
podem ser representadas fisicamente e não podem, por consequência, serem 
representadas em um computador clássico (Feynman, 1982). Com relação à 
presença de efeitos não-locais entre objetos quânticos, os trabalhos mais 
significativos publicados foram o de Freedman e Clauser (1972) e o de Aspect, 
Grangier e Roger (1982), que realizaram em laboratório o experimento EPR com 
fótons, violando as desigualdades de Bell e confirmando os resultados previstos 
pela Mecânica Quântica quanto à não-localidade dos eventos quânticos. 
Algumas propriedades de sistemas quânticos, tais como os distúrbios inevitáveis 
envolvidos no processo de medição, têm uso prático em criptografia quântica 
(Bennett, 1973; Bennett et al., 1993; Steane, 1997). Porém, o salto significativo 
em direção à Computação Quântica foi dado por David Deutsch, sendo o 
primeiro a explorar as possibilidades de fazer computação com sistemas de 
mecânica quântica, propondo um análogo à máquina de Turing denominado 
Computador Quântico Universal. Neste trabalho, ele ainda propôs a primeira 
versão do que hoje é chamado de algoritmo de Deutsch, abrindo caminho para 
o desenvolvimento de algoritmos mais complexos e desenvolvimento maior da 
Computação Quântica. As operações simples utilizadas por ele no algoritmo são 
denominadas agora de portas quânticas. Deutsch se baseou no princípio da 
superposição quântica em seu algoritmo, explorando o aspecto do paralelismo 
massivo (Deutsch, 1985). 
Outra característica de um sistema quântico na forma de um circuito é a 
possibilidade de reversibilidade das operações. Ainda que a maior parte do 
desenvolvimento da Computação Quântica tenha acontecido na década de 
1980, Charles Bennett já havia explorado a possibilidade de uma máquina de 
Turing fazendo computação utilizando processos reversíveis (Bennett, 1973). As 
portas lógicas utilizadas nos circuitos eletrônicos comuns não poderiam fornecer 
reversibilidade, exceto a porta NOT. Ou seja, não é possível restaurar o estado 
anterior do sistema após uma operação lógica. Assim, certas portas lógicas, 
 
 
4 
como a porta Toffoli e a porta Fredkin, foram então concebidas de modo a 
permitir operações de computação reversível (Fredkin; Toffoli, 1982; Toffoli, 
1980). Porém, a reversibilidade não passava de uma curiosidade, pois mesmo 
em um circuito digital continua havendo dispêndio de energia para se fazer a 
operação reversa, obedecendo à lei de entropia. Com a Computação Quântica, 
a reversibilidade permitiria a recuperação dos estados anteriores às operações, 
simplesmente invertendo-se o sentido do circuito quântico. 
O algoritmo de Deutsch, como proposto inicialmente, utilizava apenas dois 
q-bits. Em trabalho subsequente, este algoritmo foi aprimorado de modo a conter 
mais q-bits, mostrando que sistemas de Computação Quântica poderiam ser 
escaláveis (Deutsch; Jozsa, 1992), sendo conhecido, assim, o algoritmo de 
Deutsch-Josza. Foi demonstrado, portanto, que certos problemas 
computacionais poderiam ser resolvidos de forma mais eficiente em um 
computador quântico do que em um computador clássico (Bernstein; Vazirani, 
1993; Berthiaume; Brassard, 1992). Um importante avanço foi feito por Simon 
(1994), que descreveu um algoritmo quântico eficiente para o qual não há uma 
solução eficiente pela abordagem clássica, mesmo utilizando métodos 
probabilísticos e explorando a periodicidade em aritmética modular. Este 
trabalho inspirou Peter Shor (1994) a descrever um algoritmo que não era 
apenas eficiente em um computador quântico, mas envolvia um problema 
fundamental em ciência da computação, a fatoração de números primos muito 
grandes. A força do sistema de criptografia RSA, muito utilizado por várias 
corporações mundiais, reside no fato de que não é possível fatorar em tempo 
polinomial o número composto fornecido para a chave pública de 128 ou 256 
bits. Entretanto, Shor demonstrou que um computador quântico, contendo um 
número suficiente de q-bits, tornaria possível a descoberta da chave privada do 
sistema RSA utilizando este algoritmo, o qual, mesmo sendo probabilístico, é 
eficiente (Shor, 1994). Os algoritmos de Simon e de Shor fazem uso das 
propriedades de superposição e emaranhamento quântico. 
Junto do algoritmo de Shor, outro algoritmo que mostrou a força da 
Computação Quântica em relação à Computação Clássica foi o algoritmo 
quântico de busca desenvolvido por Lov Grover (1996). Mediante o uso da 
superposição e da interferência quântica, Grover mostrou que a busca de um 
item em um conjunto de elementos não ordenados poderia ser feita com 
 
 
5 
complexidade menor do que em um algoritmo clássico. Mais tarde, foi 
demonstrado que o algoritmo de Grover perfaz uma busca ótima (Zalka, 1999). 
A Computação Quântica requer computadores quânticos para sua 
execução, e tais computadores estão sujeitos a efeitos de ruído do ambiente que 
podem interferir na precisão dos resultados dos algoritmos. A computação 
quântica deve ser feita com um grau razoável de acurácia, e conseguir