Instituto de Matematica e Estatstica - USP

MAC0412 - Organizacao de Computadores

Monografia

Computacao Quantica para leigos

Ana Luiza Domingues Fernandez Basalo - 6431109

William Alexandre Miura Gnann - 6431176

30 de janeiro de 2011

Sumario

1 Introducao 3

2 Historico 42.1 Fsica Quantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Computacao Quantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 O basico 53.1 Espacos de Hilbert e algumas notacoes . . . . . . . . . . . . . . . . . . . . . . . 53.2 Quantum Bits ou qubits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.3 Por que quantica? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.3.1 Sobreposicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.3.2 Observacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.3.3 Emaranhamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.3.4 Reversibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.3.5 Interferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.3.6 Decoerencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3.7 Nao-Clonagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Computadores Quanticos na pratica 124.1 Criterio de DiVincenzo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4.1.1 Escalabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.1.2 Inicializacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.1.3 Tempo de Coerencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.1.4 Portas Logicas Quanticas . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.1.5 Observacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4.2 Algumas implementacoes por alto . . . . . . . . . . . . . . . . . . . . . . . . . . 124.2.1 Armadilhas de on: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2.2 Optica: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2.3 Supercondutores: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2.4 Adiabatico: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2.5 Outros: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

5 Algoritmos Quanticos 145.1 Algoritmo de Deutsch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145.2 Algoritmo de Shor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155.3 Outros algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

6 Aplicacoes e possibilidades da Computacao Quantica 176.1 Criptografia Quantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

6.1.1 Implicacoes para a Criptografia Classica . . . . . . . . . . . . . . . . . . 176.1.2 Sistemas Criptograficos Quanticos . . . . . . . . . . . . . . . . . . . . . . 176.1.3 Distribuicao Quantica de Chaves . . . . . . . . . . . . . . . . . . . . . . 176.1.4 One-time pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

6.2 Speedup de algoritmos classicos . . . . . . . . . . . . . . . . . . . . . . . . . . . 186.3 Simulacao de sistemas quanticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 196.4 Outras aplicacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1

7 Informacao Quantica e Correcao de Erros 207.1 Informacao Quantica - Uma visao geral . . . . . . . . . . . . . . . . . . . . . . . 207.2 Teoria Quantica da Informacao . . . . . . . . . . . . . . . . . . . . . . . . . . . 207.3 Correcao de erros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

7.3.1 Correcao de erros classica . . . . . . . . . . . . . . . . . . . . . . . . . . 207.3.2 Correcao de erros quantica . . . . . . . . . . . . . . . . . . . . . . . . . . 21

8 Onde se faz Computacao Quantica? 228.1 Computacao Quantica na Academia . . . . . . . . . . . . . . . . . . . . . . . . . 228.2 Empresas e companhias que atuam com Computacao Quantica . . . . . . . . . . 228.3 Computacao Quantica no Brasil . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

9 Conclusao 24

2

1 Introducao

Com uma certa frequencia vemos, na mdia, diversas notcias, reportagens ou materiasacerca da Fsica Quantica. Ja, com menos frequencia, vemos alguma reportagem sobre Com-putacao Quantica. Em geral, essas materias costumam citar o conhecidssimo problema daquebra das chaves de criptografia baseadas em numeros primos e do caos causado a`s transacoesbancarias e aos departamentos de seguranca.

Tambem costumam dizer coisas magicas sobre as possibilidades da Computacao Quantica,mas, quase sempre, se esquecendo de diversos detalhes importantssimos como o problema daobservacao e a enorme dificuldade de tornar o computador quantico algo real.

Tentaremos, adiante, dar um parecer menos esoterico1 acerca dessa nova e intrigante areaque une tres grandes viloes do curso de engenharia: Fsica, Matematica e Computacao.

1Um bom exemplo do esoterismo associado a` Fsica Quantica e o filme Quem somos nos?.

3

2 Historico

Para falarmos de Computacao Quantica e necessario, antes, ver o contexto no qual surgiua Fsica Quantica e, depois, como surgiu seu estudo propriamente dito.

2.1 Fsica Quantica

No final do seculo XIX houve um momento bastante crtico para o desenvolvimento daFsica: a teoria parou de bater com alguns experimentos!

Os experimentos em questao envolviam objetos de dimensoes bem modestas ou mesmo ra-diacao. Pela modelagem imperfeita das teorias vigentes, surgiram, na epoca, conceitos absurdoscomo a Catastrofe Ultravioleta na qual a energia de uma onda poderia ser infinita.

