Algoritmo de Grover

Para este módulo de Qiskit en el aula, los estudiantes deben tener un entorno Python funcional con los siguientes paquetes instalados:

• qiskit v2.1.0 o más reciente
• qiskit-ibm-runtime v0.40.1 o más reciente
• qiskit-aer v0.17.0 o más reciente
• qiskit.visualization
• numpy
• pylatexenc

Para configurar e instalar los paquetes anteriores, consulta la guía Instalar Qiskit. Para ejecutar trabajos en computadoras cuánticas reales, los estudiantes necesitarán configurar una cuenta con IBM Quantum® siguiendo los pasos de la guía Configura tu cuenta de IBM Cloud.

Este módulo fue probado y utilizó 12 segundos de tiempo de QPU. Esta es una estimación de buena fe; tu uso real puede variar.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introducción

El algoritmo de Grover es un algoritmo cuántico fundamental que aborda el problema de búsqueda no estructurada: dado un conjunto de $N$ elementos y una forma de verificar si cualquier elemento dado es el que está buscando, ¿qué tan rápido puedes encontrar el elemento deseado? En computación clásica, si los datos no están ordenados y no hay una estructura que explotar, el mejor enfoque es verificar cada elemento uno por uno, lo que conduce a una complejidad de consultas de $O(N)$ — en promedio, necesitará verificar aproximadamente la mitad de los elementos antes de encontrar el objetivo.

El algoritmo de Grover, introducido por Lov Grover en 1996, demuestra cómo una computadora cuántica puede resolver este problema de manera mucho más eficiente, requiriendo solo $O(\sqrt{N})$ pasos para encontrar el elemento marcado con alta probabilidad. Esto representa una aceleración cuadrática sobre los métodos clásicos, que es significativa para conjuntos de datos grandes.

El algoritmo opera en el siguiente contexto:

• Configuración del problema: Tiene una función $f(x)$ que devuelve 1 si $x$ es el elemento que desea, y 0 en caso contrario. Esta función a menudo se llama oráculo o caja negra, ya que solo puede aprender sobre los datos consultando $f(x)$.
• Utilidad de lo cuántico: Mientras que los algoritmos clásicos para este problema requieren, en promedio, $N/2$ consultas, el algoritmo de Grover puede encontrar la solución en aproximadamente $\pi\sqrt{N}/4$ consultas, que es mucho más rápido para $N$ grande.
• Cómo funciona (a alto nivel):
  • La computadora cuántica primero crea una superposición de todos los estados posibles, representando todos los elementos posibles a la vez.
  • Luego aplica repetidamente una secuencia de operaciones cuánticas (la iteración de Grover) que amplifica la probabilidad de la respuesta correcta y disminuye las otras.
  • Después de suficientes iteraciones, medir el estado cuántico produce la respuesta correcta con alta probabilidad.

Aquí hay un diagrama muy básico del algoritmo de Grover que omite muchos detalles. Para un diagrama más detallado, consulta este artículo.

Algunas cosas a tener en cuenta sobre el algoritmo de Grover:

• Es óptimo para búsqueda no estructurada: ningún algoritmo cuántico puede resolver el problema con menos de $O(\sqrt{N})$ consultas.
• Proporciona solo una aceleración cuadrática, no exponencial — a diferencia de algunos otros algoritmos cuánticos (por ejemplo, el algoritmo de Shor para factorización).
• Tiene implicaciones prácticas, como potencialmente acelerar ataques de fuerza bruta en sistemas criptográficos, aunque la aceleración no es suficiente para romper la mayoría de la encriptación moderna por sí sola.

Para estudiantes universitarios familiarizados con conceptos básicos de computación y modelos de consulta, el algoritmo de Grover ofrece una ilustración clara de cómo la computación cuántica puede superar los enfoques clásicos para ciertos problemas, incluso cuando la mejora es "solo" cuadrática. También sirve como puerta de entrada para comprender algoritmos cuánticos más avanzados y el potencial más amplio de la computación cuántica.

La amplificación de amplitud es un algoritmo cuántico de propósito general, o subrutina, que puede usarse para obtener una aceleración cuadrática sobre un puñado de algoritmos clásicos. El algoritmo de Grover fue el primero en demostrar esta aceleración en problemas de búsqueda no estructurada. Formular un problema de búsqueda de Grover requiere una función oráculo que marque uno o más estados de base computacional como los estados que estamos interesados en encontrar, y un circuito de amplificación que aumente la amplitud de los estados marcados, suprimiendo consecuentemente los estados restantes.

Aquí, demostramos cómo construir oráculos de Grover y usar el GroverOperator de la biblioteca de circuitos de Qiskit para configurar fácilmente una instancia de búsqueda de Grover. La primitiva Sampler del runtime permite la ejecución sin problemas de circuitos de Grover.

Teoría

Supón que existe una función $f$ que mapea cadenas binarias a una sola variable binaria, lo que significa

$$f: \Sigma^n \rightarrow \Sigma$$

Un ejemplo definido en $\Sigma^6$ es

$$f(x)= \begin{cases} 1 \qquad \text{si }x=\{010101\}\\ 0 \qquad \text{de otro modo } \end{cases}$$

Otro ejemplo definido en $\Sigma^{2n}$ es

$$f(x)= \begin{cases} 1 \qquad \text{si números iguales de 1 y 0 en la cadena}\\ 0 \qquad \text{de otro modo } \end{cases}$$

Su tarea es encontrar estados cuánticos correspondientes a aquellos argumentos $x$ de $f(x)$ que se mapean a 1. En otras palabras, encontrar todos los $\{x_1\}\in \Sigma^n$ tales que $f(x_1)=1$ (o si no hay solución, informar eso). Por supuesto, haremos esto en una computadora cuántica, usando estados cuánticos, por lo que es útil expresar estas cadenas binarias como estados:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

