Búsqueda Cuántica con el Algoritmo de Grover
En este tutorial, aprenderemos sobre el algoritmo de Grover, que es un algoritmo cuántico para buscar en una base de datos no ordenada con una aceleración cuadrática en comparación con los algoritmos clásicos.
Nota
Si aún no lo has hecho, puede ser útil revisar primero estos tutoriales: Quantum Basics y Quantum Circuits.
El Problema
Supongamos que tienes una lista de N elementos y quieres encontrar un elemento específico que satisfaga cierta condición. Por ejemplo, podrías tener una lista de números de teléfono y querer encontrar el que pertenece a una persona específica.
Este es el problema de buscar en una base de datos no ordenada. Clásicamente, esto significaría tener algún arreglo e iterar a través de él. La versión cuántica de este problema consiste en encontrar un estado específico en una superposición de estados que satisfaga cierta condición.
Por ejemplo, podríamos tener el estado:
\(|\psi\rangle = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} |i\rangle\)
y queremos «encontrar» el estado \(|x\rangle\) tal que \(f(x) = 1\) para alguna función \(f\). Por lo tanto, queremos realizar alguna operación para aumentar la probabilidad de medir \(|x\rangle\) cuando medimos nuestro estado.
La Solución
Clásicamente, tendrías que verificar cada elemento uno por uno, lo que llevaría un tiempo \(O(N)\) en el peor caso. El algoritmo de Grover te permite encontrar el elemento deseado en un tiempo \(O(\sqrt{N})\), lo cual es una mejora significativa para N grande. Fue inventado por Lov Grover en 1996 y es uno de los algoritmos cuánticos más conocidos.
El algoritmo consta de dos partes: el oráculo y el operador de difusión.
El oráculo es una operación cuántica que marca el estado deseado invirtiendo su fase, en este caso correspondiendo a la función \(f\) que queremos evaluar. Puede representarse como un operador \(O\) tal que:
\(O |x\rangle = (-1)^{f(x)} |x\rangle\)
El operador de difusión es una operación cuántica que amplifica la amplitud del estado marcado, aumentando la probabilidad de medirlo. Puede representarse como un operador \(D\) tal que:
\(D = 2|\psi\rangle\langle\psi| - I\)
donde \(|\psi\rangle\) es el estado de superposición uniforme e \(I\) es el operador identidad.
Aplicando \(O\) seguido de \(D\) repetidamente, podemos amplificar la amplitud del estado marcado y aumentar la probabilidad de medirlo. Más concretamente, tras \(\text{floor}(\frac{\pi}{4} \sqrt{N})\) iteraciones, la probabilidad de medir el estado marcado será cercana a 1.
La Implementación
¿Cómo son en realidad estos operadores? El oráculo depende del problema específico que se intenta resolver, pero para casos como buscar una cadena de bits específica, puede implementarse con puertas X y Z controladas. Por ejemplo, si queremos buscar la cadena de bits «01» en un sistema de 2 cúbits, podemos implementar el oráculo de la siguiente manera:
from qilisdk.digital import Circuit, CZ, X
oracle = Circuit(2)
oracle.add(X(0))
oracle.add(CZ(0, 1))
oracle.add(X(0))
Esto invierte el bit del primer cúbit (de modo que nuestro estado objetivo es ahora «11»), aplica una puerta Z controlada que invierte la fase del estado «11» y luego devuelve el bit del primer cúbit a su estado original.
El operador de difusión es un poco más complicado, pero puede implementarse aplicando una puerta Hadamard y luego X en todos los cúbits, una puerta Z controlada en todos los cúbits y deshaciendo las operaciones anteriores:
from qilisdk.digital import Circuit, H, X, CZ
diffusion = Circuit(2)
diffusion.add(H(0))
diffusion.add(H(1))
diffusion.add(X(0))
diffusion.add(X(1))
diffusion.add(CZ(0, 1))
diffusion.add(X(1))
diffusion.add(X(0))
diffusion.add(H(1))
diffusion.add(H(0))
Nuestro estado inicial será el estado de superposición uniforme, que se puede preparar aplicando una puerta Hadamard a cada cúbit:
from qilisdk.digital import Circuit, H
initial_state = Circuit(2)
initial_state.add(H(0))
initial_state.add(H(1))
Ahora podemos combinar estas operaciones para implementar el algoritmo de Grover. Solo necesitamos una repetición porque tenemos 4 elementos en nuestro estado y \(\text{floor}(\frac{\pi}{4} \sqrt{4}) = 1\).
from qilisdk.digital import Circuit
grover = initial_state
grover += oracle
grover += diffusion
Simulando el resultado con QiliSim:
from qilisdk.backends import QiliSim
from qilisdk.functionals import DigitalPropagation
from qilisdk.readout import Readout
qilisim_backend = QiliSim()
result = qilisim_backend.execute(DigitalPropagation(grover), Readout().with_sampling(nshots=100))
print(result.get_samples())
Esto nos da:
{'01': 100}
Este es el resultado esperado ya que estábamos buscando el estado «01».