Diante de uma situacao tao crtica, a Fsica obteve sua salvacao com a teoria de Max Planck,na qual a radiacao eletromagnetica e emitida atraves de quanta 2 cuja energia e proporcional a`frequencia da onda. Surgiu o que chamamos atualmente de Fsica Quantica.

Mais tarde, teramos, tambem, a explicacao de Einstein para o efeito fotoeletrico baseadona ideia do quantum. Da surgiu o conceito de foton: a partcula da qual a luz - uma ondaeletromagnetica - e composta.

Com a consolidacao da Teoria Quantica, muita coisa foi pesquisada na area e, com RichardFeynman, conhecido mundialmente por sua habilidade com o bongo 3, surgiu a EletrodinamicaQuantica, cujo objeto de estudo, grosso modo, e o efeito da radiacao nos eletrons.

2.2 Computacao Quantica

No comeco da decada de 1980, Richard Feynman escreveu, num artigo, que um sistemaquantico grande nao pode ser simulado num computador comum devido ao fato de um sistemacom n estados quanticos necessitar de 2n variaveis. Em particular, um sistema quantico com300 estados quanticos demandaria 2300 variaveis, ou seja, uma quantidade maior de variaveisdo que temos de atomos no universo observavel 4!

No artigo de Feynman tambem havia uma hipotese interessante: um computador construdoa partir das leis da Fsica Quantica poderia ser capaz de simular eficientemente um sistemaquantico, ou seja, um computador quantico poderia trabalhar exponencialmente mais rapidoque um computador comum.

A Computacao Quantica engatinhava ate que, em 1994, Peter W. Shor escreveu um algo-ritmo para computadores quanticos capaz de fatorar numeros inteiros em tempo polinomial. Opilar da criptografia baseada em numeros (e.g. RSA) foi abalado.

Atualmente, ha muita teoria como codigos corretores de erros para informacao quantica,diversos algoritmos que se aproveitam das propriedades quase magicas de um computadorquantico, duzias de modelos de computadores quanticos e, infelizmente, nenhum computadorquantico de uso geral.

2quanta e o plural de quantum, palavra do Latim que significa quantidade.3Na realidade, ele e mais conhecido por seu premio Nobel.4Estudos estimam cerca de 1080 atomos no universo observavel.

4

3 O basico

Para estudar Computacao Quantica, e imprescindvel entender coisas sobre como os fenomenosquanticos sao modelados, quais sao os que tem influencia direta e as diferencas entre o compu-tador quantico e o computador classico.

3.1 Espacos de Hilbert e algumas notacoes

Definicao 1. Um espaco vetorial H e completo se, para cada sequencia de vetores x tais que

limm,n

||xm xn|| = 0,

existe um vetor x H tal quelimn

||xn x|| = 0

Definicao 2. O produto interno de um espaco vetorial H associado ao corpo C e uma funcaode H H C com x, y, z H e C com as seguintes propriedades:

1. x | y = y | x

2. x | x 0 e x | x = 0 x = 03. x | y + z = x | y+ x | z4. x | y = x | y

Definicao 3. Entende-se por espaco de Hilbert, H, um espaco vetorial completo sobre C munidode produto interno como definido acima. Hn, n N, e o espaco de Hilbert de dimensao n.Observacao 1. Os vetores poderao ser notados da seguinte forma: |. Essa notacao tem onome de ket.

Definicao 4. Um operador linear e um mapeamento T : H H, dados x, y H e C,com a propriedade:

T (x+ y) = T (x) + T (y)

Em particular, se T (x) = x, com x H e C, x e dito um autovetor de T e umautovalor.

Definicao 5. Seja T um operador linear, se TT = I dizemos que T e unitario. Definimos T

como o T transposta com todos seus elementos conjugados.

Definicao 6. O produto tensorial e denotado por Hn Hm. Ele associa elementos xi da basede Hn com yj da base de Hm da seguinte forma: xi yj. Ele e definido da seguinte forma:

(ni=1

ixi) (mj=i

jyj) =ni=1

mj=i

ijxi yj

Notacoes alternativas:|x |y = |x |y = |x, y

5

3.2 Quantum Bits ou qubits

Definicao 7. Um sistema quantico com n estados pode ser denotado como um elemento de Hncom a forma:

| = 1 |x1+ 2 |x2+ ...+ n |xnOnde |xi e um elemento da base de Hn e i C.

No entanto i nao e qualquer, ele e escolhido tal que:ni=1

|i|2 = 1

Ou seja, |i|2 forma uma distribuicao de probabilidade em cima da base de Hn.Definicao 8. Um qubit e um sistema quantico com dois estados.

| = 1 |0+ 2 |1E importante salientar que |0 e ortogonal a |1. Caso contrario, as associacoes entre qubits

nao poderiam ser bem definidas.Para fazermos tais associacoes entre qubits podemos usar o produto tensorial. Logo um

sistema com dois qubits e isomorfo a H2 H2 e uma representacao possvel pode ser:| = 1,1 |00+ 1,2 |01+ 2,1 |10+ 2,2 |11

Um modo interessante de vermos o qubit e compara-lo com seu semelhante do mundoclassico, o bit. A tabela abaixo ilustra as principais diferencas entre as duas unidades basicas.

Propriedade bit qubitTipo numero vetorGasto n 2n

Natureza determinstica probabilsticaRepresentacao eletrica diversaQuantico nao sim

Depois de tantas diferencas, e interessante saber como estao relacionados. Tomemos, attulo de ilustracao, uma associacao de 2 bits e uma associacao de 2 qubits. Teremos os bits 00,01, 10 e 11 e a associacao de qubits :

| = 1,1 |00+ 1,2 |01+ 2,1 |10+ 2,2 |11Imediatamente, percebe-se a clara relacao entre os bits e a base da associacao de qubits. No

entanto, o grande diferencial dos qubits e que todos os estados sao representados simultanea-mente, ja o bit pode representar apenas um estado por vez - por isso o n 2n acima.

Essa representacao simultanea e a essencia do conceito de sobreposicao, que sera descritoadiante.

Uma duvida que pode ter aparecido, apesar de a relacao ser clara entre um bit e um qubit,e como relaciona-los exatamente, uma vez que ha uma infinidade 5 de combinacoes linearespossveis para um qubit.

Apesar da representacao simultanea, apenas um estado da base do qubit pode ser observado6 por isso, teremos n estados observaveis para n qubits.

Observacao 2. Pesquisas recentes transcenderam o conceito de qubit em numeros de estados.Temos hoje o qudit que e representado por H5 - que nada mais e que um sistema quanticocom cinco estados em vez de dois - e variaveis contnuas quanticas que fogem ao escopo destamonografia introdutoria.

5Lembre-se que a unica restricao para os coeficientes en

i=0 |i|2 = 1.6Observacao, aqui, e no sentido da Fsica Quantica.

6

3.3 Por que quantica?

E um fato que existem propriedades que sao exclusivas dos computadores quanticos. Casocontrario, seria trivial fazer a simulacao de um deles por uma Maquina de Turing.

Quais propriedades seriam essas?

3.3.1 Sobreposicao

Um dos grandes trunfos da quantica e, certamente, a sobreposicao. No estado de sobre-posicao, o sistema quantico assume todos os estados, mesmo que cada um tenha probabilidade|i|2 de ser observado.

Isso significa que a sobreposicao e um dos responsaveis pelo paralelismo sem precedentes.Em contrapartida, e justamente pela sobreposicao que os sistemas quanticos sao de tao difcilsimulacao.

Em termos de qubits, gastaramos, para n qubits, 2n numeros.Sera ilustrada, a seguir, a aplicacao de uma porta de Hadamard num sistema com n qubits.Situacao inicial:

| = 1 |x1+ ...+ 2n |x2nAplicando Hadamard, H(|), que sera descrita com detalhes mais adiante:

i =i + 2n1+1

2

Obteremos, por fim, uma nova configuracao:

|H() = 1 |x1+ ...+ 2n |x2n

Conclusao: mexendo com um qubit e possvel baguncar todos os outros estados.

3.3.2 Observacao

Certamente um dos problemas-chave para a quantica. Ao observarmos um sistema quantico,ocorre o que e chamado de colapso.

O colapso consiste em devolver |xi com probabilidade |i|2. Isso significa, primeiramente,que podemos obter resultados distintos a partir da observacao de um mesmo sistema quantico.O computador quantico deve ser perfeitamente isolado justamente para evitar rudos que co-lapsem o estado de sobreposicao.

Ademais, todo nosso cuidado usando a maravilha da sobreposicao pode ser inutil se obti-vermos um resultado errado ao observar.

Portanto, o problema da observacao consiste basicamente em saber como tratar os dadosdos qubits para obter o resultado correto com probabilidade alta na hora de observarmos.

Observamos acima como as portas logicas quanticas podem influenciar no sistema com aatuacao da porta Hadamard numa associacao de qubits. Uma enorme parcela desse tratamentoe oriunda do emprego dessas portas logicas quanticas.

Observacao 3. A observacao pode ser vista como um operador linear O : H2n B, comB H2n sendo o conjunto formado pela base da associacao de qubits.

7

3.3.3 Emaranhamento

Primeiramente, podemos ver o emaranhamento com os olhos de um matematico a partirdos espacos de Hilbert e do produto tensorial - lembrando que so teremos emaranhamento commais de um qubit.

Se um vetor | pode ser decomposto como o produto tensorial de dois outros vetores, naoha emaranhamento.

Exemplo: Considere o sistema quantico

1

2(|00+ |01+ |10+ |11)

Ele pode ser decomposto em:

12

(|0+ |1) 12

(|0+ |1)

Por outro lado, se ele nao puder ser decomposto como o produto tensorial de dois vetores,ha emaranhamento.

Exemplo: Considere o sistema quantico

12

(|00+ |11)

Vamos tentar decompo-lo:

12

(|00+ |11) = (1 |0+ 2 |1)(1 |0+ 2 |1)

= 11 |00+ 12 |01+ 21 |10+ 22 |11Mas

11 =12

12 = 021 = 022 =

12

O que configura um absurdo, pois temos:

1

2= 1122 = 1221 = 0

O sistema quantico emaranhado do exemplo, na realidade, e um sistema muito peculiar,conhecido por par EPR (Einstein, Podolsky, Rosen).

Uma propriedade muito importante de emaranhamentos e que, observando um qubit do par,sabemos exatamente em qual estado o outro esta. E algo tao contra-intuitivo que essa ligacaoentre os qubits se mantem mesmo a quilometros de distancia 7.

Os emaranhamentos terao aplicacoes muito importantes no futuro, tais como:

1. Teletransporte quantico: e possvel aproveitar a propriedade do sistema emaranhado paratransportar dados.

2. Codificacao superdensa: a partir de um qubit podemos colocar informacao na sobreposicaode forma que mais dados sejam enviados de uma vez.

3. Criptografia: pode-se fazer um mecanismo de autenticacao a partir do par emaranhado.

7Consta em [CA2] a marca de 100km!

8

3.3.4 Reversibilidade

Antes de vermos exatamente o que e a reversibilidade, e interessante vermos as portas logicasquanticas.

Assim como na Computacao Classica, a Computacao Quantica tambem depende de portaslogicas. Tais mecanismos sao usados no controle dos qubits.

Em termos de espacos de Hilbert, uma porta logica quantica nada mais e que uma trans-formacao linear unitaria, ou seja, a norma do vetor e mantida (o que e extremamente convenientelembrando que

|i|2 = 1).Entretanto, a propriedade mais interessante de uma transformacao linear unitaria e que ela

e inversvel e a inversa e sua transposta conjugada. Isso significa que teoricamente todaporta logica quantica unitaria e reversvel, coisa que nao acontece com suas avos, as portaslogicas eletricas.

Reversibilidade e a capacidade de recuperar algum estado anterior por meio de algumatransformacao inversa. Como a porta logica quantica e reversvel, podemos voltar a algumaconfiguracao anterior no meio de um processamento.

Exemplos de portas:

Hadamard ou Walsh [12

12

12 1

2

]

Pauli-X ou NOT [0 11 0

] Pauli-Y [

0 ii 0

] Pauli-Z [

1 00 1

] Phase [

1 00 i

] pi/8 [

1 00 eipi/4

] NOT [

12 1

212

12

]

3.3.5 Interferencia

A interferencia como conhecemos e aquela na qual a adicao de duas ondas e capaz de criarum novo padrao de onda. No mundo da quantica, ate as partculas sao dotadas dessa estranhapropriedade.

Em termos matematicos, podemos explicar a interferencia como uma consequencia da uti-lizacao de numeros complexos para representar sistemas quanticos. Pelo fato de os numeros

9

serem complexos, ao aplicar uma transformacao linear num sistema quantico, e possvel que onumero imaginario i seja multiplicado por outro i, gerando 1. Esse numero negativo pode,eventualmente, apagar algum escalar do vetor. As transformacoes unitarias tambem podemfazer algo parecido.

Um exemplo envolve aplicar a transformacao de Hadamard no estado: | = 12(|0+ |1).

Teremos entao:

H(|) =[

12

12

12 1

2

][12

12

]=

[10

]= 1 |0+ 0 |1 = |0

Caso seja aplicada Hadamard mais uma vez, obteremos:

H(H(|)) =[

12

12

12 1

2

] [10

]=

[12

12

]=

12|0+ 1

2|1

Apagamos o |1 e o recuperamos com a mesma transformacao. Ela interferiu tanto o apa-gando quanto o recuperando.

Outro exemplo de interferencia pode ser dado pelo experimento que usa um aparato chamadointerferometro.

O interferometro em questao consiste basicamente de um emissor de luz polarizada, doisdivisores de luz (metade refrata, metade reflete), dois espelhos perfeitos e dois detectores defotons.

Por causa da interferencia, um dos detectores nao recebera fotons como ilustrado abaixo.

Figura 1: Interferometro.

Quando a interferencia aumenta algum escalar de tal forma que ele fique maior, em modulo,do que todos os outros, temos a interferencia construtiva. Ja quando a interferencia causa aanulacao de um determinado estado, ela e chamada interferencia destrutiva.

10

3.3.6 Decoerencia

Um dos grandes problemas da Computacao Quantica, na pratica, e que os diferentes tipos dematerial do qual os qubits sao compostos nao conseguem armazenar por tempo indeterminadoas informacoes. Passado um determinado tempo, os estados sao embaralhados e a informacaose perde.

A decoerencia e justamente a perda de informacao.Atualmente, algumas implementacoes de computador quantico como a por armadilhas de

on chegam a alguns minutos [CA2], porem grande parte delas nao passa de menos de ummilissegundo.

O grande desafio e justamente garantir um tempo razoavel para que o processamento sejafeito antes de a informacao se perder.

3.3.7 Nao-Clonagem

Teorema 1 (Teorema da Nao-Clonagem[MH]). Para um sistema com n > 1 estados quanticos,nao ha uma copiadora quantica.

Demonstracao. Definamos a transformacao linear copiadora C : Hn Hn Hn tal que, dadox Hn, facamos:

C(|x |) = |x |x| e o estado para o qual queremos copiar |x.

E facil ver que C(| |) = | | e C(| |) = | |.

Pela definicao da funcao temos:

C(12

(|+ |) |) = 12

(|+ |)(|+ |) = 12| |+ 1

2| |+ 1

2| |+ 1

2| |

Por outro lado, pelo fato de C ser linear:

C(12

(|+ |) |) = 12C(| |) + 1

2C(| | = 1

2| |+ 1

2| |

Entretanto, 12| |+ 1

2| | nao pode ser decomposto na forma 1

2(|+ |)(|+ |).

Isso significa que, por um lado, C( 12(|+ |) |) tem dimensao 4 e, por outro, dimensao

2. Um absurdo!

Uma consequencia desse teorema e que nao e possvel copiar estados de sobreposicao usandoum circuito quantico, ou seja, e impossvel, no meio de um processamento, copiar um estadode sobreposicao.

Uma outra abordagem e pensarmos que e impossvel observar um estado de sobreposicao,pois, na observacao, o estado colapsa para algum estado observavel. Logo ha perda de in-formacao e nao conseguiremos copia-lo.

11

4 Computadores Quanticos na pratica

Apesar de nao haver um computador quantico plenamente funcional, ha diversos tipos dearquiteturas e projetos de construcao que exploram as mais variadas formas de compor o qubite controla-lo.

Mesmo havendo duzias de possibilidades, ha um certo padrao que e desejavel ser respeitado.

4.1 Criterio de DiVincenzo

DiVincenzo e um pesquisador da IBM que postulou cinco requisitos que devem ser obe-decidos para um computador quantico funcionar para um uso mais geral como vistos em[PQC][MAL].

4.1.1 Escalabilidade

O qubit deve ser representado adequadamente tendo seu estado de sobreposicao coerente.Tambem e necessario que seja possvel compor um sistema com uma quantidade de qubitsgrande o suficiente para o processamento ser realizado.

4.1.2 Inicializacao

Deve ser possvel fixar o valor inicial de um qubit em algum valor desejado.Fazendo um paralelo com a Computacao Classica, a inicializacao e a mesma que um pro-

gramador C faz ao declarar variaveis para garantir a integridade dos dados.

4.1.3 Tempo de Coerencia

O sistema deve ter um tempo alto de coerencia nos dados de tal forma que toda computacaonecessaria seja feita e que a taxa de erros seja a menor possvel - o que pode ser feito com recursoscomo correcao de erros quantica, mas isso demanda, de qualquer forma, mais tempo antes dadecoerencia.

O tempo de coerencia e considerado alto dependendo do tempo necessario 8 para realizaras operacoes nos qubits.

4.1.4 Portas Logicas Quanticas

Esse requisito e o responsavel pela computacao propriamente dita. Um computador quanticodeve ser capaz de realizar todas as operacoes logicas necessarias. O funcionamento delas deveser eficiente.

A implementacao de portas e, provavelmente, o requisito mais difcil de ser contempladoporque mexer num sistema quantico sem causar colapso e bastante complicado.

4.1.5 Observacao

Depois de toda computacao ser realizada, e necessario extrair os dados dos qubits. Paratanto, precisamos de meios eficientes para fazer a observacao (senao nao adiantaria de nada terfeito toda a computacao e nao poder ver o resultado).

4.2 Algumas implementacoes por alto

Toda essa secao foi escrita com base em [CA2].

8Atualmente, um tempo de coerencia razoavel e de mais de 8000 vezes o tempo para realizar as operacoes.

12

4.2.1 Armadilhas de on:

Sao usados campos magneticos e/ou eletricos e resfriamento a laser para criar um registradorquantico com um espacamento micrometrico entre os ons.

O movimento do on funciona como um barramento de dados. As portas sao implementadasmodulando os ons vizinhos usando laser.

O tempo de decoerencia 9 e de cerca de 10min! No entanto, as portas sao bastante lentas echegam a demorar alguns microssegundos para modificar dois qubits.

Outra possibilidade e integrar chips CMOS com armadilhas de on permitindo comunicacaoquantica. Na mesma linha, ha pesquisas envolvendo a combinacao de armadilhas de on comsupercondutores - procurando obter o melhor de ambas. Acredita-se que os supercondutoresajudem na comunicacao.

4.2.2 Optica:

Os qubits oriundos desse processo sao fotons que tem seus estados codificados por pola-rizacoes (verticais, horizontais ou alguma combinacao).

A vantagem e o tempo longo de decoerencia e, ainda por cima, ha a fibra optica que e,naturalmente, um candidato a meio de comunicacao quantica.

Entretanto, a criacao de fotons, bem como sua deteccao, e lenta.Um grupo da Universidade de Queensland conseguiu rodar o algoritmo de Shor (decompondo

15) num circuito optico de quatro qubits. Logo depois, Prem Kumar da Northwestern Universityanunciou uma porta logica quantica de fibra optica.

Tambem veio da optica o otimo resultado sobre o emaranhamento de 100km usando fibraoptica.

4.2.3 Supercondutores:

Os qubits podem vir de tres vias: carga, fluxo e fase. Costumam usar estados de excitacaode juncoes Josephson: dois supercondutores separados por um insulador fino o suficiente parapares de eletrons do cobre passarem.

Essa abordagem e escalavel porque a supercondutividade habilita um controle rapido aocusto da temperatura necessaria ser extremamente baixa (menos de 1K). Materiais supercon-dutores em temperatura mais elevada sao possibilidades futuras.

Outro ponto ruim do uso de supercondutores e o tempo de decoerencia baixo.

4.2.4 Adiabatico:

De forma superficial, podemos descrever como todas as combinacoes de energia cinetica epotencial de uma unica entidade o Hamiltoniano.

Nesse sentido, podemos dizer que as partculas ocupam uma posicao no Hamiltoniano. Omodelo adiabatico, como o proprio nome ja diz, nao manipula diretamente as partculas, masmanipula o Hamiltoniano.

Em palavras simples, muda-se o Hamiltoniano para resolver o problema e, depois, tenta-sevoltar ao Hamiltoniano antigo.

As chances de obter uma resposta correta estao na casa dos 90%.

4.2.5 Outros:

Existem muitas outras formas de se construir computadores quanticos, apesar de nenhumater sido bem sucedida no objetivo do computador quantico plenamente funcional.

9A leitura correta seria tempo ate a decoerencia, nao obstante a terminologia usada ser essa.

13

5 Algoritmos Quanticos

Um algoritmo classico e uma sequencia finita de instrucoes bem definidas para resolverum problema, onde cada passo ou instrucao pode ser executado por um computador classico.Analogamente, um algoritmo quantico e tambem um conjunto finito de instrucoes ordenadase nao ambguas, onde cada uma pode ser executada num computador quantico. De fato, otermo algoritmo quantico e reservado para algoritmos que usam alguma propriedade essencialda Quantica (a rigor, algoritmos quanticos sao maneiras de combinar operacoes num sistemaquantico para resolver um problema). E necessario ressaltar que qualquer problema que podeser resolvido por um computador quantico pode ser resolvido por um classico e vice-versa. Emparticular, problemas que sao indecidveis no contexto da Computacao Classica tambem o saono ambito da Computacao Quantica. Assim sendo, a Computacao Quantica nao fere a Tese deChurch-Turing, que afirma, em termos simples, que

Toda funcao que seria naturalmente computavel pode ser computada por umaMaquina de Turing.

O grande interesse nos algoritmos quanticos vem, portanto, do fato de que eles podemresolver alguns problemas mais rapidamente que os algoritmos classicos.

Seja no contexto da Computacao Classica ou da Computacao Quantica, projetar algoritmose uma tarefa complexa. Porem, quando se trata de Quantica, tal tarefa torna-se ainda maiscomplicada devido ao novo paradigma que a Computacao Quantica introduz e a`s tentativasde utilizar as propriedades da Mecanica Quantica para reduzir a complexidade de algoritmose tornar possvel solucionar - em tempo viavel - problemas intrataveis do ponto de vista daComputacao Classica.