Usando la notación de estado cuántico (Dirac), estamos buscando uno o más estados especiales $\{|x_1\rangle\}$ en un conjunto de $N=2^n$ estados posibles, donde $n$ es el número de qubits, y con no-soluciones denotadas $\{|x_0\rangle\}.$

Podemos pensar en la función $f$ como proporcionada por un oráculo: una caja negra que podemos consultar para determinar su efecto en un estado $|x\rangle.$ En la práctica, a menudo conoceremos la función, pero puede ser muy complicada de implementar, lo que significa que reducir el número de consultas o aplicaciones de $f$ podría ser importante. Alternativamente, podemos imaginar un paradigma en el que una persona está consultando un oráculo controlado por otra persona, de modo que no conocemos la función oráculo, solo conocemos su acción en estados particulares de la consulta.

Este es un "problema de búsqueda no estructurada, en el sentido de que no hay nada especial sobre $f$ que nos ayude en nuestra búsqueda. Las salidas no están ordenadas ni se sabe que las soluciones se agrupan, y así sucesivamente. Considera las viejas guías telefónicas de papel como una analogía. Esta búsqueda no estructurada sería como escanear a través de ella buscando un cierto número, y no como buscar a través de una lista alfabetizada de nombres.

En el caso donde se busca una sola solución, clásicamente, esto requiere un número de consultas que es lineal en $N$. Claramente podría encontrar una solución en el primer intento, o podría no encontrar soluciones en las primeras $N-1$ conjeturas, de modo que necesite consultar la entrada $N^{th}$ para ver si hay alguna solución en absoluto. Dado que las funciones no tienen estructura explotable, requerirá $N/2$ conjeturas en promedio. El algoritmo de Grover requiere un número de consultas o cómputos de $f$ que escala como $\sqrt{N}.$

Esquema de circuitos en el algoritmo de Grover

Un recorrido matemático completo del algoritmo de Grover se puede encontrar, por ejemplo, en Fundamentals of quantum algorithms, un curso de John Watrous en IBM Quantum Learning. Un tratamiento condensado se proporciona en un apéndice al final de este módulo. Pero por ahora, solo revisaremos la estructura general del circuito cuántico que implementa el algoritmo de Grover.

El algoritmo de Grover se puede dividir en las siguientes etapas:

• Preparación de una superposición inicial (aplicando compuertas Hadamard a todos los qubits)
• "Marcar" el(los) estado(s) objetivo con un cambio de fase
• Una etapa de "difusión" en la que se aplican compuertas Hadamard y un cambio de fase a todos los qubits.
• Posibles repeticiones de las etapas de marcado y difusión para maximizar la probabilidad de medir el estado objetivo
• Medición

A menudo, la compuerta de marcado $Z_f$ y las capas de difusión que consisten en $H,$ $Z_{\text{OR}},$ y $H$ se denominan colectivamente el "operador de Grover". En este diagrama, solo se muestra una única repetición del operador de Grover.

Las compuertas Hadamard $H$ son bien conocidas y se usan ampliamente en la computación cuántica. La compuerta Hadamard crea estados de superposición. Específicamente está definida por

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

Su operación en cualquier otro estado se define a través de linealidad. En particular, una capa de compuertas Hadamard nos permite ir del estado inicial con todos los qubits en $|0\rangle$ (denotado $|0\rangle^{\otimes n}$) a un estado donde cada qubit tiene cierta probabilidad de ser medido en $|0\rangle$ o $|1\rangle;$ esto nos permite sondear el espacio de todos los estados posibles de manera diferente que en la computación clásica.

Una propiedad corolaria importante de la compuerta Hadamard es que actuar una segunda vez puede deshacer tales estados de superposición:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

Esto será importante en un momento.

Comprueba tu comprensión

Lee la pregunta a continuación, piensa en tu respuesta, luego haz clic en el triángulo para revelar la solución.

Partiendo de la definición de la compuerta Hadamard, demuestra que una segunda aplicación de la compuerta Hadamard deshace tales superposiciones como se afirma anteriormente.

Respuesta:

Cuando aplicamos X al estado $|+\rangle$, obtenemos el valor y +1 y al estado $|-\rangle$ obtenemos -1, entonces si tuviéramos una distribución 50-50, obtendríamos un valor esperado de 0.

La compuerta $Z_\text{OR}$ es menos común, y se define según

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{si } x = 0^n \\ -|x\rangle & \text{si } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

Finalmente, la compuerta $Z_f$ se define por

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

Nota que el efecto de esto es que $Z_f$ voltea el signo en un estado objetivo para el cual $f(x) = 1$ y deja otros estados sin afectar.

A un nivel muy alto y abstracto puede pensar sobre los pasos en el circuito de las siguientes maneras:

• Primera capa de Hadamard: coloca los qubits en una superposición de todos los estados posibles.
• $Z_f$: marcar el(los) estado(s) objetivo agregando un signo "-" al frente. Esto no cambia inmediatamente las probabilidades de medición, pero cambia cómo se comportará el estado objetivo en pasos subsiguientes.
• Otra capa de Hadamard: El signo "-" introducido en el paso anterior cambiará el signo relativo entre algunos términos. Dado que las compuertas Hadamard convierten una mezcla de estados computacionales $(|0\rangle+|1\rangle)/\sqrt{2}$ en un estado computacional, $|0\rangle,$ y convierten $(|0\rangle-|1\rangle)/\sqrt{2}$ en $|1\rangle$ esta diferencia de signo relativo ahora puede comenzar a jugar un papel en qué estados se miden.
• Una capa final de compuertas Hadamard se aplica, y luego se realizan mediciones. Veremos con más detalle cómo funciona esto en la siguiente sección.

Ejemplo

Para entender mejor cómo funciona el algoritmo de Grover, trabajemos a través de un pequeño ejemplo de dos qubits. Esto puede considerarse opcional para aquellos no enfocados en mecánica cuántica y notación de Dirac. Pero para aquellos que esperan trabajar sustancialmente con computadoras cuánticas, esto es altamente recomendado.

