Algoritmo de Grover em detalhes
Na postagem de hoje estarei trazendo aqui a implementação do algoritmo de grover usando o Qiskit. Antes de começar o step by da step da construção vamos entender porque esse algoritmo é tão relevante.
Um dos problemas mais básicos em ciências da computação é a busca em base não estruturada. Basicamente o problema consiste em procurar um elemento em uma lista não ordenada. Classicamente a complexidade desse problema é dado em Big O notation por O(N). O algoritmo de Grover é capaz de reduzir essa complexidade para O(√N).
O que isso significa na prática?
Imagine que tenhamos uma lista com N elementos, para exemplificar melhor vamos escolher N = 100.000.000, ou seja, 100 milhões de elementos na lista. O melhor algoritmo clássico necessitaria de cerca de 100 milhões de iterações para achar o elemento procurado na lista, enquanto que um computador quântico utilizando o algoritmo de Grover poderia encontrá-lo com apenas 10.000 iterações. Ou seja, uma redução quadrática.
O algoritmo de Grover, ou pelo menos sua estrutura básica, é utilizado como sub-rotina de vários outros algoritmos quânticos, como por exemplo: amplitude amplification e amplitude estimation. Vale a pena entender a lógica de funcionamento e como construí-lo.
Entendendo Cálculo do Grover: Step by Step
No algoritmo de Grover iniciamos o circuito com todos os qubits em superposição. É nesse espaço de superposição que a lista de elementos é armazenada.
Após colocar os qubits em superposição vamos analisar o estado que estamos criando e escrevê-lo em uma base que facilite o nosso cálculo.
A escolha da base |s'>, |w> não foi aleatória. Iremos entender mais na frentes o porquê dessa escolha.
Como podemos ver acima, os estados |w> e |s'> formam uma base para nosso estado |s> e por isso podemos escrever:
O algoritmo de Grover tem como objetivo transformar |s> (o estado que temos inicialmente representando todos os elementos da lista) em |w> ( o elemento da lista que estamos buscando).
Essa "transformação" é feita por meio de dois operadores:
Setp 2: O primeiro Operador é que vai marcar o elemento da lista que estamos buscando. Por esse motivo ele muda de acordo com o elemento buscado. Matematicamente o que ele faz é colocar um sinal negativo na fase do estado marcado.
Step 3: O segundo operador U_s é chamado de Diffuser. Aplicando o Operado U_s, após aplicar o operador U_w, ratacionamos o estado |s> em direção ao estado |w>.
Vamos agora analisar step by step a atuação do operador U_s no estado U_w|s>:
Ao aplicar UsUw mais uma vez, obteremos:
A cada aplicação UsUw completamos uma rotação. A grande questão do algoritmo de Grover é saber quantas vezes devemos aplicar (UsUw) no estado |s> a fim de obter o estado |w> com maior probabilidade.
Vamos calcular qual seria esse número de aplicações.
O resultado acima é a chave do algoritmo de Grover. E com este cálculo que mostramos a vantagem quântica em relação à solução clássica.
Construindo Operadore Us e Uw no Circuito Quântico: Exemplo com 3 qubits
Abaixo mostramos um exemplo de como fica a construção do oráculo para cada um dos estados marcados no espaço de 3 qubits.
Como podemos ver acima, sempre que o qubit do estado que queremos marcar for zero, aplicamos X gate, e quando ele for 1, aplicamos a identidade (não fazemos nada). Em seguida aplicamos um MCZ (multi controled Z gate) com todos o n-1 qubits como controle e o último qubit como target. Isso vai mudar o sinal do estado que queremos marcar. Por último nós desfazermos a operação X gate para voltar ao estado original, mantendo o sinal negativo na fase.
A construção do operador Us é mais simples e independe do estado |w>
Construindo o Operador Us no circuito quântico:
Para finalizar vamos mostrar um exemplo da execução do algoritmo de Grover para um circuito com 3 qubits
- Colocamos os qubits em superposição.
- Escolhemos o elemento que iremos marcar.
- Preparamos Uw para o elemento procurado.
- Calculamos o número de vezes que precisaremos aplicar UsUw. Como N = 2³ = 8, t = π/4 √N ~ 2. Ou seja, aplicaremos UsUw 2 vezes.
- Vamos mostrar o Circuito:
A sequência UsUw foi aplicada 2 vezes, como previsto pelo cálculo. E abaixo mostramos o resultado do circuito. Com probabilidade ~ 1 encontramos o elemento buscado (nesse caso o 000).
Abaixo coloco outros plots para outros elementos marcados:
Independentemente do Elemento Marcado o algoritmo encontra-o com o mesmo número de iterações (nesse caso 2).
Esse detalhe é essencial para compreender o algoritmo de Grover. Uma vez que a lista agora é um estado em superposição, o ordenamento da lista não importa, uma vez que manipulamos todos os estados (elementos da lista) simultaneamente. Sendo assim, o algoritmo de Grover é menos eficiente que o clássico, se o elemento estiver entre os primeiros da lista, por exemplo. Grover sempre executará ~√N iterações, onde N é o número de elementos da lista, enquanto que o clássico poderá parar após a primeira iteração, caso o elemento seja o primeiro da lista.
Espero que tenham gostado e até a próxima.