Dada a inviabilidade de abordar com detalhes todos os algoritmos quanticos existentes,foram selecionados apenas dois deles - o primeiro pela simplicidade e importancia historica eo segundo pelo avanco que representou por apresentar uma complexidade muito menor que osalgoritmos classicos para o mesmo problema.

5.1 Algoritmo de Deutsch

O primeiro algoritmo quantico foi descrito por David Deutsch em 1989.

Suponha que nos e dado um circuito reversvel (i.e. um circuito tal que dada a sada, epossvel recuperar a entrada) que calcula uma funcao f : {0, 1} {0, 1}. Considere tal circuitouma caixa preta. O problema que o algoritmo de Deutsch resolve consiste em determinar ovalor de f(0) f(1) (i.e. a soma dos valores da funcao f modulo 2). Se determinarmos quef(0)f(1) = 0, entao saberemos que f(0) = f(1) (embora o valor da funcao seja desconhecido),e a funcao f e dita constante. Se, por outro lado, determinarmos que f(0) f(1) = 1, entaosaberemos que f(0) 6= f(1) e diremos que a funcao e balanceada. Portanto, determinarf(0) f(1) e equivalente a determinar se a funcao f e constante ou balanceada.

O problema de Deutsch consiste em, dada uma funcao f : {0, 1} {0, 1},determinar se ela e balanceada ou constante.