Aquí está el diagrama de circuito con los estados cuánticos etiquetados en varias posiciones a lo largo. Nota que con solo dos qubits, solo hay cuatro estados posibles que podrían medirse bajo cualquier circunstancia: $|00\rangle$, $|01\rangle$, $|10\rangle$, y $|11\rangle$.

Supongamos que el oráculo ($Z_f$, desconocido para nosotros) marca el estado $|01\rangle$. Trabajaremos a través de las acciones de cada conjunto de compuertas cuánticas, incluyendo el oráculo, y veremos qué distribución de estados posibles sale en el momento de la medición. Al principio, tenemos

$$|\psi_0\rangle = |00\rangle$$

Usando la definición de compuertas Hadamard, tenemos

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

Ahora el oráculo marca el estado objetivo:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

Nota que en este estado, los cuatro resultados posibles tienen la misma probabilidad de ser medidos. Todos tienen un peso de magnitud $1/2,$ lo que significa que cada uno tiene una probabilidad de $|1/2|^2=1/4$ de ser medido. Entonces, mientras que el estado $|01\rangle$ está marcado a través de la fase "-", esto aún no ha resultado en una probabilidad aumentada de medir ese estado. Continuamos aplicando la siguiente capa de compuertas Hadamard.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Combinando términos semejantes, encontramos

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

Ahora $Z_{\text{OR}}$ voltea el signo en todos los estados excepto $|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

Y finalmente, aplicamos la última capa de compuertas Hadamard:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Vale la pena trabajar a través de la combinación de estos términos para convencerse de que el resultado es de hecho:

$$|\psi_5\rangle =|01\rangle$$

Es decir, la probabilidad de medir $|01\rangle$ es 100% (en ausencia de ruido y errores) y la probabilidad de medir cualquier otro estado es cero.

Este ejemplo de dos qubits fue un caso especialmente limpio; el algoritmo de Grover no siempre resultará en una probabilidad del 100% de medir el estado objetivo. Más bien, amplificará la probabilidad de medir el estado objetivo. Además, el operador de Grover puede necesitar repetirse más de una vez.

En la siguiente sección, pondremos este algoritmo en práctica usando computadoras cuánticas IBM® reales.

La imagen geométrica

El ejemplo de dos qubits anterior mostró cómo funciona el álgebra para un caso pequeño, pero hay una manera mucho más intuitiva de entender el algoritmo de Grover: como una secuencia de reflexiones geométricas en un plano bidimensional. A continuación describimos esta imagen. También puedes consultar el curso de John Watrous Fundamentos de algoritmos cuánticos para más detalles.

Estableciendo el plano. Podemos descomponer el estado de superposición inicial $|\psi\rangle$ en dos componentes. El estado correcto — el que estamos buscando — lo llamamos $|A_1\rangle$. Todos los demás estados, agrupados, los llamamos $|A_0\rangle$. Por definición, $|A_1\rangle$ y $|A_0\rangle$ son ortogonales entre sí, por lo que podemos representarlos como ejes perpendiculares en un espacio abstracto bidimensional. Como $|\psi\rangle$ es una combinación lineal de estos dos componentes, se sitúa en un ángulo pequeño $\theta$ respecto al eje $|A_0\rangle$ — cerca de $|A_0\rangle$, porque al inicio solo una pequeña fracción del estado está en el componente correcto $|A_1\rangle$.

Reflexiones. El hecho matemático clave que necesitamos es que un operador de la forma

$$2|v\rangle\langle v| - I$$

refleja cualquier estado sobre el eje definido por $|v\rangle.$ Para entender por qué, considera dos casos: un estado a lo largo de $|v\rangle$ queda sin cambios, y un estado perpendicular a $|v\rangle$ tiene su signo invertido. Cualquier otro estado puede descomponerse en estos dos componentes, y el operador actúa sobre cada uno en consecuencia — lo que es exactamente una reflexión sobre $|v\rangle$.

Resulta que tanto el oráculo como los pasos de difusión en el algoritmo de Grover pueden expresarse como reflexiones en esta imagen geométrica.

El oráculo como reflexión. El oráculo invierte el signo del estado $|A_1\rangle$ y deja todo lo demás sin cambios. Eso es lo mismo que una reflexión sobre el eje $|A_0\rangle$.

La difusión como reflexión. Es un poco más difícil ver cómo el operador de difusión es también una reflexión. El operador de difusión es

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

$Z_{\text{OR}}$ por sí mismo es una reflexión sobre el estado todo-cero, ya que invierte el signo de cada estado que no sea $|0\rangle^{\otimes n}$. Esto puede escribirse como $2|0\rangle\langle 0| - I$. Las capas de Hadamard circundantes realizan efectivamente un cambio de base, transformando el eje de reflexión. Recuerda que $H^{\otimes n}$ mapea $|0\rangle^{\otimes n}$ a la superposición uniforme $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Como la transformada de Hadamard es su propia inversa, la expresión completa se convierte en

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

que es una reflexión sobre $|u\rangle$. Como $|u\rangle$ está muy cerca de $|\psi\rangle$ (ambos están casi sobre $|A_0\rangle$), esta segunda reflexión lleva el estado a un ángulo $2\theta$ desde donde empezó.

Rotación por $2\theta$. El efecto combinado de estas dos reflexiones es una rotación de $2\theta$ hacia $|A_1\rangle$. Cada iteración sucesiva del operador de Grover rota el estado en otros $2\theta.$

Número óptimo de iteraciones. Nuestro objetivo es rotar el estado lo más cerca posible a $|A_1\rangle$, lo que significa rotar un total de aproximadamente $\pi/2$ radianes (un cuarto de vuelta). Si cada iteración contribuye $2\theta$, el número óptimo de iteraciones $t$ satisface

