Algoritmos Quânticos de Busca

Michael Alexandre Pontes, Manoel Ferreira Borges

Este artigo apresenta a implementacao de um algoritmo de busca quântica com pequenas modificacoes. A ideia desse algoritmo e ser hibrido, podendo funcionar em sistemas classicos e sistemas quânticos. Sao apresentados os conceitos quânticos das buscas e introduzido um pseudo-framework capaz de gerar codigos para computadores classicos (C++) e computadores quânticos (QCL). Os algoritmos foram submetidos a simulacoes, 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 numeros muito parecidos entre sistemas classicos e quânticos, isso gera uma expectativa de que a busca em computadores quânticos reais seja muito mais eficiente.

Didier Gamaliel Buendía Ortiz

Juan Ignacio Cirac Sasturáin

Pedro Lara

Algoritmos de otimização são conhecidos por apresentarem uma vasta gama de aplicações em diversas áreas do conhecimento. Desta forma, qualquer melhoria no desempenho dos algoritmos de otimização gera grande impacto na resolução de diversos problemas. Neste sentido, este trabalho introduz a área de algoritmos quânticos para a otimização global (maximização/minimização) de funções contínuas através de diferentes métodos quânticos de busca e algoritmos clássicos de otimização local. Neste caso, a utilização de algoritmos quânticos de busca está diretamente associada ao desempenho com relação ao método clássico: usando um computador quântico pode-se encontrar um elemento em um banco de dados não-ordenado usando apenas $O(\sqrt{N})$ consultas.

Héctor Freytes, Graciela Domenech

André Soranzzo Mota, Marcelo Terra Cunha

O objetivo do trabalho é estudar algoritmos quânticos de busca, usados em computadores quânticos. Até então, algoritmos de busca utilizados em computadores clássicos dependem da estrutura na qual os dados estão organizados para serem ou não eficientes. Para conjuntos de dados não estruturados, o único jeito é verificar cada elemento do conjunto procurando o elemento passado na entrada do algoritmo, e dependendo da quantidade de elementos nesse conjunto, pode-se levar muito tempo, mesmo para computadores muito rápidos. Portanto, algoritmos que realizem busca de maneira eficiente são um atrativo e tanto para cientistas da computação, que podem pensar em inúmeras aplicações dos mesmos e tornar vários softwares cada vez mais eficientes. Tendo isso em vista, a computação quântica traz artifícios inexistentes na computação clássica que podem acelerar esse processo, como, por exemplo, o paralelismo quântico. Basicamente, consiste na capacidade de sobrepor todos os dados do conjunto em um único registrador, ou a grosso modo, analisar todos ao mesmo tempo, apesar de não ser tão simples quanto isso. É baseado nisso que temos o Algoritmo de Grover, que utilizando o paralelismo quântico, e reflexões no conjunto de dados, através do uso de transformações unitárias feitas por portas quânticas, temos uma probabilidade alta de que quando medirmos este registrador quântico, termos como resultado o dado procurado.