Se estivessemos considerando o problema do ponto de vista classico, teramos que fazer duasconsultas a` caixa preta: consultaramos primeiro, por exemplo, o valor de f(0). Mas apenasessa informacao nao seria suficiente para determinarmos f(0) f(1): seria necessario consultarnovamente a caixa preta para obter o valor de f(1).

14

Quanticamente, podemos solucionar o problema com apenas uma consulta a` caixa preta.A razao para isso esta no princpio da sobreposicao. Vamos mostrar entao como funciona oalgoritmo de Deutsch para esse problema a partir de um circuito quantico.

O circuito reversvel que calcula f pode ser transformado num circuito quantico se todaporta reversvel do circuito inicial for substituda pela sua porta quantica analoga. Tal circuitoquantico pode ser representado por

Uf : |x|y 7 |x|y f(x)Se mantivermos o segundo qubit no estado |y = |0 e o primeiro qubit em |x = |0, obte-

remos |0 f(0) = |f(0). Analogamente, se repetirmos o estado do segundo qubit e fizermos|x = |1 como estado do primeiro qubit, teremos |f(1) como sada. Portanto, com essas entra-das descritas, conseguimos exatamente o mesmo comportamento do circuito reversvel classicocom entradas 0 e 1, respectivamente.

Poderamos, no entanto, fornecer entradas tais que os qubits fossem uma sobreposicao de|0 e |1: ainda mantendo o segundo qubit da entrada no estado |y = |0, colocamos o primeiroqubit no estado