$$(2t + 1)\theta \approx \frac{\pi}{2}$$

Para una sola solución entre $N$ estados, el ángulo inicial es $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (para $N$ grande). Sustituyendo,

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

De aquí proviene la famosa aceleración $\sqrt{N}$: solo necesitamos $O(\sqrt{N})$ iteraciones para alcanzar el objetivo, en lugar de las $O(N)$ comprobaciones que requeriría una búsqueda clásica.

Más en general, si hay $|A_1|$ estados de solución entre $N$ estados totales, el número óptimo de iteraciones es

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

Nota que si aplicas demasiadas iteraciones, rotas más allá de $|A_1\rangle$ y la probabilidad de encontrar tu estado objetivo comenzará a disminuir nuevamente. Encontrar el número correcto de iteraciones es importante, aunque en hardware cuántico ruidoso el número óptimo experimentalmente puede diferir de esta fórmula ideal.

¿Por qué es útil el algoritmo de Grover?

En este punto puede que te preguntes: acabamos de construir un oráculo que marca un estado objetivo — pero para construirlo, tuvimos que conocer el estado objetivo. Entonces, ¿qué estamos buscando realmente?

Esta es una pregunta válida, y hay varias buenas respuestas.

• El modelo de consulta es una herramienta teórica. El modelo de consulta de computación nunca fue diseñado para ser directamente práctico. Su propósito es darnos una manera limpia de analizar la complejidad algorítmica separando un problema en dos partes: el oráculo, y todo lo demás. ¿Qué tan difícil es la búsqueda, dado que la verificación es gratuita? ¿Cómo escala el número de consultas con el tamaño de la entrada? Estas son preguntas útiles incluso si ningún sistema real funciona exactamente de esta manera.

• También puedes pensarlo como una actividad de dos partes: una persona conoce el estado objetivo y construye el oráculo; el trabajo de la otra persona es encontrar la respuesta usando el oráculo como una caja negra, sin mirar adentro. En la Actividad 2 a continuación, harás exactamente esto con un compañero.

• La amplificación de amplitud es una subrutina ampliamente útil. Incluso si esta primera demostración parece circular, el mecanismo subyacente — llamado amplificación de amplitud — aparece una y otra vez en la computación cuántica. Lo que realmente estamos construyendo aquí es una intuición para una herramienta que aparece como subrutina en muchos algoritmos cuánticos más complejos.

• Hay problemas donde puedes construir un oráculo sin conocer la respuesta. La idea clave es que existe toda una clase de problemas para los cuales es muy difícil encontrar una solución, pero muy fácil verificar que una solución dada es correcta. La factorización es un ejemplo: dado un producto de dos números primos grandes, es extremadamente difícil determinar cuáles son esos primos, pero una vez que los tienes, puedes multiplicarlos fácilmente para verificar. (Tenemos un algoritmo mejor que el de Grover para la factorización específicamente — ver el algoritmo de Shor — pero este está lejos de ser el único problema con esta característica.) El Sudoku, la satisfacción de restricciones, e incluso el clásico juego del Buscaminas son todos problemas que son difíciles de resolver pero fáciles de verificar.

¿Por qué es eso relevante? Significa que podemos conocer todas las condiciones y requisitos que debe satisfacer una solución, y podemos codificar esos requisitos en un circuito cuántico que sirve como oráculo — incluso aunque no conozcamos la solución en sí. El algoritmo de Grover la encontrará por nosotros.

Con estas ideas en mente, trabajemos a través de varios ejemplos. Comenzaremos con un ejemplo en el que el estado de solución está claramente especificado para que podamos seguir la lógica del algoritmo. Luego pasaremos a una actividad de dos partes, y finalmente a un ejemplo en el que el oráculo se construye a partir de restricciones del problema en lugar del conocimiento de la respuesta.

Importaciones generales y enfoque

Comenzamos importando varios paquetes necesarios.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

A lo largo de este y otros tutoriales, usaremos un marco para computación cuántica conocido como "patrones Qiskit", que divide los flujos de trabajo en los siguientes pasos:

• Paso 1: Mapear entradas clásicas a un problema cuántico
• Paso 2: Optimizar el problema para ejecución cuántica
• Paso 3: Ejecutar usando primitivas Qiskit Runtime
• Paso 4: Post-procesamiento y análisis clásico

Generalmente seguiremos estos pasos, aunque puede que no siempre los etiquetemos explícitamente.

Actividad 1: Encontrar un único estado objetivo dado

Paso 1: Mapear entradas clásicas a un problema cuántico

Necesitamos la compuerta de consulta de fase para poner una fase general (-1) en los estados de solución, y dejar los estados no-solución sin afectar. Otra forma de decir esto es que el algoritmo de Grover requiere un oráculo que especifique uno o más estados de base computacional marcados, donde "marcado" significa un estado con una fase de -1. Esto se hace usando una compuerta controlled-Z, o su generalización multi-controlada sobre $N$ qubits. Para ver cómo funciona esto, considera un ejemplo específico de una cadena de bits {110}. Nos gustaría un circuito que actúe sobre un estado $|\psi\rangle = |q_2,q_1,q_0\rangle$ y aplique una fase si $|\psi\rangle = |011\rangle$ (donde hemos volteado el orden de la cadena binaria, debido a la notación en Qiskit, que pone el qubit menos significativo (a menudo 0) a la derecha).

Así, queremos un circuito $Z_f$ que logre

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{si} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{si} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

