Onde está o Wally? Algoritmo Quântico de Busca (Grover)
Você já brincou de onde está o Wally?
A brincadeira consiste em encontrar o Wally em um cenário muito confuso, em que tudo (cores e formas) lembra o Wally.
Para encontrá-lo precisamos conhecer suas características. Podemos pensar em um conjunto de características que o Wally tem e ao comparar com outros objetos da figura verificamos se eles apresentam essas características. Se todas as características aparecerem, encontramos o Wally, caso contrário, continuamos procurando.
Olhando para a figura abaixo, podemos pensar que estamos buscando o Wally, olhando apenas para duas características:
- Cores vermelha e branca
- Humano com boina vermelha e branca
Vemos que o primeiro elemento da lista nossa lista de busca não possui nenhuma das duas características, portanto é representado por |00>.
O segundo (o mago) possui a primeira característica (cores), mas falha na segunda, portanto será representado por |01>.
O terceiro elemento (cachorro) passa na primeira, mas falha na segunda, portanto será representado como |10>.
E finalmente temos o Wally que possui todas as características que procuramos, portanto será representado como |11>
No exemplo acima estamos procurando em um universo de apenas duas características, codificando a informação em estados de dois qubits. Mas podemos codificar essa informação em estados quânticos com mais qubits e diluir mais propriedades. Por exemplo:
- calça azul
- óculos
- bengala
- camisa listrada
- cor vermelha
- cor branca
- sapado marrom
Com essas características, poderíamos definir o estado quântico do Wally como sendo |1111111> e caracterizar os elementos da figura acima como sendo (abaixo estamos seguindo o ordenamento |1234567>):
|0101000> — homem amarelo
|0000110> — mago
|0101110> — cachorro
Com essa codificação conseguimos colocar os dados de entrada no computador quântico (estados representados características do elemento buscado) e usar o algoritmo de Grover para procurá-lo nessa lista.
Procurando o Wally classicamente
O que faríamos é comparar cada elemento como que estamos buscando. Se der certo paramos a busca, se não der, tentamos o próximo elemento.
Procurando o Wally Quanticamente
A procura seria a equivalente a jogar uma luz em todos os elementos simultaneamente, aquele elemento que tem as características que buscamos vai brilhar, os demais ficarão opacos. No final só iremos ver um elemento brilhando (o que aparece com maior probabilidade) e os demais estarão praticamente apagados.
Nós conseguimos fazer esse teste simultâneo porque estamos utilizando o poder de paralelismo quântico (superposição)
Algoritmo de Grover
O Agoritmo de Grover é uma versão quântica do algoritmo de busca, que usa o fenômeno de paralelismo quântico para buscar soluções para o problema de busca. Ele apresenta uma melhoria quadrática em relação ao algoritmo clássico. Isso significa que, em uma lista com N elementos o algoritmo quântico precisaria ser executado cerca de √N vezes para achar a resposta, enquanto que o algoritmo clássico seria executado da ordem de N vezes.
Como construir o algoritmo de Grover no Qiskit?
O primeiro Gate é o Oráculo, e ele marca o estado que estamos procurando.
Como podemos ver abaixo, após aplicar U_w marcamos o estado |3> = |011> com um sinal negativo.
O segundo Gate é o Diffuser e ele amplifica a probabilidade do estado marcado e reduz a probabilidade dos estados não marcados.
Nosso circuito fica então:
- Qubits em superposição
- Oráculo
- Diffuser
Após aplicação do Diffuser podemos verificar como ficam as amplitudes dos estados. Relembrando que a amplitude não é a probabilidade, e por isso pode ser negativa. A probabilidade será o módulo quadrado da amplitude.
O que queremos após aplicar a sequência de gates acima é que o estado com maior amplitude (em módulo) seja o estado que marcamos. E como podemos ver o estado |3> é o de maior amplitude com -0.88388.
E se aplicarmos o algoritmo de Grover 2 vezes (Uw Us Uw Us)?
Como mostrado abaixo, a amplitude do estado aumentou ainda mais
A pergunta central então é?
Quantas vezes devemos aplicar Grover, de modo a amplificar a amplitude do estado que estamos buscando ao máximo?
Conseguirmos mostrar matematicamente que o número de iterações será igual a pi/4 * √N/t, onde t é a quantidade de elementos que estamos buscando e N é o tamanho da nossa lista.
Dessa maneira o nosso algoritmo de Grover final fica:
Vamos usar nosso algoritmo de Grover para buscar o elemento 4 em um lista que vai de 0 a 7.
Como podemos ver, o algoritmo nos retorno o número 4 (|100>) com probabilidade que igual a 1, enquanto que todos os outros elementos aparecem com probabilidade praticamente 0.
Vemos ainda que executamos a sequência Grover duas vezes.
Bem espero que tenham gostado e até o próximo post.