12|0+ 1

2|1 (1)

A entrada para Uf seria entao

(12|0+ 1

2|1)|0 (2)

=12|0|0+ 1

2|1|0. (3)

Na sada de Uf , teramos o estado

Uf (12|0|0+ 1

2|1|0) (4)

=12Uf |0|0+ 1

2Uf |1|0 (5)

=12|0|0 f(0)+ 1

2|1|0 f(1) (6)

=12|0|f(0)+ 1

2|1|f(1). (7)

Observe que, de certa forma, calculamos, simultaneamente, o valor de f para ambas asentradas possveis. Embora ainda existam mais alguns passos para chegar ao resultado final, epossvel concluir que o algoritmo de Deutsch resolve o problema com apenas uma consulta aoalgoritmo (sem ter que achar separadamente os valores de f para cada entrada possvel).

5.2 Algoritmo de Shor

O algoritmo de Deutsch descrito anteriormente, embora demonstre a superioridade doscomputadores quanticos sobre os classicos, lida com um problema aparentemente simples epouco relevante dentre os problemas computacionais. Provavelmente a Computacao Quanticanao teria atrado tanta atencao e nao teria evoludo tanto se seu merito pudesse ser demonstradoapenas por problemas simples. Mas, em 1994, foram mostradas as promissoras possibilidades

15

da Computacao Quantica, quando Peter Shor publicou um algoritmo quantico que resolvia umproblema intratavel em tempo polinomial.

O algoritmo de Shor resolve o seguinte problema: dado um inteiro positivo N, achar osfatores primos de N. Sob o ponto de vista da Computacao Classica, nao existe algoritmo queresolva tal problema em tempo polinomial.

O algoritmo explora o argumento de que dois fatores fatores primos p, q de um numero posi-tivo n = pq podem ser encontrados determinando-se o perodo de uma funcao f(a) = xa mod N ,para qualquer x < n que nao tenha fatores comuns com n (a menos de 1):

Algoritmo Shor(n)

1. escolha um inteiro 1 < x < n aleatoriamente

2. se mdc(x, n) > 1

3. entao devolva mdc(x, n)

4. seja r o perodo da funcao f(a) := xa mod n

5. se r for mpar ou xr2 1 (mod n)

6. entao o procedimento falhou (deve-se escolher outro x e recomecar o procedimento)

7. devolva mdc(xr2 + 1, n)

A linha 4 do pseudo-codigo foi destacada porque representa o unico passo quantico doalgoritmo: todos os outros passos podem ser executados de forma eficiente num computadorclassico (assim como num computador quantico).

Vamos entao fazer uma simulacao do algoritmo: imagine que queremos encontrar os fatoresprimos de n = 15. Tomamos um numero aleatorio x menor que n: suponha que tenhamossorteado x = 7 (note que x e n nao tem fatores comuns - a nao ser 1), e definimos a funcaof(a) = 7a mod 15. O perodo de f e r = 4 (f(a) assume os valores 1, 7, 4, 13, 1, 7, 4, . . . quandoa = 0, 1, 2, 3, 4, 5, 6, . . . respectivamente). Com essa informacao, computar os fatores de n requerapenas que seja avaliado o maximo divisor comum entre n e x

r2 + 1. Em nosso exemplo, o

calculo do maximo divisor entre 15 e 50 = 742 + 1 devolve, de fato, o valor 5, que e um dos

fatores primos de 15.O algoritmo de Shor utiliza a propriedade da sobreposicao quantica para conseguir reduzir,

atraves de funcoes quanticas especficas, a complexidade do tempo de solucao do problemade fatoracao de exponencial para polinomial. Tal algoritmo e o melhor exemplo do quanto aComputacao Quantica pode reduzir a complexidade de problemas intrataveis: a fatoracao deum numero em primos esta em NP 10 e todos os algoritmos classicos conhecidos para resolvereste problema sao exponenciais.

5.3 Outros algoritmos

Alem dos dois algoritmos apresentados, e interessante citar o algoritmo de Deutsch-Josza,que e uma generalizacao do algoritmo de Deustch. Outro algoritmo quantico bastante conhecidoe o de Grover - utilizado para buscas em bancos de dados nao estruturados e em listas naoordenadas. O algoritmo de Grover e quadraticamente mais rapido que os algoritmos classicosque resolvem o mesmo problema.

10Classe de problemas de decisao para os quais nao existem solucoes polinomiais.

16

6 Aplicacoes e possibilidades da Computacao Quantica

6.1 Criptografia Quantica

Criptografia Quantica refere-se tanto ao uso de Criptografia Classica como protecao a ata-ques quanticos, como ao uso de fenomenos da Mecanica Quantica para quebrar ou implementarsistemas criptograficos.

6.1.1 Implicacoes para a Criptografia Classica

Atualmente varios mecanismos de seguranca digital fazem uso de sistemas de criptografiaclassicos (e.g. RSA), os quais sao baseados no fato de que e difcil achar os fatores primos deum numero num tempo viavel (em computadores classicos). A descoberta de que computadoresquanticos podem resolver o problema da fatoracao em primos em tempo polinomial teve umefeito dramatico. A implementacao de tal algoritmo numa maquina fsica teria consequenciastanto cientficas como economicas.

6.1.2 Sistemas Criptograficos Quanticos

Fenomenos quanticos podem ser usados para construir e implementar sistemas criptograficosseguros. Isso porque a quantica torna possvel a geracao de chaves realmente aleatorias e, prin-cipalmente, porque permite comunicacao segura entre as partes - garantida pelas propriedadesda observacao, da nao-clonagem e do emaranhamento. Em outras palavras, um intruso quetentasse interceptar um canal de comunicacao quantico precisaria observar o estado do sistema.Primeiramente, tal intruso precisaria saber como observar o sistema. Mas ainda que tivesse essainformacao, ao efetuar a observacao, o estado do sistema quantico seria perturbado de formairreversvel, e, portanto, a interceptacao do canal nao passaria despercebida. Ademais, pelanao-clonagem, nao seria possvel para um intruso copiar o estado (desconhecido) do sistemaquantico interceptado. Finalmente, com relacao ao emaranhamento, e possvel gerar pares desistemas quanticos com estados emaranhados para comunicacao de modo que a deteccao de umsistema destruiria a correlacao com o outro sistema - tornando perceptvel uma espionagem porparte de um adversario criptografico.