Podemos usar la compuerta de objetivo múltiple de control múltiple (MCMTGate) para aplicar una compuerta Z controlada por todos los qubits (voltear la fase si todos los qubits están en el estado $|1\rangle$). Por supuesto, algunos de los qubits en nuestro estado deseado pueden estar en $|0\rangle$. Por lo tanto, para esos qubits debemos primero aplicar una compuerta X, luego hacer la compuerta Z multi-controlada, luego aplicar otra compuerta X para deshacer nuestro cambio. La MCMTGate se ve así:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Nota que muchos qubits pueden estar involucrados en el proceso de control (aquí tres qubits lo están), pero ningún qubit único se denota como objetivo. Esto es porque todo el estado obtiene un signo "-" general (cambio de fase); la compuerta afecta a todos los qubits de manera equivalente. Esto es diferente de muchas otras compuertas de múltiples qubits, como la compuerta CX, que tiene un único qubit de control y un único qubit objetivo.

En el siguiente código, definimos una compuerta de consulta de fase (u oráculo) que hace lo que acabamos de describir arriba: marca uno o más estados de base de entrada definidos a través de su representación de cadena de bits. La compuerta MCMT se usa para implementar la compuerta Z multi-controlada.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

Ahora elegimos un estado "marcado" específico para ser nuestro objetivo, y aplicamos la función que acabamos de definir. Veamos qué tipo de circuito creó.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Si los qubits 1-3 están en el estado $|1\rangle$, y el qubit 0 está inicialmente en el estado $|0\rangle$, la primera compuerta X volteará el qubit 0 a $|1\rangle$ y todos los qubits estarán en $|1\rangle.$ Esto significa que la compuerta MCMT aplicará un cambio de signo general o cambio de fase, como se desea. Para cualquier otro caso, ya sea los qubits 1-3 están en el estado $|0\rangle$, o el qubit 0 se voltea al estado $|0\rangle$, y el cambio de fase no se aplicará. Vemos que este circuito efectivamente marca nuestro estado deseado $|0111\rangle,$ o la cadena de bits {1110}. El operador completo de Grover consiste en la compuerta de consulta de fase (oráculo), capas Hadamard, y el operador $Z_\text{OR}$. Podemos usar el grover_operator integrado para construir esto a partir del oráculo que definimos arriba.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Como discutimos en la imagen geométrica anterior, puede que necesitemos aplicar el operador de Grover múltiples veces. El número óptimo de iteraciones $t$ para maximizar la amplitud del estado objetivo en ausencia de ruido es

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

donde $|A_1|$ es el número de estados de solución y $N=2^n$ es el número total de estados. En computadoras cuánticas ruidosas modernas, el número experimentalmente óptimo de iteraciones podría ser diferente — pero aquí calculamos y usamos este número teórico óptimo usando $|A_1|=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

Ahora construyamos un circuito que incluya las compuertas Hadamard iniciales para crear una superposición de todos los estados posibles, y apliquemos el operador de Grover el número óptimo de veces.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

¡Hemos construido nuestro circuito de Grover!

Paso 2: Optimizar el problema para ejecución en hardware cuántico

Hemos definido nuestro circuito cuántico abstracto, pero necesitamos reescribirlo en términos de compuertas que son nativas de la computadora cuántica que queremos usar. También necesitamos especificar qué qubits en la computadora cuántica deben usarse. Por estas razones y otras, ahora debemos transpilar nuestro circuito. Primero, especifiquemos la computadora cuántica que deseamos usar.

Hay código a continuación para guardar tus credenciales en el primer uso. Asegúrate de eliminar esta información del notebook después de guardarla en tu entorno, para que tus credenciales no se compartan accidentalmente cuando compartas el notebook. Consulta Configura tu cuenta de IBM Cloud y Inicializa el servicio en un entorno no confiable para más orientación.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.

# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',
# instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Ahora usamos un administrador de pases preestablecido para optimizar nuestro circuito cuántico para el backend que seleccionamos.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Vale la pena notar en este momento que la profundidad del circuito cuántico transpilado es sustancial.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

Estos son en realidad números bastante grandes, incluso para este caso simple. Dado que todas las compuertas cuánticas (y especialmente las compuertas de dos qubits) experimentan errores y están sujetas a ruido, una serie de más de 100 compuertas de dos qubits no resultaría en nada más que ruido si los qubits no fueran de rendimiento extremadamente alto. Veamos cómo se desempeñan.

Paso 3: Ejecutar usando primitivas Qiskit

Queremos hacer muchas mediciones y ver qué estado es el más probable. Tal amplificación de amplitud es un problema de muestreo que es adecuado para ejecución con la primitiva Sampler de Qiskit Runtime.

Nota que el método run() de Qiskit Runtime SamplerV2 toma un iterable de bloques unificados primitivos (PUBs). Para Sampler, cada PUB es un iterable en el formato (circuit, parameter_values). Sin embargo, como mínimo, toma una lista de circuito(s) cuántico(s).

# To run on a real quantum computer (this was tested on a Heron r2 processor and
# used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Para aprovechar al máximo esta experiencia, recomendamos encarecidamente que ejecutes tus experimentos en las computadoras cuánticas reales disponibles de IBM Quantum. Sin embargo, si has agotado tu tiempo de QPU, puedes descomentar las líneas a continuación para completar esta actividad usando un simulador.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Paso 4: Post-procesar y devolver resultado en formato clásico deseado

Ahora podemos graficar los resultados de nuestro muestreo en un histograma.

plot_distribution(dist)

Vemos que el algoritmo de Grover devolvió el estado deseado con la probabilidad más alta por mucho, al menos un orden de magnitud más alto que otras opciones. En la siguiente actividad, usaremos el algoritmo de una manera que sea más consistente con el flujo de trabajo de dos partes de un algoritmo de consulta.

Comprueba tu comprensión

Lee las preguntas a continuación, piensa en tu respuesta, luego haz clic en el triángulo para revelar la solución.

Acabamos de buscar una única solución en un conjunto de $2^4=16$ estados posibles. Determinamos que el número óptimo de repeticiones del operador de Grover era $t=3$. ¿Este número óptimo habría aumentado o disminuido si hubiéramos buscado (a) cualquiera de varias soluciones, o (b) una única solución en un espacio de más estados posibles?

