Embed Size (px)
Citation preview
_____________________________________ ¹ Graduando em Sistemas de Informação ² Orientador especialista em Análise de Sistemas ³ Teoria física que obtém sucesso no estudo dos sistemas físicos cujas dimensões são próximas ou abaixo da escala atômica. 4 Menor unidade de informação que pode ser armazenada ou transmitida, usada na Computação. 5 Partícula subatômica que circunda o núcleo atômico.
A EFICIÊNCIA DA COMPUTAÇÃO QUÂNTICA
Jallysson Miranda Rocha¹
Thales Will Silva Reis²
RESUMO
A computação quântica é um novo modelo computacional que utiliza todos os princípios da mecânica quântica³, com paradigmas diferentes da computação convencional, sua performan-ce em resolver problemas de classes da complexidade clássica é bastante superior ao de qual-quer outro computador convencional. Sendo capaz de ler mais de um ou todos os dados de entrada ao mesmo tempo, através do bit4 quântico, em superposição. Outro princípio que faz da computação quântica superior a atual é o Emaranhamento quântico, que permite conhecer dados distintos e separados sem conexão alguma, através de um único elétron5, que de certa forma está interligado aos outros. Muitos algoritmos quânticos já foram desenvolvidos, e re-solvem problemas bastante complicados, como o Algoritmo de Shor, que fatora números bas-tante complexos, e o de Grover, que busca dados em bases de dados desordenadas de grande proporção de dados. Estes foram os primeiros algoritmos desenvolvidos com todos os funda-mentos da computação quântica. A eficiência dos computadores quânticos é um dos principais motivos de se investir em estudos e desenvolvimento de computadores que possam executar todas as tarefas realizadas por computadores convencionais, e problemas das classes de com-plexidade de dados. Assim a pesquisa realizada mostra as principais características e princí-pios da mecânica quântica utilizadas na computação quântica, enaltecendo a eficiência dos algoritmos quânticos com ênfase no algoritmo de Grover. Com objetivo geral de explorar os princípios da mecânica quântica, em especifico detalhar a eficiência destes princípios na com-putação quântica. São realizados levantamentos bibliográficos e revisão de literatura, de livros e artigos científicos sobre mecânica quântica, computação quântica e algoritmos quânticos. PALAVRAS-CHAVE: Mecânica quântica. Computação quântica. Algoritmos quânticos.
Complexidade.
1 INTRODUÇÃO
Um novo modelo de computação conhecido como computação quântica, que utiliza os
princípios da mecânica quântica, surgiu da necessidade de resolver problemas bastantes
complexos presentes em classes de problemas da complexidade de dados clássica, que não
podem ser resolvidos com eficiência em computadores convencionais. Muitos algoritmos
2
quânticos já foram desenvolvidos, que resolvem problemas bastantes complexos, como os
primeiros algoritmos de Shor, que fatora números bastantes complexos, e o de Grover, que
busca dados em bases de dados desordenadas de grande proporção de dados. Com o cresci-
mento da mecânica quântica, empresas de tecnologia começaram a investir em estudos e de-
senvolvimentos de computadores quânticos.
A eficiência dos computadores quânticos, é um dos principais motivos de se investir
em estudos e desenvolvimento de computadores que possam executar todas as tarefas realiza-
das por computadores convencionais, e problemas das classes de complexidade de dados.
Assim a pesquisa realizada visa as principais características dos princípios da mecânica quân-
tica utilizadas na computação quântica, enaltecendo a eficiência dos algoritmos quânticos com
ênfase no algoritmo de Grover. Com objetivo geral de explorar os princípios da mecânica
quântica, em especifico detalhar a eficiência destes princípios na computação quântica. Reali-
zada por meio de levantamentos bibliográficos e revisão de literatura, de livros e artigos cien-
tíficos sobre mecânica quântica, computação quântica e algoritmos quânticos.
2 MECÂNICA QUÂNTICA
Tem como objetivo estudar os eventos que ocorrem nas camadas atômicas e subatômi-
cas, explicando problemas que eram vistos, como sem solução na física clássica. E “quando se
estuda o nível atômico e subatômico, esta teoria corrige e complementa a Física Clássica,
usualmente abordada em dois ramos: Mecânica Newtoniana e Eletromagnetismo.” (OLIVEI-
RA, 2007, pg. 06). Após a sua aceitação, proporcionou o avanço de muitas áreas, como a
computação.
A física quântica é a teoria científica que descreve os objetos microscópicos, como átomos, e sua interação com a radiação (luz, etc.). Como ela é uma teoria muito bem sucedida, pode-se dizer que qualquer fenômeno microscópico é um fenômeno quân-tico. Assim, como nosso cérebro é constituído de entidades microscópicas, num sen-tido trivial nosso cérebro é quântico, assim como nossa consciência (supondo o ma-terialismo). (PESSOA, 1994, Pg. 185).
É o principal modelo para o novo paradigma de computação, denominado computação
quântica, que utiliza todos os conceitos da mecânica quântica proporcionando um ganho em
performance bastante superior aos melhores modelos de computadores clássicos já existentes.
2.1 HISTÓRIA DA MECÂNICA QUÂNTICA
3
Iniciou-se após um ato de desespero na tentativa de explicar um fenômeno visto como
não solucionável na física clássica, conhecido como catástrofe do ultravioleta ou também
chamada de catástrofe de Rayleigh-Jeans, onde o físico alemão Max Karl Ernst Ludwig
Planck, defendeu que a energia eletromagnética poderia ser transmitida em pacotes discretos
de energia proporcionais a frequência, assim em sua lei determinou que a matéria só poderia
emitir ou observar energia em pequenas quantidades, conhecidas como “quanta” e posterior-
mente chamada de “fóton”, e para definir o tamanho desses “quanta” surgiu a constante de
Planck. “O comportamento de partículas subatômicas é o tema da física quântica, assim
chamado porque nessa escala incrivelmente pequeno, tudo parece quantizada, ou quebrado em
pedaços pequenos.” (GLASSNER, 2001, pg. 84, Tradução nossa). Quando se fala em uma data histórica para a origem da Mecânica Quântica sempre se pensa no mês de dezembro de 1900; foi nesse período que Max Ludwig Planck (1858-1947) em seus estudos sobre a radiação do corpo negro introduziu o conceito de quantum que significa em latim, unidade mínima, indivisível, lembrando o átomo de matéria. (ROSA, nd, pg. 02).
A lei de Planck estabelece que a energia (E) é igual a um número inteiro (n), multipli-
cado pela constante de Planck (h), multiplicado pela frequência da luz (ni), onde: E = n . h . v.
Figura 1 Catástrofe do ultravioleta ou também chama a figura de catástrofe de Rayleigh-
Jeans.
Fonte: http://www.if.ufrgs.br/~betz/iq_XX_A/radTerm/aRadTermFrame.htm
Os trabalhos de Planck atraíram a atenção de muitos físicos, como o alemão Albert
Einstein, que realizou grandes descobertas usando os trabalhos de Planck, como a lei do efeito
fotoelétrico, que fortaleceu a teoria quântica. Assim a teoria quântica, se fortaleceu com Max
4
Planck e Albert Einstein no inicio do século XX, com prêmios Nobel importantes e com con-
tribuições do dinamarquês Niels Henrick David Bohr e o alemão Werner Karl Heisenberg.
Onde Bohr melhora uma das teorias de Ernest Rutherford, que possuía algumas lacunas não
justificadas, a respeito do átomo, e com os trabalhos de Planck e Einstein ele soluciona essas
lacunas, e junto com Heisenberg surge o principio da incerteza. Após todas essas leis e teorias
a Mecânica quântica se firmou diante da Física clássica, e possuí conceitos e descobertas co-
mo o Emaranhamento quântico, bastante importante para outras áreas, como a computação.
2.2 PRINCIPÍO DA INCERTEZA DE HEISENBERG
“Uma das afirmações feitas pela Mecânica Quântica é de que não podemos determinar
ao certo a trajetória de uma partícula. Esta insegurança em não saber como administrar algo
que não pode ser determinado é denominada Princípio da Incerteza.” (CARDOSO; REISER;
COSTA, nd, pg. 03). Diferente da física clássica, em que as partículas de um sistema podem
ser observadas, conhecendo suas massas e velocidades, e assim determinar suas interações e
prever seus comportamentos. Na mecânica quântica, não se tem uma trajetória definida, e o
fato de observar e alterar o resultado de uma partícula, impede que sejam previstos seus com-
portamentos e interações entre si.
Os princípios de Heisenberg, é aplicado somente ao mundo subatómico, onde para
medir a posição de um elétron é necessário incidir um fóton com bastante intensidade sobre
esse, devido o fato de quanto maior for a frequência, menor será o comprimento de onde deste
fóton.
2.3 SUPERPOSIÇÃO COERENTE DE ESTADOS DISTINTOS
Na mecânica quântica, um dos fenômenos conhecido como Superposição coerente de
estados distintos, consiste em um elétron está em todos os estados possíveis em um sistema
antes que este seja observado. “A superposição ou sobreposição é talvez o mais conhecido
efeito do modelo quântico. É a propriedade que os qubit possuem de registrar ao mesmo tem-
po diferentes valores.” (OLIVEIRA, 2007, pg. 10).
Este sistema quântico entra em superposição de acordo com o princípio, em que os
elétrons agem como uma onda, causando interferência entre si, conforme a figura a seguir.
5
Figura 2 Experimento de Young da fenda dupla.
Fonte: http://www.if.ufrgs.br/tex/fisica-4/young.gif
2.4 EMARANHAMENTO QUÂNTICO
É um dos principais recursos para a eficiência da computação quântica, e “dizemos
que um estado quântico está emaranhado quando é impossível representá-lo como produto
tensorial de outros dois estados de um q-bit.” (LAGO et al, nd, pg. 867). Conhecido também
como entrelaçamento quântico, expressão elaborada originalmente pelo físico austríaco Erwin
Schrödinger, após realizar um experimento conhecido como Gato de Schrödinger. Em que o
experimento demonstra a relação entre o universo cotidiano ao universo da mecânica quânti-
ca, conforme a figura a seguir.
Figura 3 Gato de Schrodinger
Fonte: http://www.misteriosdouniverso.net/2014/05/a-interpretacao-de-copenhague-e-o-gato.html
6
A teoria do emaranhamento quântico, diz que mais de um objeto estão relacionados de
alguma forma, em que mesmos em dimensões diferentes ou em qualquer outra distância, con-
tinuam relacionados. Assim qualquer alteração em algum dos objetos implicará a mesma
alteração nos demais objetos relacionados a este. “Os sistemas quânticos quando combinados
possuem a característica de não poderem mais ser descritos como dois espaços, mas sim, co-
mo um único espaço maior.” (OLIVEIRA, 2007, pg. 11).
2.5 ESPAÇO DE ESTADOS
“O estado de um sistema físico descreve suas características físicas em um determina-
do instante.” (BARCELOS; ANDRADE; BOAVENTURA, 2010, pg. 11).
Os sistemas quânticos, possuem caraterísticas como ocupar mais de um estado em um
mesmo objeto, esse espaços são representados por vetores. Dois estados em um espaço quân-
tico, não representa exatamente só esses, mas sim muitos estados. “Um sistema físico isolado
tem associado um espaço de Hilbert, chamado de espaço de estados. O estado do sistema é
totalmente descrito por um vetor unitário, chamado de vetor de estado, nesse espaço de Hil-
bert.” (BARCELOS; ANDRADE; BOAVENTURA, 2010, pg. 14).
2.5.1 Postulados
“Uma mecânica pode ser vista como um conjunto de propriedades aplicáveis no estu-
do e manipulação de sistemas físicos.” (OLIVEIRA, 2007, pg. 05).
2.5.2 Postulado de Hilbert
“Este primeiro postulado associa um sistema físico qualquer a um espaço vetorial
complexo denominado Espaço de Hilbert.” (OLIVEIRA, 2007, pg. 05).
Existe, para cada sistema físico isolado, um espaço vetorial complexo com produto interno (ou seja, um espaço de Hilbert), conhecido como espaço de estados do sis-tema. O sistema é completamente descrito por seu vetor estado, que é um vetor uni-tário no espaço de estados do sistema. Segundo NIELSEN e CHUANG (apud LA-GO, nd, pg. 866).
2.5.3 Operadores Unitários
7
“A evolução de um sistema quântico de um estado |Ψ1› para um estado |Ψ2› se dá
através da aplicação de um operador unitário U. Um operador é definido como uma matriz
quadrada com as dimensões do espaço em questão.” (OLIVEIRA, 2007, pg. 06).
2.5.4 Medições
A principal característica do postulado de Medição, são quer “[...] os sistemas quânti-
cos são fechados por definição, pois as leituras externas interferem no próprio estado lido.”
(OLIVEIRA, 2007, pg. 07). Alterando o estado final para um outro diferente do original, apos
sofrer interferência externa.
2.5.5 Composições de Espaços
“O espaço de estados de um sistema físico composto é o produto tensorial dos espaços
de estado dos sistemas que o compõem.” (LAGO, nd, pg. 867).
“A questão abordada por este postulado é a montagem de sistemas quânticos eficazes
utilizando vários qubit.” (OLIVEIRA, 2007, pg. 09).
3 COMPUTADORES QUÂNTICOS
“O século XX apresenta os grandes passos do desenvolvimento científico necessários
para o surgimento da chamada Computação Quântica (CQ), originada de uma vertente da
Física hoje conhecida como Mecânica Quântica (MQ).” (OLIVEIRA, 2007, pg. 04). Seguindo
os princípios da mecânica quântica com o objetivo de realizar tarefas em que os computadores
clássicos não conseguem realizar ou que levam bastante tempo para concluir. Porém é preciso
conhecer um novo paradigma, para poder desenvolver computadores quânticos, e programas
que atendam aos princípios da mecânica quântica.
A Computação Quântica (CQ) é um novo paradigma que utiliza a Mecânica Quânti-ca como base para o processamento e transmissão de informação. Esta mudança de paradigma parece estar no caminho natural da evolução tecnológica, já que a redu-ção no tamanho dos componentes dos atuais computadores, se aproxima rapidamen-te do nível atômico. (OLIVEIRA, 2007, pg. 01).
8
3.1 HISTÓRIA DA COMPUTAÇÃO QUÂNTICA
A necessidade de um novo modelo de computação surgiu da necessidade de resolver
problemas bastantes complexos e demorados que a computação clássica até resolveriam, mas
não no tempo viável. Com o crescimento da mecânica quântica, empresas de tecnologia co-
meçaram a investir em estudos e desenvolvimentos de computadores quânticos, o primeiro
computador quântico foi construído pela D-Wave não sendo totalmente quântico, mas que
mostrou resultados satisfatórios e a possibilidade de se ter um computador totalmente quânti-
co no futuro.
Muitos algoritmos quânticos já foram desenvolvidos, que resolvem problemas bastan-
tes complexos, como o Algoritmo de Shor, que fatora números bastantes complexos, e o de
Grover, que busca dados em bases de dados desordenadas de grande proporção de dados. Es-
tes foram os primeiros algoritmos desenvolvidos com todos os fundamentos da computação
quântica. Recentemente os estudos e desenvolvimentos mais estáveis, estão sendo realizados
por parcerias entre: Google, NASA e D-Wave
Figura 4 Computadores quântico D-Wave 2
Fonte: http://rcristo.com.br/2014/06/02/d-wave-2-vesuvius-512-qbits-a-segunda-geracao-de-
computadores-quanticos-comerciais/
3.2 CONCEITO DE COMPUTADOR QUÂNTICO
9
Um computador quântico é baseado nos conceitos da Mecânica quântica, que vai além
da capacidade de um computador clássico atual, e sua estrutura é composta por registradores
quânticos e portas lógicas quânticas, e seus resultados se baseiam em estatísticas.
Um computador quântico é difícil de implementar, devido à dificuldade em resolver
um dos princípios da computação quântica conhecido, como superposição coerente de estados
distintos, este é um ponto que faz da computação quântica superior a Computação clássica.
Mesmo não existindo muitos computadores quânticos até hoje, e os que já foram feitos não
realizarem todas as tarefas que os atuais fazem, seus algoritmos já vêm sendo estudados e
desenvolvidos a bastante tempo, antes mesmo de desenvolver o computador físico em si.
Desenvolver algoritmos quânticos não é uma tarefa fácil pois é preciso conhecer os
princípios da mecânica quântica e o funcionamento de um computador quântico, desde suas
portas quânticas até lidar com as superposições e as incertezas presente em computadores
quânticos.
3.3 PRINCÍPIOS DA COMPUTAÇÃO QUÂNTICA
A computação quântica segue os padrões da mecânica quântica em que um elétron po-
de ser uma partícula e uma onda em algum momento e utiliza leis comprovadas teoricamente
e experimental por grandes físicos renomeados. Compõe-se de princípios fundamentais, que
demostram como um computador quântico, é muito superior a um computador no modelo
clássico. Capaz de ler mais de um ou todos os dados de entrada ao mesmo tempo, através do
bit quântico, em superposição.
3.4 O BIT QUÂNTICO (Q-BIT)
Em um Computador Quântico, a unidade de medida é o bit quântico (qubit), que dife-
rente da computação clássica que assume o valor de 0 ou 1, o bit quântico pode assumir um
destes dois estados, como pode entrar em superposição coerente de estados distintos e assumir
mais de um estado ao mesmo tempo. “Para fazer uso das propriedades quânticas na computa-
ção, fez-se necessária uma redefinição da forma de representação da informação. Ao invés de
utilizarmos bits, utilizamos os bits quânticos - q-bits - que são representados por |0› e o |1›.”
(LAGO, nd, pg. 866). conforme a figura a seguir.
10
Figura 5 Bit quântico (qubit).
Fonte: http://www.comppet.ufu.br/printf/?q=content/entendendo-melhor
Com essa possibilidade um computador quântico pode ler toda uma entrada de dados
ao mesmo tempo e ter uma velocidade surpreendente comparada aos computadores já desen-
volvidos, “Em princípio, e possível construir um qubit que contenha em si uma quantidade
arbitrariamente elevada de informação, bastando para tal codificar essa informação nas ampli-
tudes” (AMOREIRA, nd, pg. 05), mas não é garantido que toda a entrada seja lida ao mesmo
tempo e nem quantos dados serão lidos usando esse princípio, mas a mecânica quântica garan-
te que é possível de ocorrer, e tudo é previsto por meio de estatística.
4 COMPUTAÇÃO QUÂNTICA X COMPUTAÇÃO CONVENCIONAL
A computação evoluiu bastante desde os primeiros computadores, o nível de proces-
samento de dados avançou bastante e continua avançando, porém ainda existem muitos pro-
blemas sem solução, e que exigem computadores superiores que resolvem estes problemas e
de maneira rápida. A computação quântica surgiu para realizar tarefas demoradas nos compu-
tadores convencionais e a resolver problemas que eram vistos como sem solução.
Mesmo os computadores quânticos serem bastantes superiores aos computadores con-
vencionais em processamento, ainda são vistos apenas como complemento da computação
clássica que se tem atualmente. Os computadores convencionais ainda são indispensáveis, e
mesmo que sua velocidade em problemas complexos sejam bastantes inferiores aos modelos
quânticos, estes são melhores em resolver problemas comuns.
Os computadores que temos hoje, já se encaminha ao modelo quântico, a medida que
os transistores diminuem seu tamanho, ocorrendo a evolução do modelo atual para o novo
modelo dos computadores quânticos.
4.1 APLICAÇÕES PARA A COMPUTAÇÃO QUÂNTICA
11
A computação clássica, não atende a todos os problemas existentes em período de
tempo razoável, e muitos problemas que podem ser considerados impossíveis de se conseguir
fazer, podem ser bem efetivados utilizando a computação quântica. Problemas como fatoração
de números bastantes complexos e busca de dados em grandes bases de dados desordenadas,
em que necessita muito tempo e um grande poder de processamento no modelo convencional
atual. “Interesse da NASA em computação quântica é baseado em parte em potenciais ganhos
de eficiência para os tipos de problemas computacionais associados com capacidades de
autonomia a bordo.” (HUGHES; WILLIAMS, 2000, pg. 10, Tradução nossa).
Para esses problemas e muitos outros, já foram desenvolvidos algoritmos quânticos,
que já foram comprovados cientificamente, sua ótima performance, o Algoritmo de Peter
Shor para fatoração de números e o Algoritmo de Grover para busca de dados em bases de
dados desordenadas.
Figura 6 Tabela do desempenho do Algoritmo de Shor em relação aos algoritmos clás-
sicos.
Fonte: http://www.gta.ufrj.br/grad/10_1/quantica/quantica.html
4.2 COMPUTAÇÃO QUÂNTICA E A SEGURANÇA DA INFORMAÇÃO
Se tratando de segurança da informação atual, o modelo computacional quântico pode
trazer bons e maus problemas, porque um computador quântico estável, usado em um algo-
ritmo de criptografia clássico pode ser facilmente quebrável em pouquíssimo tempo, com-
prometendo toda a segurança do modelo clássico. Visto de outra forma um computador quân-
tico pode finalmente garantir total segurança por meio de criptografias quânticas, em relação
ao modelo convencional e a própria computação quântica.
12
Figura 7 Confiabilidade da criptografia da computação quântica.
Fonte: http://www.gta.ufrj.br/grad/08_1/quantica/cap4.html
O estudo da criptografia quântica ainda está em crescimento, mas ainda continua sen-
do uma promessa futura assim como os computadores quânticos. A criptografia quântica, é
responsável pelo transporte da informação criptografada, e caso os dados sejam capturados no
canal por outras pessoas indevidas, a informação é alterada para manter a confidencialidade.
Se houver alguma diferença entre os fótons enviados e os recebidos, isso indica que houve tentativa de interceptação da mensagem e, portanto, a chave criptográfica transmitida deve ser descartada. Qualquer tentativa do interceptador de reproduzir o fóton interceptado, enviando a cópia ao receptor final, para que ele não desconfie da interceptação, será fadada ao fracasso, devido à impossibilidade de clonagem quântica. (CARDONHA; SILVA, 2004, pg. 67).
4.3 COMPUTAÇÃO QUÂNTICA E A CLASSIFICAÇÃO DE DADOS
A classificação de Dados ainda é um problema sendo estudado no mundo quântico,
por ser baseado em estatísticas, e não se ter um resultado exato, ainda é um fato que impossi-
bilita ampliar a computação quântica ao cotidiano das pessoas. “A mecânica quântica não
pode fazer previsões exatas. Para um dado estado inicial do elétron, uma medida subsequente
pode dar vários resultados.” (OBRA COLETIVA, nd, pg. 09).
Assim medir um dado quântico é algo difícil, porque só pelo fato de observar o resul-
tado já sofre interferência, para os programadores de computadores clássicos, lidar com essas
possibilidades e entender o funcionamento dos dados quânticos, é de grande importância ao
realizar no futuro o tratamento dos dados quânticos.
4.4 UM NOVO PARADIGMA A SER SEGUIDO
O surgimento da computação quântica provocou mudanças nos paradigmas da compu-
tação clássica, surgindo novos paradigmas que ocasionaram um futuro promissor na área da
13
inteligência artificial. Provocaram mudanças na programação de computadores clássicos, mu-
dando o conceito clássico, em que o processamento de dados é realizado um por vez.
Muito cuidado deve ser tomado ao programador, com o tratamento dos dados.
Aproveitar o máximo da superposição e do emaranhamento quântico é fundamental para
tornar a computação quântica o melhor modelo computacional existente. “Com o computador
quântico, um programador também não precisa compreender os fenōmenos da física quântica
para poder utilizer todo o seu poder, mas precisa compreender a lógica desse novo paradigma
da computação.” (JOSÉ; PIQUEIRA; LOPES, 2013, pg. 01).
5 ALGORITMOS QUÂNTICOS
Os principais algoritmos quânticos, mostram o quanto a computação quântica é efici-
ente, resolvendo problemas que exigem muito tempo para ser concluído na computação con-
vencional. “Os dois algoritmos quânticos mais famosos são: algoritmo para fatoração de Shor
[Shor 1994] e o algoritmo para busca de Grover [Grover 1997].” (KOWADA et al, nd, pg.
01).
Todos os “algoritmos quânticos estão baseados no modelo computacional que utiliza a
estrutura quântica da matéria no processo de computação.” (GRILO, nd, pg. 08). Todos os
princípios da computação quântica são levados em conta no desenvolvimento de algoritmos
quânticos, e sua eficiência consiste no bom aproveitamento destes princípios.
Para evitar erros de medição, uma solução básica, à primeira vista, seria preparar o mesmo estado várias vezes e medir várias vezes a saída, até que a probabilidade de erro seja suficientemente baixa para que o dado seja considerado seguro. Porém, este excesso de medidas diminuiria o desempenho, fazendo com que os desempenhos dos algoritmos quânticos talvez se igualassem, ou mesmo fossem inferiores ao dos algoritmos clássicos. (LAGO, nd, pg. 868).
“Um conceito importante para o desenvolvimento de algoritmos quânticos é o para-
lelismo quântico.” (GRILO, nd, pg. 08). Em que são realizadas operações simultâneas com
diversos dados em superposição.
5.1 PARALELISMO QUÂNTICO
A computação convencional que temos hoje utiliza o recurso de simular paralelismo,
no processamento de dados ao mesmo tempo em mais de um processador ou com uso de mais
14
de um núcleo de processamento. Não sendo realmente um processamento paralelo, mas se
tratando em paralelismo quântico, realmente os dados são processados simultaneamente.
O paralelismo é uma consequência direta da superposição quântica. Como o sistema evolui através de operações unitárias (vide Postulado 2), todas as componentes superpostas do estado em questão são modificadas ao mesmo tempo, como se fossem argumentos individuais para a função computada pela operação. (OLIVEIRA, 2007, pg. 10 a 11).
5.2 COMPLEXIDADES DE ALGORITMOS QUÂNTICOS
O tempo consumido por uma MTQ com entrada x é o número de passos que a m áquina efetua até terminar a execução. Essa definição ́e consistente, porque exigimos que, quando uma configuração da superposição atinge um estado final, todas as de-mais configurações também o fazem. (CARDONHA; SILVA, 2004, pg. 80).
As classes Bounded Error Quantum Polynomial Time (BQP), Exact Quantum
Polynomial Time (EQP) e Zero Error Quantum Polynomial Time (ZQP) foram as responsá-
veis por fundamentar a base da complexidade quântica, “Denomina-se BQP a classe dos pro-
blemas que são resolvíveis de maneira eficiente no modelo computacional quântico.” (GRI-
LO, nd, pg. 11).
Uma destas classes é análoga ao BPP e é conhecida como BPQ (Bounded-error quantum polynomial time). Ela contém problemas que podem ser resolvidos de for-ma eficiente por máquinas quânticas com uma pequena probabilidade de erro. E é devido à solução de problemas desta classe o motivo de grande parte do interesse em computação quântica. (PINTO; RIBEIRO; MORETTI, nd, pg. 05).
5.3 ALGORITMO DE GROVER
O algoritmo de Grover é um dos principais algoritmos quânticos, “[...] foi projetado
para encontrar um elemento dentro de uma lista não-ordenada.” (KOWADA et al, nd, pg. 03),
sua eficiência demonstra o quanto a computação quântica é superior a computação convenci-
onal.
O algoritmo de Grover foi desenvolvido inicialmente para a busca em uma lista não-ordenada [Grover 1997], mas segundo a opinião de diversos autores, o seu uso mais eficiente não será desta forma, mesmo porque o hardware para isso necessita de (N) chaves quânticas. Segundo Nielsen e Chuang (apud KOWADA et al, nd, pg. 01 a 02).
Áreas importantes como a criptoanálise, o uso de algoritmos de busca, é muito impor-
tante. “Outro campo de aplicação para problemas de busca é a criptografia, mais precisamente
a criptoanálise.” (KOWADA et al, nd, pg. 02).
15
No desenvolvimento de algoritmos quânticos, é fundamental conhecer os principais
algoritmos quânticos, que formam a base destes. “[..] o Algoritmo Quântico de Busca de Gro-
ver têm sido as bases para o desenvolvimento dos algoritmos quânticos evidenciando as po-
tencialidades de uma máquina quântica.” (OLIVEIRA, 2007, pg. 12). Igual o modelo conven-
cional, os computadores quânticos não serão eficientes, com o uso de algoritmos ineficientes,
que não usufruem dos princípios importantes da mecânica quântica.
Os melhores métodos de busca convencionais em grandes bases de dados desordena-
das, não possuem a mesma eficiência que o algoritmo de busca de Grover. “O melhor algo-
ritmo clássico resolve a busca de um elemento em uma estrutura desordenada em tempo O(N)
(onde N é a quantidade de elementos do conjunto de entrada), enquanto a solução apresentada
por Grover encontra o elemento em tempo O(√N).” (OLIVEIRA, 2007, pg. 13).
O Algoritmo de Grover está dividido em três etapas. A primeira delas, bastante co-mum na Computação Quântica, é a preparação dos qubits utilizados colocando-os em superposição. A segunda etapa deve marcar o elemento buscado através de uma operação unitária denominada oráculo. Por fim, na terceira etapa, é aplicada uma operação conhecida como amplificação de amplitude, que deve aumentar a probabi-lidade de leitura do elemento anteriormente marcado. (OLIVEIRA, 2007, pg. 14).
Figura 8 Estrutura de um circuito que executa uma iteração do algoritmo de Grover.
Fonte: A Utilização do Algoritmo Quântico de Busca em Problemas da Teoria da Informação.
5.3.1 Primeira Etapa
O processo de execução do algoritmo de Grover, ao passar pela primeira etapa das
três, prepara os qubits, “[..] utilizando portas Hadamard. Esta porta coloca os qubit em super-
posição, com uma amplitude de probabilidade igualmente distribuída para cada estado da base
do espaço [..].” (OLIVEIRA, 2007, pg. 14).
16
5.3.2 Segunda Etapa
Ao terminar a primeira etapa de por todos os qubits em superposição, a segunda etapa,
consiste na marcação do objeto pesquisado, “[...] refere-se à aplicação do oráculo (porta
Orac). Este é um operador unitário que utiliza qubits auxiliares para marcar o elemento procu-
rado.” (OLIVEIRA, 2007, pg. 15).
5.3.3 Terceira Etapa
“A operação unitária Ampl = (2 | Ψ› ‹Ψ| − I) foi introduzida por Grover em [Gro96], e
sua aplicação em um estado com elementos previamente marcados, acarreta na amplificação
da amplitude [BHMT00] de tais elementos.” (OLIVEIRA, 2007, pg. 17).
O Algoritmo de Grover resolve o problema de buscas em um banco de dados desordenado, apresentando um ganho quadrático em relação aos algoritmos clássicos. O ganho não é exponencial, como no caso dos algoritmos de Shor, porém é possível aplicar seu resultado em muitos problemas importantes, inclusive a todos os problemas da classe NP. (GRILO, nd, pg. 09).
O algoritmo de Grover, pode ser visto e testado no simulador em nuvem Quantum
Playground da empresa Google, que emula um dispositivo que armazena até 22 qubits, escrito
em linguagem de programação clássica. Além do algoritmo de Grover e outros exemplos, é
possível escrever próprias linhas de códigos e simular seu funcionamento em computadores
quânticos.
Figura 9 Algoritmo de Grover no simulador quântico em nuvem da empresa Google.
Fonte: http://www.quantumplayground.net/#/playground/5185026253651968
17
CONCLUSÃO
A mecânica quântica foi uma das principais descobertas no mundo da física, com prin-
cípios bastantes eficientes para outras áreas como a computação. A computação quântica é o
novo modelo computacional com paradigmas diferentes dos convencionais, que originou-se
destes princípios, melhorando a eficiência e resolvendo problemas que eram vistos como sem
solução no modelo clássico existente. Ao longo do trabalho foram vistos os princípios da me-
cânica quântica utilizados na computação quântica, por meio de levantamentos bibliográficos
e revisão de literatura, de livros e artigos científicos sobre mecânica quântica, computação
quântica e algoritmos quânticos, mostrando o interesse em solucionar problemas complexos
por meio de algoritmos quânticos como o de Grover, visando a importância deste novo mode-
lo computacional, aos problemas existente dos modelos atuais.
ABSTRACT
Quantum computing is a new computational model that uses all the principles of quantum mechanics, only with different paradigms of conventional computing his performance in solv-ing problems of the classical complexity classes is quite greater than that of any other conven-tional computer. Being able to read more than one or all the input data at the same time, through quantum superposition in bit4. Another principle that makes quantum computation exceeding current is the quantum entanglement, allowing meet distinct and separate data without any connection, through a single elétron5, which in a way is connected to the other. Many quantum algorithms have been developed, and re-solvem very complicated problems, such as Shor's algorithm, that factor numbers bas-tante complexes, and Grover, which fetches data in databases of large proportion of jumbled data. These were the first algorithms devel-oped with all Sling-ments of quantum computation. The efficiency of quantum computers is one of the main reasons to invest in studies and development of computers that can perform all the tasks performed by conventional computers, and problems of the classes of data com-plexity. The survey shows the main features and complies with-pios of quantum mechanics used in quantum computation, extolling the efficiency of something-quantum rhythms with emphasis on Grover algorithm. With overall objective to explore the principles of quantum mechanics, in specific detail the efficiency of these principles in with-quantum putação. Bib-liographic surveys are performed and review of the literature, of books and scientific articles on quantum mechanics, quantum computation and quantum algorithms. KEYWORDS: Quantum mechanics. Quantum computation. Quantum algorithms. Comple-xit. REFERÊNCIAS
18
AMOREIRA, Luís J.M. Alguns algoritmos para computação quântica. Nd. UBI-DF, nd. BARCELOS, Célia A. Zorzo; ANDRADE, Eliana X.L; BOAVENTURA, Maurílio. Notas em Matemática Aplicada: Algoritmos Quânticos de Busca. São Calos, SP: SBMAC, 2010, v. 47. CARDONHA, Carlos H; SILVA, Marcel K. de Carli. Computação Quântica: Complexidade e Algoritmos. 2004. Trabalho Acadêmico (Iniciação Científica) Departamento de Ciência da Computação, Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, 2004. CARDOSO, Marcos B; REISER, Renata H.S; COSTA, Antônio C.R. Desenvolvendo Algo-ritmos Quânticos Utilizando uma Linguagem Funcional. Nd. Trabalho Acadêmico. Escola de Informática, Universidade Católica de Pelotas, Pelotas, nd. DAVIDOVICH, Luiz. Informação Quântica: do Tele transporte ao Computador. Ciência Ho-je, p. 24-29, Julho. 2009. GLASSNER, Andrew. Andrew Glassner’s Notebook. IEEE Computer Graphics and Ap-plications, p. 84-91, Agosto. 2001. GRILO, Alex Bredariol. Projeto de Pesquisa Computação Quântica e Teoria da Compu-tação. Nd. Trabalho Acadêmico. Instituto de Computação, Universidade de Campinas, Cam-pinas, nd. HUGHES, Richard J; WILLIAMS, Colin P. Quantum computing: The final frontier? IEEE Intelligent Systems, p. 10-18, Setembro/Outubro. 2000. JOSÉ, Marcelo Archanjo; PIQUEIRA, José Roberto Castilho; LOPES, Roseli de Deus. In-trodução à programação quântica. 2013. Trabalho Acadêmico. Escola Politécnica, Univer-sidade de São Paulo, São Paulo, 2013. KOWADA, Luis Antonio et al. Aplicação do Algoritmo de Grover para Problemas NP-Completos. Nd. Trabalho Acadêmico. Universidade Federal Fluminense et al, Niterói, nd. LAGO, Rafael Ferreira et al. Simulação do Algoritmo de Grover. Nd. Trabalho Acadêmico. PESC, Universidade Federal do Rio de Janeiro. Rio de Janeiro, nd. MECÂNICA. Mecânica Quântica. Nd. Obra Coletiva, nd.
19
OLIVEIRA, Nigini Abilio. A Utilização do Algoritmo Quântico de Busca em Problemas da Teoria da Informação. 2007. Trabalho Acadêmico. Centro de Engenharia Elétrica e In-formática, Universidade Federal de Campina Grande, Campina Grande, 2007. PESSOA, Osvaldo. A Física Quântica seria necessária para explicar a Consciência? 1994. Trabalho Acadêmico. Universidade de São Paulo, São Paulo. 1994. PINTO, Victor Valdevite; RIBEIRO, Pedro Pereira; MORETTI, Alessandro. Computação Quântica. Nd. Trabalho Acadêmico. Instituto de Computação, Universidade Estadual de Campinas, Campinas nd. ROSA, Pedro Sérgio. O Início da Mecânica Quântica: A necessidade de um novo modelo. Nd. Curso de Eletrônica, Tatuí, São Paulo, nd.