Na pratica, atualmente, a Criptografia Quantica e usada para gerar e distribuir chaves.

6.1.3 Distribuicao Quantica de Chaves

Em criptografia simetrica (tambem conhecida por criptografia de chave secreta), as partesinteressadas em se comunicar conhecem uma mesma chave K: para enviar uma mensagem, aparte emissora criptografa um texto legvel x usando K, obtendo um texto ilegvel fK(x) = y.A parte receptora entao, para obter a mensagem legvel original, decriptografa o conteudorecebido usando o algoritmo inverso f1K (y), obtendo x se e so se tal receptor conhece K. Eclaro que, nesse caso, somente as partes interessadas devem poder ter conhecimento da chaveK. Para isso, e necessario que, quando do acordo sobre qual sera a chave secreta K pelas partesinteressadas (i.e. a distribuicao da chave K), nenhum invasor tenha acesso a K. O uso decomunicacao quantica no acordo sobre a chave secreta (i.e. distribuicao quantica da chave)garante a seguranca da transacao.

6.1.4 One-time pad

O algoritmo mais comumente associado com a Criptografia Quantica e o one-time pad : amensagem a ser criptografada e combinada com uma chave aleatoria (pad) cujo comprimento

17

e maior ou igual ao da mensagem. E possvel provar que o one-time pad e totalmente seguroquando segue dois criterios:

E usado com uma chave realmente aleatoria; A chave usada e mantida em segredo.Com o uso de Criptografia Quantica, as propriedades supracitadas podem ser asseguradas

(no caso da segunda, apenas parcialmente, uma vez que pode-se garantir apenas a distribuicaosegura da chave e nao a manuntencao da mesma em segredo).

6.2 Speedup de algoritmos classicos

Como dito anteriormente, algoritmos quanticos podem resolver problemas intrataveis doponto de vista classico num tempo viavel: o termo speedup refere-se ao quanto um algoritmoquantico e mais rapido que um algoritmo classico para o mesmo problema.

Adotaremos a seguinte terminologia (conforme a usada em [QAZ]): se existe uma constantepositiva tal que o tempo de execucao C(n) do melhor algoritmo classico conhecido e o tempodo algoritmo quantico Q(n) do algoritmo quantico satisfazem C = 2(Q

), entao diremos que oalgoritmo quantico prove um speedup superpolinomial. Do contrario, o speedup e dito polinomialapenas.

Para o problema da fatoracao em primos, temos o seguinte cenario: seja N o inteiro positivoa ser fatorado e seja m = blog Nc+1 (i.e. m e o numero de bits necessarios para representar N).Entao o algoritmo de Shor esta em O((log N)3), ou, equivalentemente, em O(m3), enquanto

os algoritmos classicos estao em O(e(log N)13 (log log N)

23 ) - ou em O(em) - com relacao ao tempo.

O speedup fornecido pelo algoritmo de Shor, e, portanto, superpolinomial. Se considerarmosagora o algoritmo de Grover, temos um speedup polinomial: para busca de um item numa listanao ordenada de N elementos, temos O(

N) para o algoritmo quantico e O(N) (tempo linear)

para os algoritmos classicos.A seguir, sao citados, com carater ilustrativo, alguns algoritmos quanticos e os respectivos

speedups :

Algoritmo/Problema: Busca de triangulos em grafosSpeedup: PolinomialDescricao: Suponha que temos uma caixa preta que acessa um grafo com N vertices: dado

um par de vertices, a caixa preta devolve se existe uma aresta entre eles. O problema consisteem achar um triangulo (i.e. um grafo completo de tamanho tres) no grafo (se existir). Um

algoritmo quantico para o problema tem tempo de execucao O(N32 ), enquanto os algoritmos

classicos estao em O(N2).

Algoritmo/Problema: Equacao de PellSpeedup: SuperpolinomialDescricao: Dado um inteiro positivo d que nao possui raiz inteira, a equacao de Pell e

x2 dy2 = 1. Para todo d (que satisfaz a hipotese anterior) ha infinitos pares (x, y) que saosolucao da equacao. Seja (x1, y1) o par que minimiza x+ y

d. O problema consiste em achar

tal par. Algoritmos classicos o fazem em tempo exponencial, enquanto o algoritmo quanticoconsegue a solucao em tempo polinomial (considerando o numero de bits necessarios pararepresentar d).

18

6.3 Simulacao de sistemas quanticos

Sempre que uma tecnologia nova e complexa e criada, e necessario que ela seja simulada:tanto teoricamente - atraves de equacoes matematicas, como atraves de computadores - execu-tando um programa. Quando se trata de um sistema quantico de n estados, sua simulacaorequer 2n estados. Tal proporcao exponencial torna inviavel a simulacao de tais sistemasem computadores classicos. Assim, uma das mais fundamentais aplicacoes dos computado-res quanticos e a simulacao de sistemas quanticos.

6.4 Outras aplicacoes

Outra aplicacao dos fenomenos quanticos e a geracao de numeros verdadeiramente aleatorios:usando fenomenos quanticos imprevisveis e possvel construir dispositivos para esse fim (de fato,ja existem implementacoes comerciais de hardware quantico para gerar numeros aleatorios).Alem dessa, outras possveis aplicacoes da Computacao Quantica seriam em aprendizagemcomputacional e em areas que necessitam de computacao intensa.

Ate o momento sao essas as possibilidades da Computacao Quantica. Nao esta claro, ainda,por exemplo, o potencial total da Computacao Quantica para aplicacoes comerciais. O quee fato e que a realizacao da Computacao Quantica proveria um imenso poder computacional.Provavelmente outras aplicacoes surgirao com o desenvolvimento da area.

19

7 Informacao Quantica e Correcao de Erros

7.1 Informacao Quantica - Uma visao geral

Informacao quantica e a informacao fsica contida num estado de um sistema quantico. EmComputacao Quantica, a unidade logica basica de informacao e o qubit. Os qubits diferem dosbits classicos nos seguintes aspectos:

Os bits podem assumir apenas um estado - 0 ou 1 - de cada vez. Pela propriedade dasobreposicao, qubits podem estar em mais de um estado num dado momento;

O estado de um qubit nao pode ser medido sem que haja um colapso para o estadoobservado;

Um estado desconhecido de um qubit nao pode ser clonado.Em termos simples, a maior diferenca entre a informacao classica e a quantica esta no

processamento, nao no que pode ser representado.

7.2 Teoria Quantica da Informacao

A Teoria da Informacao examina formas de representar e transmitir informacao de maneiraeficiente. A Teoria Quantica da Informacao, por sua vez, e o resultado de esforcos para gene-ralizar a Teoria Classica da Informacao para o contexto quantico: como armazenar, transmitire, sobretudo, processar informacao usando sistemas quanticos?