Respuesta:

Recuerda que mientras el número de soluciones sea pequeño comparado con todo el espacio de soluciones, podemos expandir la función seno alrededor de ángulos pequeños y usar

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) Vemos de la expresión anterior que aumentar el número de estados de solución disminuiría el número de iteraciones. Siempre que la fracción $\frac{|\mathcal{A}_1|}{N}$ aún sea pequeña, podemos describir cómo $t$ disminuiría: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) A medida que el espacio de soluciones posibles ($N$) aumenta, el número de iteraciones requeridas aumenta, pero solo como $t~\sqrt{N}$.

Supón que pudiéramos aumentar el tamaño de la cadena de bits objetivo para que sea arbitrariamente larga y aún tener el resultado de que el estado objetivo tiene una amplitud de probabilidad que es al menos un orden de magnitud mayor que cualquier otro estado. ¿Significa esto que podríamos usar el algoritmo de Grover para encontrar confiablemente el estado objetivo?

Respuesta:

No. Supón que repetimos la primera actividad con 20 qubits, y ejecutamos el circuito cuántico un número de veces num_shots = 10,000. Una distribución de probabilidad uniforme significaría que cada estado tiene una probabilidad de $10,000/2^{20}=0.00954$ de ser medido incluso una sola vez. Si la probabilidad de medir el estado objetivo fuera 10 veces esa de las no-soluciones (y la probabilidad de cada no-solución se disminuyera correspondientemente ligeramente), solo habría aproximadamente un 10% de probabilidad de medir el estado objetivo incluso una vez. Sería muy poco probable medir el estado objetivo múltiples veces, lo que lo haría indistinguible de los muchos estados de no-solución obtenidos aleatoriamente. La buena noticia es que podemos obtener resultados de mayor fidelidad usando supresión y mitigación de errores.

Actividad 2: Un flujo de trabajo preciso de algoritmo de consulta

Comenzaremos esta actividad exactamente como la primera, excepto que ahora te emparejarás con otro entusiasta de Qiskit. Elegirás una cadena de bits secreta, y tu compañero elegirá una cadena de bits (generalmente) diferente. Cada uno generará un circuito cuántico que funciona como un oráculo, y se intercambiarán. Luego usarás el algoritmo de Grover con ese oráculo para determinar la cadena de bits secreta de tu compañero.

Paso 1: Mapear entradas clásicas a un problema cuántico

Usando la función grover_oracle definida arriba, construye un circuito oráculo para uno o más estados marcados. Asegúrate de decirle a tu compañero cuántos estados has marcado, para que puedan aplicar el operador de Grover el número óptimo de veces. No hagas tu cadena de bits demasiado larga. 3-5 bits deberían funcionar sin mucha dificultad. Cadenas de bits más largas resultarían en circuitos profundos que requieren técnicas más avanzadas como mitigación de errores.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

Ahora has creado un circuito cuántico que voltea la fase de tu estado objetivo. Puedes guardar este circuito como my_circuit.qpy usando la sintaxis a continuación.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

Ahora envía este archivo a tu compañero (por correo electrónico, servicio de mensajería, un repositorio compartido, y demás). Haz que tu compañero te envíe su circuito también. Asegúrate de guardar el archivo en algún lugar donde puedas encontrarlo fácilmente. Una vez que tengas el circuito de tu compañero, podrías visualizarlo - pero eso rompe el modelo de consulta. Es decir, estamos modelando una situación en la que puedes consultar el oráculo (usar el circuito oráculo) pero no examinarlo para determinar qué estado marca.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Pregunta a tu compañero cuántos estados objetivo codificaron e ingrésalo a continuación.

# Update according to your partner's number of target states.
num_marked_states = 1

Esto se usa en la siguiente expresión para determinar el número óptimo de iteraciones de Grover.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Paso 2: Optimizar el problema para ejecución en hardware cuántico

Esto procede exactamente como antes.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Paso 3: Ejecutar usando primitivas Qiskit

Esto también es idéntico al proceso en la primera actividad.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used
# 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Paso 4: Post-procesar y devolver resultado en formato clásico deseado

Ahora muestra un histograma de tus resultados de muestreo. Uno o más estados deberían tener una probabilidad de medición mucho más alta que los demás. Reporta estos a tu compañero y verifica si determinó correctamente los estados objetivo. Por defecto, el histograma mostrado es del mismo circuito de la primera actividad. Deberías obtener resultados diferentes del circuito de tu compañero.

plot_distribution(dist)

Comprueba tu comprensión

Lee las preguntas o indicaciones a continuación, piensa en tu respuesta o discute el proceso con tu compañero. Haz clic en el triángulo para sugerencias o pistas.

Deberías haber obtenido correctamente el(los) estado(s) objetivo de tu compañero. Si no lo hiciste, trabaja con tu compañero para identificar qué salió mal. Haz clic a continuación para algunas ideas.

Sugerencias:

• Visualiza/dibuja el circuito de tu compañero y asegúrate de que se cargó correctamente.
• Compara los circuitos usados y compara el resultado esperado con el que obtuviste.
• Verifica la profundidad de los circuitos usados para asegurarte de que la cadena de bits no fuera demasiado larga o el número de iteraciones de Grover prohibitivamente alto.

Si aún no lo has hecho, dibuja el circuito oráculo que tu compañero te envió. Ve si puedes hablar del efecto de cada compuerta y argumentar cuál debe haber sido el estado objetivo. Esto será mucho más fácil para el caso de un único estado marcado que para múltiples.

Sugerencias:

• Recuerda que el trabajo del oráculo es voltear el signo en el estado objetivo.
• Recuerda que la MCMTGate voltea el signo en un estado si y solo si todos los qubits involucrados en el control están en el estado $|1\rangle$.
• Si tu estado objetivo ya tendrá un $|1\rangle$ en un qubit particular, entonces no necesitas hacer nada con ese qubit. Si tu objetivo tiene un $|0\rangle$ en un qubit particular y quieres que la MCMTGate voltee el signo, necesitas aplicar una compuerta X a ese qubit en tu oráculo (y luego deshacer la compuerta X después de la MCMTGate).

Repite el experimento con una iteración menos del operador de Grover. ¿Aún obtienes la respuesta correcta? ¿Por qué sí o por qué no?

Orientación:

Probablemente lo hará, aunque podría depender del número de soluciones codificadas. Esto resalta una sutileza: el número "óptimo" de iteraciones de Grover es el número que hace que la probabilidad de medir el estado marcado sea lo más alta posible. Pero menos iteraciones que eso aún podrían hacer que el estado marcado sea sustancialmente más probable que otros estados. Por lo tanto, podría arreglárselas con menos iteraciones que el número óptimo. Esto reduce la profundidad del circuito, y así reduce las tasas de error.

¿Por qué alguien querría usar menos iteraciones de Grover que el número "óptimo" identificado aquí?

Respuesta:

El número "óptimo" de iteraciones de Grover es el número que hace que la probabilidad de medir el estado marcado sea lo más alta posible en ausencia de ruido. Pero menos iteraciones que eso aún podrían hacer que el estado marcado sea sustancialmente más probable que otros estados. Entonces podría arreglárselas con menos iteraciones que el número óptimo. Esto reduce la profundidad del circuito, y así reduce las tasas de error.

Actividad 3: Resolver una cuadrícula del Buscaminas con el algoritmo de Grover

En la sección anterior, señalamos que el algoritmo de Grover se vuelve genuinamente útil cuando podemos construir un oráculo a partir de las restricciones de un problema, en lugar del conocimiento de la respuesta. El Buscaminas es un ejemplo perfecto: las celdas numeradas nos dicen cuántas minas son adyacentes, y esas restricciones determinan completamente dónde deben estar las minas — pero encontrar la configuración requiere búsqueda.

Se ha demostrado que el Buscaminas es NP-completo: es difícil de resolver pero fácil de verificar. Eso lo convierte en un candidato natural para el algoritmo de Grover. Por supuesto, aún no podemos resolver una cuadrícula completa de 9$\times$9 en una computadora cuántica ruidosa — los circuitos serían demasiado profundos. En cambio, usaremos una cuadrícula pequeña como demostración de juguete de cómo se abordaría un tablero más grande en una futura máquina tolerante a fallos.

Algunas advertencias importantes. El algoritmo de Grover proporciona solo una aceleración cuadrática sobre la búsqueda clásica no estructurada. El Buscaminas casi con certeza tiene estructura explotable que un algoritmo clásico inteligente podría aprovechar. Y para un espacio de búsqueda que crece exponencialmente, incluso la mejora $\sqrt{N}$ solo llega hasta cierto punto. Pero dejemos esas preocupaciones de lado y usemos este problema de juguete para ilustrar cómo las restricciones del problema se codifican en un oráculo cuántico.

La cuadrícula

Aquí está nuestra pequeña cuadrícula del Buscaminas:

Cada celda en blanco puede representarse mediante una variable binaria que indica si contiene una mina. Las etiquetamos $x_0$, $x_1$ y $x_2$, donde $x_i = 1$ significa que hay una mina en esa celda y $x_i = 0$ significa que no:

Podríamos resolverlo mentalmente en aproximadamente medio segundo, pero usamos este problema de juguete para ilustrar cómo se podría abordar un tablero mucho más difícil con una computadora cuántica.

Codificar las restricciones

Cada celda numerada impone una condición sobre las celdas en blanco adyacentes. Necesitamos expresar estas condiciones como expresiones booleanas que puedan codificarse en un circuito cuántico.

La celda "1" adyacente a $x_0$ y $x_1$ dice que exactamente una de ellas contiene una mina. Esta es precisamente la operación OR exclusivo (XOR), $\oplus$, que devuelve verdadero cuando exactamente una de sus entradas es verdadera:

$$(x_0 \oplus x_1)$$

De manera similar, la otra celda "1" (adyacente a $x_1$ y $x_2$) nos da:

$$(x_1 \oplus x_2)$$

La celda "2" dice que dos de las tres celdas en blanco deben contener minas. Como XOR es una operación de paridad, $x_0 \oplus x_1 \oplus x_2$ devuelve verdadero cuando un número impar de las variables son verdaderas. Queremos que un número par (específicamente dos) sea verdadero, por lo que negamos con $\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

Por sí sola, esta expresión se satisfaría con cero o dos qubits en el estado $|1\rangle$, ya que es una afirmación sobre la paridad. Pero combinada con las otras dos cláusulas, que cada una requiere al menos una mina, la única asignación satisfactoria tiene exactamente dos minas.

Las tres condiciones deben satisfacerse simultáneamente, por lo que las unimos con símbolos de conjunción $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

Paso 1: Mapear entradas clásicas a un problema cuántico

Ahora necesitamos codificar esta expresión booleana en un circuito cuántico que sirva como oráculo. La versión cuántica de XOR puede realizarse con compuertas CX (CNOT): aplicar dos compuertas CX desde los qubits de datos a un qubit de espacio de trabajo (ancilla) computa efectivamente su XOR y almacena el resultado en el ancilla.

Introducimos tres qubits de espacio de trabajo — uno para cada cláusula. Almacenamos el resultado de cada expresión booleana en su qubit de espacio de trabajo correspondiente, luego usamos una compuerta Z multi-controlada para invertir la fase del estado de tres qubits que hace que los tres qubits de espacio de trabajo sean $|1\rangle$ (es decir, todas las cláusulas se satisfacen simultáneamente).

