71 Interciência & Sociedade BUSCA QUÂNTICA EM BANCOS DE DADOS XML USANDO ALGO- RITMO DE GROVER RESUMO: Este artigo apresenta a implementação de um algoritmo de busca quântica com peque- nas modificações. A idéia desse algoritmo é ser hibrido, podendo funcionar em sistemas clássicos e sistemas quânticos. São apresentados os conceitos quânticos das buscas e introduzido um pseudo- -framework capaz de gerar códigos para computadores clássicos (C++) e computadores quânticos (QCL). Os algoritmos foram submetidos a simulações, que resultaram em um estudo comparativo do funcionamento do algoritmo de Grover em ambos os sistemas, realizando buscas em uma massa de dados em arquivos no formato XML. Como resultado, observa-se números muito parecidos entre sis- temas clássicos e quânticos, isso gera uma expectativa de que a busca em computadores quânticos reais seja muito mais eficiente. PALAVRAS-CHAVE: busca quântica, grover, QCL, emaranhamento, sobreposição. PONTES, Michael Alexandre Universidade Estadual Paulista (UNESP) michaelpontes@terra.com.br BORGES, Manoel Ferreira Neto Universidade Estadual Paulista (UNESP) borges@ibilce.unesp.br ABSTRACT: This paper presents a quantum search algorithm implementation with small modifications. The algorithm idea is to be hybrid, capable to run on classical systems and quantum systems. We present the concepts of quantum search and introduced a pseudo-framework able to generate code for classical computers (C++) and quantum computers (QCL). The algorithms were submitted to simu- lations, which resulted in a comparative study of the operation of Grover’s algorithm on both systems, carrying out searches in a mass of data in XML format files. As a result, we see very similar numbers between classical and quantum systems, this creates an expectation that the search in real quantum computers is much more efficient. KEYWORDS: quantum search, grover, qcl, entanglement, superposition. INTRODUÇÃO Como todas as simples ideias na ciência, levou tempo para que se notasse a conexão entre os conceitos de computação e as características de sistemas físicos mi- croscópicos, propriedades como emaranha- mento e superposição coerentes de estados distintos estão presentes nos fundamentos da mecânica quântica e sempre foram con- siderados aspectos mais estranhos desta teoria (NIELSEN; CHUANG, 2005). O re- conhecimento de que a informação, muito mais que um conceito matemático abstrato, é uma propriedade de sistemas físicos, le- vou a enormes avanços na interpretação da Mecânica Quântica. Com a utilização da Computação Quântica, tempos impraticáveis necessários para executar certas tarefas na computação clássica, passam a ser tempos normais em computadores quânticos. Como afirma HA- WKING, 2009, problemas praticamente in- solúveis para computação clássica passam a ser solúveis em computação quântica. Computadores quânticos oferecem computação mais poderosa (SIMON, 1994) do que os computadores clássicos, devido à capacidade dos computadores quânti- cos de terem alguns estados que não têm equivalência em um computador clássico. Características como a superposição de valores e/ou o emaranhamento de estados são aspectos que representam o “coração” do funcionamento de um sistema quântico. Isso tudo somado ao paralelismo quântico, Interciência & Sociedade72 PONTES, M. A.; BORGES NETO, M. F. representa um diferencial considerável fren- te à computação que estamos habituados. Visando contribuir com a área pou- co explorada da Computação Quântica, este artigo propõe a implementação de um sistema híbrido de busca em bancos de da- dos não estruturados. Tal sistema visa rea- lizar buscas clássicas e buscas quânticas, ambas baseadas no mesmo algoritmo de busca, o Algoritmo de Grover. Este algorit- mo é conhecido na área quântica, porém sua implementação de forma híbrida é um desafio novo. A proposta de um mesmo en- gine capaz de realizar buscas em sistemas quânticos e clássicos é o que justifica e de- fine a originalidade deste trabalho. As buscas realizadas pelo algo- ritmo proposto poderão ser aplicadas em sistemas de computação clássica, com- putação quântica ou computação hibrida (SCHUBOTZ, 2007; ÖMER, 2000). Neste artigo, o algoritmo proposto utiliza um simu- lador quântico para testar os algoritmos em sistemas quânticos, e realiza as buscas em bancos de dados baseados em estruturas XML (eXtensible Markup Language). 1. COMPUTAÇÃO QUÂNTICA Na computação clássica, a memó- ria do computador é organizada em bits, onde cada bit representa um ou zero. Na computação quântica, por outro lado, exis- tem alguns fenômenos da mecânica quân- tica, como superposição e emaranhamento de estados, que são utilizados para execu- tar operações em dados (MUTIARA; RE- FIANTI, 1994). Computadores Quânticos foram propostos no início dos anos 1980 (BENIO- FF, 1980) e em muitos aspectos, mostraram- -se tão poderosos quanto os computadores clássicos. A descrição formal dos computa- dores quânticos só foi realizada no final dos anos 80 e início dos anos 90 (DEUTSCH, 1985; BERTHIAUME; BRASSARD, 1994; BERNSTEIN; VAZIRANI, 1993; YAO, 1993) e os computadores quânticos, em vários problemas específicos, se mostraram mais poderosos que os computadores clássicos. No início de 1994, (SHOR, 1994) demonstrou que um computador quânti- co poderia resolver de forma eficiente um problema bem conhecido, para o qual não havia algoritmo eficiente usando computa- dores clássicos. Este é o problema de fa- toração, isto é, encontrando os fatores de um determinado número inteiro , em um tempo que é polinomial em . A pesquisa na área de computação e informação quântica ganhou um imenso interesse com os resultados apresenta- dos para o problema de fatoração (SHOR, 1994). Na sequência, os algoritmos de bus- ca (GROVER, 1996) também passaram a chamar bastante atenção para sua eficiên- cia. Esses resultados comprovam o enor- me poder computacional de uma máquina quântica. No entanto, a construção de com- putadores quânticos representa um imenso desafio tecnológico e, neste momento, o hardware quântico só está disponível em la- boratórios de pesquisa. Diante desse cená- rio, os simuladores quânticos tornaram-se instrumentos valiosos no desenvolvimento e testes de algoritmos quânticos, bem como na simulação de modelos físicos (CARAI- MAN; MANTA, 2010). Um dos grandes atrativos na com- putação quântica é que no lugar de usar bits, são usados qubits (bits quânticos). Um único qubit pode representar um, zero, ou ambos ao mesmo tempo, o que é chamado de superposição. Com essa capacidade, a computação quântica pode realizar várias tarefas simultaneamente de forma mais rá- pida do que a computação clássica. Há também outro fenômeno em computação quântica, que é chamado ema- ranhamento. Se dois qubits receberem uma força externa, então os qubits podem estar na condição de emaranhados. Isso significa que, mesmo à distância um do outro, qual- quer influência que um dos qubits receber, irá afetar o outro também (MUTIARA; RE- FIANTI, 1994). Sistemas de informação quântica, em geral, são baseados no uso de matemá- tica intensa. Porém, o grande truque desses sistemas é a utilização de um modelo sim- ples de construção por blocos de abstração: bits quânticos, portas e algoritmos (OSKIN; CHONG; CHUANG, 2002), o que facilita sua implementação. Nessa pequema introdução sobre computação quântica, é possível perceber 73 Interciência & Sociedade Busca quântica em bancos de dados xml usando algoritmo de Grover a riqueza desse novo sistema de compu- tação. A utilização de conceitos quânticos na computação ultrapassa fronteiras, ofe- recendo novas formas de processamento. Nas próximas sessões, será explorada al- gumas características dos sistemas quânti- cos, visando atingir o objetivo proposto por esse artigo. 2. Problema de busca Encontrar um dado em um ban- co de dados não-estruturado é conhecido como problema de pesquisa em banco de dados não-ordenados (UDS – unsorted database search), este problema é muito comum e difícil de ser solucionado. Muitos problemas científicos podem ser reduzidos a problemas de UDS e esta tem larga apli- cação em ciência e tecnologia (LONG; LIU, 2007; HU; ZHANG; LU, 2009). Mesmo em ciência da computa- ção teórica, são bastante comuns proble- mas em que seja necessário examinar uma série de possibilidades diferentes para ver se uma delas satisfaz dada condição. Esta situação é análoga ao problema de busca descrito acima, e o ponto de observação mais crítico em problemas de busca é sem- pre o desempenho e eficiência do algoritmo utilizado (GROVER, 1996). 2.1. Busca quântica Os algoritmos quânticos são pro- babilísticos, isso oferece um ótimo ponto de partida para se pensar em suas possíveis aplicações (BERNSTEIN; VAZIRANI, 1993). Nestes algoritmos, o sistema não está em um estado especificado, ao contrá- rio disso, está em uma distribuição de vá- rios estados com certa probabilidade de ser cada um deles. Em cada etapa, há uma pro- babilidade de acontecer uma transição de um estado para o outro. A evolução do sis- tema é obtida através da pré-multiplicação do vetor de probabilidades pelo estado de transição da matriz (GROVER, 1996). Suponha que se tenha um mapa contendo muitas cidades, e que se deseje encontrar o menor caminho entre elas. Um algoritmo simples para resolver esse pro- blema consiste em encontrar todas as rotas possíveis, mantendo gravada a de menor comprimento. Em um computador clássico, se existirem N rotas, serão obviamente ne- cessárias operações para se determi- nar o menor caminho (NIELSEN; CHUANG, 2005; LONG; LIU, 2007). O algoritmo quântico de Grover au- menta significativamente a velocidade des- sa busca, necessitando apenas de operações. Além disso, o algoritmo quânti- co de busca é geral, no sentido de que ele pode ser aplicado para acelerar diversos algoritmos clássicos que usam rotinas de busca (GROVER, 1996). Tais algoritmos representam pa- péis muito importantes nos campos da in- formação e computação. Tomando como exemplo a tarefa de encontrar o proprie- tário de um número telefônico decifrando um código como DES (BRASSARD, 1997), resolvendo o problema de Simon (BRAS- SARD; HOYER, 1997), solucionando o pro- blema de contagem quântica (BRASSARD; HOYER; TAPP, 1998). O espaço pode ser vasculhado de forma altamente eficiente por um robô quântico usando o algoritmo de busca (BENIOFF, 2000). Esses algoritmos também podem acelerar a resolução de problemas de raiz quadradas considerados difíceis, como o problema do deslocamen- to oculto (TWAMLEY, 2000), o problema do circuito hamiltoniano (DESURVIRE, 2009) e problemas NP-completos em geral (GUO; LONG; LI, 2002). O algoritmo de Grover, utilizando as propriedades quânticas da superposição e do emaranhamento, também pode ser usado para procurar um elemento em uma lista não estruturada de elementos qua- drática com velocidade superior aos algo- ritmos clássicos (BRICKMAN; et al, 2005). 3. Algoritmo de Grover Na seção anterior, superposição e emaranhamento de estados quânticos fo- ram apontados como os fatores essenciais para a obtenção do desempenho dos sis- temas quânticos. O algoritmo de busca de Grover (BUGAJSKI, 2001; GROVER, 1996; KLAMKA, 2002) faz uso desses fenôme- nos. A complexidade da pesquisa clássica de uma coleção não ordenada de itens é Interciência & Sociedade74 de . Usando o algoritmo quântico, po- demos reduzir esse fator para . O algoritmo utiliza um quregister único de qubits, onde . Para sim- plificar, assumimos que é uma potência de e . Como segue: 1. No primeiro passo, uma super- posição de todos estados é ge- rado. 2. Uma transformação é realizada para fazer com que a amplitude da probabilidade do estado se diferen- cie das outras (Oráculo Quântico). 3. Outra transformação (difusão) é realizada para ampliar a probabili- dade deste estado. 4. Os passos (2) e (3) são iterados quantas vezes forem necessárias. 5. O algoritmo termina quanto a probabilidade do estado desejado está próxima de 1. Na sequência, uma medição é realizada. A superposição é uma operação realizada através do operador quântico Ha- damard, que resulta no mesmo valor para todas as amplitudes possíveis. Na Figura 1a está situação está representada por um registro de 4-qubit, que contém 16 valores diferentes. A soma dos quadrados de todas as amplitudes é 1, o valor de cada amplitu- de é demonstrado na sequência em (1): O Oráculo Quântico é o segundo passo do algoritmo, esse é o ponto em que o item procurado é identificado. O Oráculo decide se o argumento é o item que está sendo procurado, e é simultaneamente cha- mado para cada item presente na lista de estados. A operação tem que ser reversí- vel, portanto nenhuma informação pode ser perdida. Isto é obtido através da negação da amplitude do item procurado (Figura 1b). Dado que é o estado que está sendo pes- quisado, temos em (2): A medida da amplitude é comple- xa, a operação de negação é descrita antes como a rotação do estado marcado por uma fase de π. De qualquer modo, esta opera- ção não irá afetar a possibilidade de detec- ção deste estado em uma medição feita nesse ponto. (1) (2) Figura 1: Etapas iniciais do Algoritmo de Grover. Fonte: Adaptado de: FRANCIK, 2002. O operador de difusão é o próximo passo do algoritmo, nessa etapa, é feita a operação de interferência. Esta operação é muitas vezes referenciada como inversão sobre a média, como é dado a seguir em (3): onde é a média de todas as amplitudes. Esta operação é aplicada sobre um vetor no qual todos os componentes, exceto um, são iguais a um valor, como α; o componente um, que é diferente, é negativo (Figura 1b). A média ā é aproximadamente igual a , então componentes não alteram de forma significativa o resultado da inversão sobre a média. O componente um, que es- tava negativo, torna-se positivo e aumenta cerca de (Figura 2c).(3) PONTES, M. A.; BORGES NETO, M. F. 75 Interciência & Sociedade Iteração: o ganho efetivo obtido por uma inversão única sobre a média não é o suficiente, especialmente se for notado que mais estados possuem ganhos menores. Após certo número de iterações, possivel- mente a amplitude se aproximará de 1. Porém a amplitude nunca será igual a 1, pelo fato do algoritmo de Grover ser probabilístico: o resultado mais adequa- do é obtido com uma alta probabilidade, mas não é garantido totalmente. Iterações consecutivas são mos- tradas da Figura 2c até Figura 2f. Na ter- ceira iteração (Figura 2e) a amplitude do estado desejado atingiu o máximo (para o caso de 16 estados); após isso, diminui (Figura 2f). O valor do componente , denotado , lentamente diminui uma vez que se aproxima de zero, e o ganho efetivo inverte. Na verdade, ambos os valores são quantificados em uma função periódica (a amplitude desejada cresce novamente de- pois das iterações 9, 15 e assim por diante). O problema é: quantas vezes de- vemos iterar para obter o resultado ideal? Vamos denotar , sendo o valor de todas as amplitudes acrescido de um, e β é a ampli- tude do estado iniciando a pesquisa em . Então, a média é dada por (4): Usando (3), (2) e (1), temos: onde e são os estados anteriores, e e são os próxmos estados de α e β. A solução (5) leva a uma equação quadrática com raízes complexas. A abor- dagem analítica pode ser complicada, mas observa-se que, depois de uma substituição , a equação (5) torna-se uma equação de rotação de um ponto ao redor do centro das coordenadas do siste- ma por um ângulo . O melhor resultado é alcançado quando o ângulo atinge π/2, então o número de iterações é apresentado em (6): Após a última iteração, a medição final é executada. 3.1. Grover sem emaranhamento quântico A propriedade de emaranhamen- to quântico é considerada necessária para que os algoritmos quânticos superem os Figura 2: Iterações do Algoritmo de Grover. Fonte: FRANCIK, 2002. (4) (5) (6) Busca quântica em bancos de dados xml usando algoritmo de Grover Interciência & Sociedade76 clássicos. Porém, diversos autores, dentre eles LLOYD (1999) e MEYER (2000) obser- varam em suas pesquisas que o algoritmo de busca quântico de Grover pode ser im- plementado sem o emaranhamento quânti- co. Isso só é possível com a realização de substituições de partículas múltiplas (carac- terísticas quânticas) por uma partícula úni- ca, porém com muitos estados exponencial- mente associados a ela. Segundo LLOYD (1999), qualquer algoritmo quântico pode ser reescrito sem o uso de emaranhamento. Para tal, basta simplesmente desconsidedar a estrutura do produto tensorial do espaço de Hilbert. Fa- zendo isso, naturalmente, haverá um custo extra de utilização do sistema, já que a com- putação quântica estará sendo subjulgada. Não se deve concluir que o ema- ranhamento é desnecessário. Para algorit- mos iterativos, pode haver redução do nú- mero de consultas necessárias, reduzindo o caminho até a solução. Já nos algoritmos de contagens (funções locais), há perda de desempenho e aumento no uso dos re- cursos para sua execução. Simon (1994) demonstrou em seu algoritmo que a imple- mentação da fatoração de Shor (1994) sem o emaranhamento não apresentavam resul- tados satisfatórios. Concluímos que alguns algorit- mos quânticos podem ter seus equivalen- tes clássicos, abrindo mão de propriedades quânticas, em especial, o emaranhamento. Por outro lado, nem todos os algoritmos respondem bem a esse tipo de adaptação. Para o contexto desse artigo, as pesquisas de LLOYD (1999) e MEYER (2000) mos- tram que o algoritmo de busca quântico de Grover não sofre perdas ao retirar a proprie- dade de emaranhamento quântico, sendo assim, será conceitualizado o algoritmo de Grover em sistemas clássicos, visto que o objetivo do artigo é a criação de um sistema híbrido de buscas. 3.2. Implementação híbrida do algoritmo de Grover Conforme a sessão 3.1, o algoritmo de Grover pode ser implementado sem utili- zar algumas propriedades que são exclusi- vamente quânticas. Diante disso, é possível a criação de um modelo de algoritmo que seja híbrido, e possa ser executado tanto em sistemas clássicos quanto em sistemas quânticos. YAMASHITA (2006) propõe em seu trabalho, a criação de um framework com o objetivo de permitir que algoritmos sejam ajustados de forma automática, dependen- do do modelo clássico ou modelo quântico. Com relação ao algoritmo de Gro- ver (1996), que pode ser considerado de uso geral, a adaptação de seu funcionamento em diversos modelos computacionais ofe- rece notável flexibilidade em sua utilização. Para a modelagem híbrida propos- ta por esse artigo, os conceitos propostos por YAMASHITA (2006) foram utilizados, onde o algoritmo de Grover foi implementa- do usando uma linguagem Clássica (C++) e uma linguagem Quântica (QCL). O framework capaz de compatibi- lizar essa dupla implementação, funciona analisando o código e gerando novos códi- gos baseados nas plataformas específicas. Neste artigo, utilizamos o modelo, concei- tos e implementamos uma versão própria do framework proposto por YAMASHITA (2006), mais simples com o objetivo apenas de gerar a versão híbrida do algoritmo de Grover. Na Figura 3, podemos observar o fluxo da informação dentro do pseudo-fra- mework criado para esse artigo. O código desenvolvido é aplicado no framework, que faz uma pré-análise e gera os circuitos e códigos baseados no tipo de sistema a ser aplicado. PONTES, M. A.; BORGES NETO, M. F. 77 Interciência & Sociedade No Quadro 1, podemos observar um trecho do código fonte do algoritmo de Grover em linguagem C++. Para fins de comparação, apenas a função Grover() está sendo apresentada. Figura 2: Framework para geração de código híbrido. Fonte: YAMASHITA, 2006. Por outro lado, no Quadro 2, nota- mos um trecho do código fonte do algorit- mo de Grover em linguagem QCL. Para fins de comparação, apenas a função Grover() está sendo apresentada. Quadro 1. Função Grover em C++. Quadro 2. Função Grover em QCL. Busca quântica em bancos de dados xml usando algoritmo de Grover Interciência & Sociedade78 4. Simulações Com o objetivo de validar os con- ceitos apresentados nesse artigo, um am- biente de simulação foi estruturado com o desafio de realizar testes de carga nos al- goritmos construídos. Para realização dos testes, foi ge- rado um banco de dados em XML com uma massa de dados não-estruturada de cerca de 5.000 registros. O objetivo foi realizar buscas com os algoritmos de Grover nessa massa de dados, e analisar três fatores im- portantes: (i) Compatibilidade dos algoritmos, ou seja, se o algoritmo clássico e o quânti- co executam de formas semelhantes, sem a necessidade de realizar ajustes nos dados ou nos códigos fontes. Esse item avalia a portabilidade de códigos diferentes aces- sando o mesmo banco de dados. (ii) Desempenho da execução, um comparativo simples de tempos decorridos, para gerar informações sobre os tempos gastos por cada um dos algoritmos, consi- derando as mesmas condições. (iii) Número de iterações, como o algoritmo de Grover é iterativo, quanto me- nor o número de iterações, com a mesma eficiência, melhor os resultados da execu- ção dos algoritmos. 4.1. Simuladores Para realizar as simulações, foram utilizadas duas ferramentas. Para o dese- nho e avaliação do Circuito Quântico, foi utilizada a ferramenta Wolfram Demonstra- tions (http://demonstrations.wolfram.com/). Essa ferramenta permitiu a construção de um código dinâmico para gerar o circuito quântico que foi implementado no simula- dor quântico para execução das buscas. Já para execução do código quân- tico, foi utilizada a biblioteca libquantum (http://www.enyo.de/libquantum/). Tal biblio- teca foi apresentada no trabalho de SCHU- BOTZ (2007), onde o autor realiza um estu- do comparativo entre três simuladores, e a libquantum mostra-se melhor em todos os critérios. A libquantum é uma biblioteca em C específica para computação quântica. Ela usa o modelo QRAM, e fornece regis- tradores quânticos, operações unitárias e funções de medição. A biblioteca vem com uma interface para codificar registros quân- ticos, controle de correção de erro quântico (QEC) e oferece flexibilidade no uso. Seu principal objetivo é uma precisa simulação física de um computador quântico com alto desempenho (SCHUBOTZ, 2007). Apesar da biblioteca já incluir a im- plementação do algoritmo de Grover, para as simulações, utilizamos os algoritmos e circuitos gerados no decorrer da pesquisa. 4.2. Resultados Os testes em sistemas clássicos foram realizados em ambiente de compu- tação clássica tradicional, onde o arquivo XML com os dados estava armazenado em disco e as rotinas em C++ foram executa- das e os indicadores analisados. Já os testes em sistemas quânti- cos, foram realizados no simulador libquan- tum apresentado na sessão 4.1. O arquivo XML foi armazenado dentro da estrutura do simulador e os testes foram realizados e os devidos indicadores foram analisados. Na Figura 4, observa-se o circuito quântico construído dentro da ferramenta li- bquantum, notem que o circuito sugere pelo menos 4 iterações, porém devido ao tama- nho da massa de dados, a execução do cir- cuito completo é interativa até que a massa de dados seja completamente analisada. 00001 b1b2b3b4b5 H H H H H X X X X X X X X H H H H X X X X Z X X X X H H H H X X X X X X X X H H H H X X X X Z X X X X H H H H Figura 4: Cirtuito Quântico iterativo aplicado na libquantum (gerado na ferramenta Wolfram). PONTES, M. A.; BORGES NETO, M. F. 79 Interciência & Sociedade Na Tabela 1, temos os resultados das análises de cada um dos algoritmos, executados e analisados nos sistemas pro- postos, baseado em uma massa de dados com 5.000 registros em formato XML. Podemos notar que o sistema Quântico, apesar de rodar sobre um simula- dor, apresentou uma quantidade menor de iterações até convergir para o melhor resul- tado. Apresentam-se as três iterações do sistema Quântico no momento em que a convergência ocorreu, e sua precisão che- gou aos 100% com 55 iterações, mesma precisão atingida pelo sistema Clássico em 72 iterações. Essa diferença de precisão e número de iterações é esperada, já que o sistema Clássico é determinístico e o siste- ma Quântico é probabilístico. Grover Clássico Quântico Quântico Quântico Iterações 72 54 55 56 Tempo decorrido 23s 30s 32s 34s Precisão 100% 99,8% 100% 99,8% Compatibilidade Total Total Total Total Tabela 1. Grover Clássico X Grover Quântico. Em termos de tempo decorrido, no- tamos uma diferença considerável onde o Grover clássico (23s) é cerca de 39% mais rápido que o Grover quântico (32s), porém isso se justifica pois o sistema quântico está rodando sobre um simulador, e a documen- tação da libquantum afirma perdas de até 45% pelo fato de ser um ambiente simula- do. Além disso, não existem sistemas quân- ticos consistentes disponíveis para conse- guirmos uma simulação com valores reais. Observamos também, que os có- digos são perfeitamente portáveis, ou seja, ambos os códigos funcionaram na mesma massa de dados, sem quaisquer modifica- ções ou necessidades de ajustes em ne- nhuma das partes. CONSIDERAÇÕES FINAIS A busca em bancos de dados não- estruturados é muito importante para ciên- cia e tecnologia. Ela serve como compara- tivo de algoritmos para demonstrar o poder de computadores quânticos. Curiosamente, um algoritmo totalmente quântico é relativa- mente simples de ser implementado, o que traz vantagens para essa área. Neste artigo, foram apresentados de forma breve alguns conceitos quânti- cos básicos. Também foi apresentado com mais detalhes a busca quântica, com espe- cial atenção para o algoritmo de busca de Grover, e demonstra seu funcionamento em sistemas clássicos e quânticos. Seguindo as implementações so- bre o algoritmo de Grover, o artigo apresen- ta um pseudo-framework capaz de tornar híbrido o algoritmo de busca, permitindo uma flexibilidade em seu uso. Após a criação dos algoritmos, si- mulações foram feitas, com o objetivo de comparar o funcionamento do algoritmo de Grover em sistemas clássicos (normais) e em sistemas quânticos (simulados). Os resultados foram apresentados na sessão 4.2, onde podemos observar poucas varia- ções entre os modelos. O objetivo de implementar um sis- tema hibrido de busca, foi cumprido. Os al- goritmos gerados conseguiram realizar bus- cas com eficiência em bases em formato XML, tanto para sistemas clássicos quanto para quânticos (simulados). O aspecto mais importante implíci- to nesse trabalho é que, gerenciar um ban- co de dados não-estruturado em um com- putador quântico é possível e eficiente. TRABALHOS FUTUROS Os resultados obtidos com essa pesquisa serão diretamente aplicados no projeto de mestrado do autor deste artigo, cujo tema é Busca Quântica em Bancos de Dados Relacionais. Este artigo apresenta os resultados da primeira fase, que se tra- ta de buscas em arquivos XML, a próxima Busca quântica em bancos de dados xml usando algoritmo de Grover Interciência & Sociedade80 fase envolverá a integração com bancos de dados relacionais e acesso aos dados em baixo nível. REFERÊNCIAS BIBLIOGRÁFICAS BENIOFF, P. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics, 22, 1980, pp. 563- 591. BENIOFF, P. Spaces searches with a quantum robot. In Quantum computation and information. Washington DC: AMS Series on Contemporary Ma- thematics, 2000, 305: 1-12. Disponível em: quant- -ph/0003006. BERNSTEIN, E.; VAZIRANI, U. Quantum Complexi- ty Theory. In Proceedings 25th ACM Symposium on Theory of Computing, 1993, pp. 11-20. BERTHIAUME, A.; BRASSARD, G. Oracle quantum computing. Journal of Modern Optics, vol.41, n. 12. December, 1994, pp. 2521-2535. BRASSARD, G. Searching a quantum phone book. Science, 1997, 275(5300): 627-628. BRASSARD, G.; HOYER, P. An exact quantum polynomial-time algorithm for Simon´s problem. In: Proceedings of 35th Annual Symposium on the Foundations of Computer Science. 1997, 116-123. BRASSARD, G.; HOYER, P.; TAPP, A. Quantum counting. Lectures Notes in Computer Science, 1998, 1443: 820-831. BRICKMAN, K. A.; HALJAN , P. C.; LEE, P. J.; AC- TON, M.; DESLAURIERS, L.; MONROE, C. Imple- mentation of Grover’s quantum search algorithm in a scalable system. FOCUS Center and Depart- ment of Physics, University of Michigan. In Proceedin- gs of The American Physical Society, Physical Review A 72, 050306-1(4). Michigan, USA:2005. BUGAJSKI, S. Quantum Search. Archiwum Informa- tyki Teoretycznej i Stosowanej, vol 13 No 2/2001, pp. 143-150. CARAIMAN, S.; MANTA, V. Parallel Simulation of Quantum Search. “Gheorghe Asachi” Technical Uni- versity of Iasi. In Proceedings Journal of Computers, Communications & Control, V(5), pp.634-641. Roma- nia, 2010. DESURVIRE, E. Classical and Quantum Informa- tion. eBook (EBL), New York, Cambridge University Press, 2009. DEUTSCH, D. Quantum Theory, the Church-Turing principle and the universal quantum computer. In Proceedings Royal Society London Series A, 400, 1985, pp. 96-117. FRANCIK, J. Quantum Software. Studia Informatica. Vol 23, n. 2A (48). Redakcji, 2002. GROVER, L. K. A fast quantum mechanical algo- rithm for database search. In Proceedings of 28th ACM Annual STOC, pp. 212-219. ACM Press New York. Philadelphia-PA/USA:1996. GUO, H.; LONG, G.L.; LI, F. Quantum algorithms for some well-known NP problems. Communications in Theoretical Physics, 2002, 37(4): 424-426. HAWKING, S. O Universo numa Casca de Noz. Rio de Janeiro: Nova Fronteira, 2009, 216p. HU, H.; ZHANG, Y.; LU, Z. An efficient quantum se- arch engine on unsorted database. Huazhong Uni- versity of Science and Technology, 2009. Disponível em: cs.DB/0904.3060v1. KLAMKA, J. Quantum search algorithm. Semina- rium Sieci Komputerowe, Zakopane, 2002. LLOYD, S. Quantum search without entanglement. Physical Reviews A61 (1999) 010301. LONG, G.L.; LIU, Y. Search an unsorted database with quantum mechanics. Frontiers of Computer Science in China, 2007, 1(3): 247-271. MEYER, D. A. Sophisticated Quantum Search Wi- thout Entanglement. Project in Geometry and Phy- sics. Department of Mathematics. Institute for Phy- sical Sciences. University of California/San Diego. Disponível em quant-ph/0007070. 2000. MUTIARA, A. B.; REFIANTI, R. Simulation of Grover’s Algorithm Quantum Search in a Classi- cal Computer. In Proceedings of the International Journal of Computer Science and Information Secu- rity. Indonesia, 8(9)261–269,1994. NIELSEN, M. A.; CHUANG, I. L. Computação Quân- tica e Informação Quântica. Rio de Janeiro, Brasil, Bookman/Artmed, 2005. ÖMER, B. Quantum Programming in QCL. Institute of Information Systems. Technical University of Vien- na, pp 42-45. Vienna, 2000. OSKIN, M.; CHONG, F. T.; CHUANG, I. L. A Prati- cal Architecture for Reliable Quantum Computers. Universidade de Toronto. IEEE Computer Society. 2002. SCHUBOTZ, R. Programming and Simulation of Quantum Agents. Department of Computer Science. Faculty of Natural Sciences and Technology I. Saar- land University, pp. 31-36. Saarbrücken, 2007. SHOR, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium of Fundamentals of Computer PONTES, M. A.; BORGES NETO, M. F. 81 Interciência & Sociedade Science (FOCS). S. Goldwasser, Santa Fe, NM. pp. 124-134. IEEE Computer Society, Los Alamitos. 20- 22 Novembro 1994. SIMON, D. R. On the power of quantum computa- tion. In Proceedings of the 35th Annual Symposium of Foundations of Computer Science. S. Goldwasser, Santa Fe, NM. pp. 116-123. 20-22 Novembro 1994. TWAMLEY, J. J. A hidden shift quantum algorithm. Journal on Physics A, 2000, 33: 8973-8979. YAMASHITA, S. How to Utilize a Grove Search in General Programming. Scholl of Information Scien- ce, Nara Institute of Science and Technology. In Pro- ceedings Laser Physics, vol 16, n. 4, pp 730-734. Iko- ma, Nara, Japan, 2006. YAO, A. Quantum circuit complexity. In Proceedin- gs 34th Annual Symposium of Foundations of Compu- ter Science (FOCS), 1993, pp. 352-361. Michael Alexandre Pontes é bacharel em Ciência da Computação pela UNiRP, Pós-graduado em Desenvolvi- mento Cliente/Servidor e Internet pela UNiRP, Pós-graduado em Engenharia de Sistemas pela Faculdade Modelo. Detentor de diversas certificações importantes, como Microsoft, Oracle, Progress, Novell, Citrix. Atualmente é pro- fessor nas seguintes instituições: Universidade Paulista, FATEC Rio Preto e Kees Informática. Também é líder de unidade de negócio da empresa Dual Software Ltda. Tem experiência com Governança de TI e Administração de Banco de Dados. Atua diretamente na área de Sistemas de Informação com ênfase em Engenharia de Sistemas. Possui vários projetos de pesquisa e desenvolvimento, tendo sido reconhecido e premiado em vários deles. Manoel Ferreira Borges Neto é graduado em Física pela Universidade de Brasília (UnB), Doutorado em Mate- mática pelo “Kings College - University of London” e Pós-doutorado pelo “Department of Mathematics and Applied Mathematics - University of Cape Town (UCT)”. Professor titular da Universidade Estadual Paulista (UNESP). Membro da “International Association of Mathematical Physics (IAMP)”. Membro e revisor da “American Mathe- matical Society (AMS)”. Membro da “European Society of Computational Methods in Sciences and Engineering (ESCMSE)”. Co-fundador e membro permanente do “World Peace and Diplomacy Forum (WPDF)”, Cambridge. Vasta experiência na área de matemática e matemática aplicada atuando principalmente nos temas: i) Geometrias Hipercomplexas; ii) Aspectos geométricos da Física-Matemática, notadamente das Teorias Alternativas da Gravi- tação, e suas relações com Variedades Topológicas; iii) Criptografia e Computação Quântica. Busca quântica em bancos de dados xml usando algoritmo de Grover