Muitos resultados - relacionados a observacao e entropia, por exemplo - fazem parte daTeoria Quantica da Informacao. No entanto, sera abordada aqui apenas a teoria relativa aosmecanismos de correcao de erros e tolerancia a falhas, pois tais resultados representaram umavanco significativo para a Computacao Quantica: era preciso provar que era possvel efetuarcorrecao de erros em computadores quanticos sem que isso prejudicasse o desempenho de formadrastica.

7.3 Correcao de erros

Qualquer dispositivo fsico que implementa um modelo computacional e imperfeito e limi-tado, devido a` suscetibilidade de seus componentes a` acao do ambiente: rudos geram errose resultados invalidos. Portanto, seja na Computacao Classica ou na Quantica, e necessarioimplementar algum mecanismo de deteccao e correcao de erros.

7.3.1 Correcao de erros classica

Para diminuir a probabilidade de ocorrencia de erros, a tecnica mais utilizada e a re-dundancia.

No caso de um canal de comunicacao binario classico, usar um bit de paridade e um dosmecanismos mais simples de redundancia: alem dos bits usados para representar a informacaopropriamente dita, um bit a mais e transmitido para informar se o numero de bits 1 dainformacao e par ou mpar.

Outra forma de garantir redundancia e a repeticao de dados. Por exemplo, poderamos usartres bits 1 para representar um unico 1, dessa forma, dois bits precisariam ser perturbadospara que ocorresse um erro.

20

Exemplo de repeticao:Um unico bit e representado por tres bits :

Codificacao:1 1110 000

Decodificacao:000 0, 001 0, 010 0, 100 0111 1, 110 1, 101 1, 011 1

Outro metodo ainda seria fazer uso de checksums : calcular uma certa funcao sobre os bitsda informacao. Se houver divergencia entre o valor do checksum calculado e o transmitido, ecerto que ocorreram erros.

7.3.2 Correcao de erros quantica

Computadores quanticos sao mais suscetveis a erros que os classicos, porque sistemasquanticos sao mais delicados e difceis de controlar, devido aos fatores mencionados no inciodesta secao.

Contudo, e possvel generalizar os mecanismos de redundancia descritos para a correcaoclassica para produzir correcao de erro quantica. Considere, por exemplo, a repeticao classica:a repeticao quantica e, de certa forma, analoga. A diferenca fundamental esta na copia dosqubits : qubits com estados sobrepostos, devido a` nao-clonagem, nao podem ser copiados dire-tamente. Assim sendo, para prover repeticao, usam-se os estados emaranhados. Alem disso,as observacoes de qubits para deteccao de erro devem ser feitas de forma que nao se percainformacao: isso e possvel de modo que so se saiba se ocorreu um erro ou nao - a informacaoarmazenada propriamente dita nao e observada.

De qualquer forma, embora seja possvel estabelecer um paralelo entre a correcao classica equantica, esta ultima e de fato mais complexa e delicada - talvez tao complicada que suspeitou-se que fosse ineficiente a ponto de prejudicar a utilidade dos computadores quanticas. Noentanto, prova-se que e possvel realizar correcao de erros em computadores quanticos comum overhead polinomial (o chamado Teorema Quantico de Tolerancia a Falhas - ou ThresholdTheorem - garante tal resultado).

21

8 Onde se faz Computacao Quantica?

A maioria dos resultados em Computacao Quantica - alguns dos quais foram mostrados aqui- sao oriundos de pesquisas academicas. No entanto, e fato que muitas organizacoes comerciaiscontriburam - e vem contribuindo cada vez mais - para o desenvolvimento da area: nao so de-senvolvendo prototipos de computadores quanticos e produtos viaveis que utilizam propriedadesda Quantica, mas tambem publicando pesquisas que concernem a aspectos teoricos.

8.1 Computacao Quantica na Academia

Muitas universidades - sobretudo na Europa e America do Norte - possuem institutos oucentros dedicados a` pesquisa e ao ensino de Computacao Quantica: e o caso, por exemplo, daUniversidade de Waterloo, no Canada, e do MIT - Massachusetts Institute of Technology, nosEstados Unidos (em 1981, na First Conference on the Physics of Computation no MIT, RichardFeynmann apresentou a ideia de computadores quanticos).

Foi na Universidade de Oxford, Inglaterra, que David Deutsch publicou muitos de seusfamosos trabalhos na area: como a descricao da Maquina de Turing Quantica em 1985. Aindaem Oxford, foi realizada a primeira demonstracao experimental de um algoritmo quantico: em1998 foi executado o algoritmo de Deutsch num computador quantico de 2 qubits.

Atualmente, ha pesquisa em diversas areas como algoritmos, implementacoes de computado-res quanticos a partir das mais variadas tecnologias, experimentos com propriedades quanticas(e.g. transmissao de dados a partir do par EPR) entre outros.

Com o advento da Internet, e bem mais facil acompanhar todo esse desenvolvimento atravesde bibliotecas online como a arXiv da Cornell University.

8.2 Empresas e companhias que atuam com Computacao Quantica

Shor e Grover publicaram os algoritmos que levam seus nomes, respectivamente, em 1994e 1996, quando trabalhavam nos laboratorios da AT&T (empresa americana de telefonia ecomunicacao).

Outra empresa que vem pesquisando Computacao Quantica ha algum tempo e a IBM:David DiVincenzo - cujos famosos criterios foram apresentados anteriormente - e pesquisadorna empresa desde 1985. A IBM ainda teve participacao - juntamente com a Universidade deStanford - na primeira execucao do algoritmo de Shor, em 2001, fatorando o numero 15 usandoum computador quantico.

Recentemente, a gigante Google anunciou uma parceria com uma empresa canadense decomputacao quantica - a D-Wave. Tal alianca teria o proposito de desenvolver computadoresquanticos para busca de imagens e aprendizagem computacional.

Vale citar tambem que ha empresas, como a suca IDQ, que fornecem produtos que naosao computadores quanticos completos, mas que usam propriedades da Quantica: entre elesfiguram geradores de numeros realmente aleatorios e hardware para Criptografia Quantica.

Com o aumento da popularidade da Computacao Quantica, a tendencia e que mais empresasse aventurem nessa area.

8.3 Computacao Quantica no Brasil

Apesar de o cenario nao ser tao favoravel a esse tipo de pesquisa quanto e na Europa ou naAmerica do Norte, o Brasil tambem tem seus centros de pesquisa como o Grupo de ComputacaoQuantica do Laboratorio Nacional de Computacao Cientfica (LNCC) que atua nas seguinteslinhas:

22

Problema do Subgrupo Escondido; Estrutura Matematica de Algoritmos Quanticos; Estrutura Matematica de Computacao Reversvel; Jogos Quanticos; Informacao Quantica; Passeio Aleatorio Quantico; Simulacao de Algoritmos Quanticos em Computadores Classicos.Recentemente11, no Instituto de Fsica da USP, pesquisadores conseguiram manipular feixes

de luz de forma a deixa-los emaranhados [FS]. Do ponto de vista da Informacao Quantica, esseexperimento foi muito importante, pois trouxe uma forma razoavel de transmissao de dadospor luz.

E provavel que haja um crescimento nas linhas de pesquisa em Computacao Quantica noBrasil, uma vez que a area esta se tornando cada vez mais popular dentre os pesquisadores domundo todo.

11Outubro de 2009.

23