En la primera celda de código a continuación, construimos la mitad de "cómputo" del oráculo — la parte que evalúa cada cláusula y escribe el resultado en los qubits de espacio de trabajo.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

En este punto, el resultado de cada cláusula está almacenado en su qubit de espacio de trabajo correspondiente. Ahora necesitamos que el estado de datos de tres qubits que hace que los tres qubits de espacio de trabajo sean $|1\rangle$ adquiera un signo negativo. Hacemos esto con una compuerta Z multi-controlada (implementada como una compuerta MCX flanqueada por compuertas Hadamard en el objetivo).

Después de aplicar el cambio de fase, debemos descomputar — deshacer todos los pasos de evaluación de cláusulas en orden inverso — para restablecer los qubits de espacio de trabajo a $|0\rangle.$ Esto es esencial para que los qubits de espacio de trabajo estén limpios para las iteraciones posteriores del operador de Grover.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Este circuito es nuestro oráculo: invierte la fase del estado de qubits de datos que satisface las tres restricciones del Buscaminas, y deja los qubits de espacio de trabajo de vuelta en $|0\rangle.$

Ahora construimos el operador de Grover completo a partir de este oráculo. Nota el argumento reflection_qubits: pasamos solo los qubits de datos x, porque los qubits de espacio de trabajo no forman parte del espacio de búsqueda. Su trabajo está hecho una vez que se ha aplicado el oráculo.

grover_op = grover_operator(qc, reflection_qubits=x)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Con tres qubits de datos y un estado de solución, el número óptimo de iteraciones de Grover es $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, por lo que usamos dos iteraciones. Aplicamos compuertas Hadamard a los qubits de datos para crear la superposición inicial, componemos el operador de Grover dos veces y medimos solo los qubits de datos.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

Paso 2: Optimizar el problema para ejecución en hardware cuántico

Como antes, transpilamos el circuito para el backend objetivo.

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

Ahora podemos verificar la profundidad del circuito transpilado. Como el oráculo del Buscaminas usa qubits de espacio de trabajo y múltiples compuertas CX, el circuito transpilado será más profundo que los de las actividades anteriores.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

Paso 3: Ejecutar usando primitivas Qiskit

# To run on a real quantum computer (this was tested on a Heron r2 processor and
#  used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Paso 4: Post-procesar y devolver resultado en formato clásico deseado

plot_distribution(dist)

El estado 101 debería aparecer con una probabilidad mucho mayor que cualquier otro, indicando que las minas están ubicadas en $x_0$ y $x_2$. ¡Hemos usado una computadora cuántica para resolver un pequeño juego de Buscaminas!

Por supuesto, los mejores algoritmos clásicos para el Buscaminas son mejores que una búsqueda por fuerza bruta a través de todas las configuraciones posibles de minas — explotan la estructura de la cuadrícula. El algoritmo de Grover solo ofrecería una ventaja en tableros extremadamente difíciles diseñados para ser maximalmente ambiguos, y aun así, la aceleración cuadrática significa que no puede mantener el ritmo con el crecimiento exponencial indefinidamente. Pero la verdadera conclusión es la técnica: codificar las restricciones del problema en un oráculo cuántico es un patrón poderoso que se extiende a la satisfacción de restricciones, la optimización combinatoria y muchos otros dominios.

Preguntas y conceptos críticos:

Conceptos críticos:

En este módulo, aprendimos algunas características clave del algoritmo de Grover:

• Mientras que los algoritmos de búsqueda no estructurada clásicos requieren un número de consultas que escala linealmente en el tamaño del espacio, $N,$ el algoritmo de Grover requiere un número de consultas que escala como $\sqrt{N}.$
• El algoritmo de Grover involucra repetir una serie de operaciones (comúnmente llamado el "operador de Grover") un número de veces $t,$ elegido para hacer que los estados objetivo sean óptimamente probables de ser medidos.
• El algoritmo de Grover puede ejecutarse con menos de $t$ iteraciones y aún amplificar los estados objetivo.
• El algoritmo de Grover encaja en el modelo de consulta de computación y tiene más sentido cuando una persona controla la búsqueda y otra controla/construye el oráculo. También puede ser útil como subrutina en otras computaciones cuánticas.
• Un oráculo puede construirse a partir de restricciones del problema en lugar del conocimiento de la solución, como se demuestra con el ejemplo del Buscaminas.

Preguntas V/F:

1. V/F El algoritmo de Grover proporciona una mejora exponencial sobre los algoritmos clásicos en el número de consultas necesarias para encontrar un único estado marcado en búsqueda no estructurada.

2. V/F El algoritmo de Grover funciona aumentando iterativamente la probabilidad de que se mida un estado de solución.

3. V/F Cuantas más veces itere el operador de Grover, mayor será la probabilidad de medir un estado de solución.

Preguntas MC:

1. Selecciona la mejor opción para completar la oración. La mejor estrategia para usar exitosamente el algoritmo de Grover en computadoras cuánticas modernas es iterar el operador de Grover...

• a. Solo una vez.
• b. Siempre $t$ veces, para maximizar la amplitud de probabilidad del(los) estado(s) de solución.
• c. Hasta $t$ veces, aunque menos puede ser suficiente para hacer que los estados de solución se destaquen.
• d. No menos de 10 veces.

2. Se muestra aquí un circuito de consulta de fase que funciona como un oráculo para marcar un cierto estado con un cambio de fase. ¿Cuál de los siguientes estados es marcado por este circuito?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Supón que quieres buscar tres estados marcados de un conjunto de 128. ¿Cuál es el número óptimo de iteraciones del operador de Grover para maximizar las amplitudes de los estados marcados?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Preguntas de discusión:

1. ¿Qué otros problemas podrías formular como una búsqueda de Grover? Piensa en problemas donde es difícil encontrar una solución pero fácil verificarla.

2. ¿Puedes ver algún problema con escalar el algoritmo de Grover en computadoras cuánticas modernas?