9 Conclusao

Im not sure what you mean by a mainstream field. To me, quantum computingalready looks pretty mainstream. Michael Nielsen, Ph.D

Em alguns anos, se a Lei de Moore for preservada, os transstores chegarao a` dimensaoatomica e uma forma diferente de computacao seguira a partir de tal ponto. Apesar de aindanao termos uma previsao de computador quantico a medio prazo, a Computacao Quantica temtudo para ser a sucessora do paradigma atual de computacao.

Ademais, o computador quantico nao possui uma forma especfica para ser construdo 12

isso significa que muitos projetos nascerao e muitos cairao ate termos, de fato, um computadorquantico plenamente funcional. Alem disso, com apenas 10000 qubits, o speedup garante que opoder de processamento atingira um nvel que nenhum computador classico conseguira alcancar!

Estudar Computacao Quantica, hoje, talvez seja bem parecido com o estudo de Computacaono passado - ja que o que temos em funcionamento e apenas um modelo teorico. Entretanto,sua complexidade e muito maior dada a natureza nao intuitiva dos fenomenos quanticos.

Mesmo com toda a dificuldade que envolve o estudo de Quantica, o mar de possibilidadesdentro do que ainda esta para vir faz com que seu estudo, ainda sim, seja algo fascinante!

12Ha diversas implementacoes usando desde luz ate ons. Veja em [MAL].

24

Referencias

[QCQ] NIELSEN M., CHUANG I., Quantum Computation and Quantum Information,Cambridge Press, 2000.

[MH] HIRSVENSALO, M., Quantum Computing,Springer, 2a edicao, 2003.

[IQC] KAYE P., LAFLAMME R., MOSCA M., An Introduction to Quantum Computing,Oxford, 2007

[MAL] CHEN G. et al, Quantum Computing Devices - Principles, Design and Analysis,Taylor & Francis Group, 2007.

[CSF] CARDONHA C., SILVA M., FERNANDES C., Computacao Quantica: Complexidadee Algoritmos,

IME-USP, 2004.

[CQ] ALLEGRETTI, Francisco J. P., Computacao Quantica,UFRGS, 2004.

[TQC] PERRY, RILEY T., The Temple of Quantum Computing,http://www.toqc.com/TOQCv1 1.pdf

[CA2] ROSS M., OSKIN M., Quantum Computing - Researchers are optimistic, but a praticaldevice is years away,

Communications of the ACM, Vol. 51, no. 7, 2008.

[ARS] ARS Technica, Adiabatic Quantum Computing,http://arstechnica.com/science/news/2007/02/7008.ars

[CA1] BACON, D., VAN DAM, W., Recent Progress in Quantum Algorithms,Communications of the ACM, Vol. 53, no. 2, 2010.

http://goo.gl/RjR5Z

[PQC] DIVINCENZO, DAVID P., Prospects for Quantum Computing,http://www.research.ibm.com/ss computing/iedm01.doc

[GE] GECCO-2008, Quantum Computing,http://www.cs.bham.ac.uk/ wbl/biblio/gecco2008/docs/p2865.pdf

[IS] Science and Technology resources on the Internet, Quantum Computing,http://www.istl.org/09-spring/internet.html

[N1] LADD, T.D. et al, Quantum Computers,Nature, vol. 464, 03/2010

http://www.nature.com/nature/journal/v464/n7285/full/nature08812.html

[N2] KNILL E., Quantum Computing Q&A,Nature, vol. 463, 01/2010

[FS] Entangled colors,Pesquisa FAPESP, October 2009, Edicao 164 http://goo.gl/yolWf

[MN] Michael Nielsen, Quantum Computing for everyone,http://michaelnielsen.org/blog/quantum-computing-for-everyone/

25

[QAZ] Caltech, Quantum Algorithm Zoo,http://www.its.caltech.edu/~sjordan/zoo.html

[aX1] MOSCA, M. Quantum Algorithms,http://arxiv.org/abs/0808.0369

arXiv:0808.0369v1 [quant-ph]

[IB1] MURCH, R., Quantum Computing: The Hype and Reality,IBM Press, 2005,

http://www.ibmpressbooks.com/articles/article.asp?p=374693

[CH] CHUANG I., Quantum Information - Joining the Foundations of Physics and ComputerScience

MIT Physics Anual 2004, 2004.

[TC] HARRISON, David M., Quantum Teleportation, Information and Cryptography,http://www.upscale.utoronto.ca/PVB/Harrison/QuantTeleport/QuantTeleport.html

[ST1] Stanford Encyclopedia of Philosofy, Quantum Computing,http://plato.stanford.edu/entries/qt-quantcomp/

[ST2] Stanford Encyclopedia of Philosofy, Quantum Entanglement and Information,http://plato.stanford.edu/entries/qt-entangle/

[WB1] Wikibooks, Breve introducao a` Computacao Quantica,http://goo.gl/LNltZ

[WK1] Wikipedia, Laser Cooling,http://en.wikipedia.org/wiki/Laser cooling

[WK2] Wikipedia, Quantum Algorithm,http://en.wikipedia.org/wiki/Quantum algorithm

[WK3] Wikipedia, Shors Algorithm,http://en.wikipedia.org/wiki/Shors algorithm

[WK4] Wikipedia, Grovers Algorithm,http://en.wikipedia.org/wiki/Grovers algorithm

[WK5] Wikipedia, Quantum Cryptography,http://en.wikipedia.org/wiki/Quantum cryptography

[WK6] Wikipedia, Quantum Key Distribution,http://en.wikipedia.org/wiki/Quantum key distribution

[WK7] Wikipedia, Quantum Error Correction,http://en.wikipedia.org/wiki/Quantum error correction

[WK8] Wikipedia, Timeline of quantum computing,http://en.wikipedia.org/wiki/Timeline of quantum computing

[WP1] Wikipedia, Criptografia Quantica,http://pt.wikipedia.org/wiki/Criptografia qua^ntica

[WP2] Wikipedia, One-time Pad,http://pt.wikipedia.org/wiki/One-time pad

26

IntroduoHistricoFsica QunticaComputao Quntica

O bsicoEspaos de Hilbert e algumas notaesQuantum Bits ou qubitsPor que quntica?SobreposioObservaoEmaranhamentoReversibilidadeInterfernciaDecoernciaNo-Clonagem

Computadores Qunticos na prticaCritrio de DiVincenzoEscalabilidadeInicializaoTempo de CoernciaPortas Lgicas QunticasObservao

Algumas implementaes por altoArmadilhas de on:ptica:Supercondutores:``Adiabtico'':Outros:

Algoritmos QunticosAlgoritmo de DeutschAlgoritmo de ShorOutros algoritmos

Aplicaes e possibilidades da Computao QunticaCriptografia QunticaImplicaes para a Criptografia ClssicaSistemas Criptogrficos QunticosDistribuio Quntica de ChavesOne-time pad

Speedup de algoritmos clssicosSimulao de sistemas qunticosOutras aplicaes

Informao Quntica e Correo de ErrosInformao Quntica - Uma viso geralTeoria Quntica da InformaoCorreo de errosCorreo de erros clssicaCorreo de erros quntica

Onde se faz Computao Quntica?Computao Quntica na AcademiaEmpresas e companhias que atuam com Computao QunticaComputao Quntica no Brasil

Concluso