Algoritmo de Grover

Para este módulo de Qiskit en las aulas, los estudiantes deben tener un entorno Python en funcionamiento 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 ordenadores cuánticos reales, los estudiantes deberán crear una cuenta en IBM Quantum® siguiendo los pasos de la guía Configure su cuenta IBM Cloud.

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

# 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 fundacional que aborda el problema de la búsqueda no estructurada : dado un conjunto de elementos $N$ y una forma de comprobar si un elemento dado es el que se busca, ¿con qué rapidez se puede encontrar el elemento deseado? En la informática clásica, si los datos no están ordenados y no hay ninguna estructura que explotar, lo mejor es comprobar cada elemento uno por uno, lo que lleva a una complejidad de consulta de $O(N)$ - por término medio, habrá que comprobar aproximadamente la mitad de los elementos antes de encontrar el objetivo.

El algoritmo de Grover, introducido por Lov Grover en 1996, demuestra cómo un ordenador cuántico puede resolver este problema de forma mucho más eficiente, necesitando sólo $O(\sqrt{N})$ pasos para encontrar el elemento marcado con alta probabilidad. Esto representa una aceleración cuadrática con respecto a los métodos clásicos, lo que es significativo para grandes conjuntos de datos.

El algoritmo funciona en el siguiente contexto:

• Planteamiento del problema: Usted tiene una función $f(x)$ que devuelve 1 si $x$ es el elemento que desea, y 0 en caso contrario. Esta función suele denominarse oráculo o caja negra, ya que sólo es posible conocer los datos consultando $f(x)$.
• Utilidad de la cuántica: Mientras que los algoritmos clásicos para este problema requieren, por término medio, $N/2$ consultas, el algoritmo de Grover puede encontrar la solución en aproximadamente $\pi\sqrt{N}/4$ consultas, lo que es mucho más rápido para grandes $N$.
• Cómo funciona (a alto nivel):
  • El ordenador cuántico crea primero una superposición de todos los estados posibles, representando todos los elementos posibles a la vez.
  • A continuación, aplica repetidamente una secuencia de operaciones cuánticas (la iteración de Grover) que amplifica la probabilidad de la respuesta correcta y disminuye las demás.
  • Tras suficientes iteraciones, la medición del estado cuántico arroja la respuesta correcta con alta probabilidad.

He aquí un diagrama muy básico del algoritmo de Grover que omite muchos matices. Para ver un diagrama más detallado, consulte este documento.

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

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

Para los estudiantes universitarios familiarizados con los conceptos básicos de computación y los modelos de consulta, el algoritmo de Grover ofrece una clara ilustración de cómo la computación cuántica puede superar a los enfoques clásicos en determinados problemas, incluso cuando la mejora es "sólo" cuadrática. También sirve de puerta de entrada a la comprensión de algoritmos cuánticos más avanzados y al 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 utilizarse para obtener un aumento cuadrático de la velocidad con respecto a 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 estructurados. Formular un problema de búsqueda de Grover requiere una función de oráculo que marque uno o más estados de la base de cálculo como los estados que nos interesa encontrar, y un circuito de amplificación que aumente la amplitud de los estados marcados, suprimiendo en consecuencia los estados restantes.

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

teoría

Supongamos que existe una función $f$ que asigna cadenas binarias a una única variable binaria, es decir

Un ejemplo definido en $\Sigma^6$ es

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

Su tarea consiste en encontrar los estados cuánticos correspondientes a los argumentos $x$ de $f(x)$ que se asignan a 1. En otras palabras, encuentre todas las $\{x_1\}\in \Sigma^n$ tales que $f(x_1)=1$ (o si no hay solución, informe de ello). Nos referiríamos a las no soluciones como $x_0$. Por supuesto, haremos esto en un ordenador cuántico, utilizando estados cuánticos, por lo que es útil expresar estas cadenas binarias como estados:

Utilizando la notación de estado cuántico (Dirac), buscamos 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 las no soluciones denotadas $\{|x_0\rangle\}.$

Podemos pensar en la función $f$ como si nos la proporcionara un oráculo: una caja negra que podemos consultar para determinar su efecto sobre 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 tal manera que no conocemos la función del oráculo, sólo conocemos su acción sobre estados particulares a partir de la consulta.

Se trata de un "problema de búsqueda no estructurada, en el sentido de que no hay nada especial en $f$ que nos ayude en nuestra búsqueda". Las salidas no están ordenadas ni se sabe si las soluciones se agrupan, etc. Considere el uso de viejas guías telefónicas de papel como analogía. Esta búsqueda no estructurada sería como recorrerla buscando un número determinado, y no como buscar en una lista alfabetizada de nombres.

En el caso de que se busque una única solución, clásicamente, esto requiere un número de consultas que es lineal en $N$. Evidentemente, es posible que encuentre una solución en el primer intento, o puede que no encuentre ninguna solución en las primeras $N-1$ conjeturas, de modo que tenga que consultar la entrada $N^{th}$ para ver si hay alguna solución. Como las funciones no tienen una estructura explotable, necesitarás $N/2$ conjeturas por término medio. El algoritmo de Grover requiere un número de consultas o cálculos de $f$ que escala como $\sqrt{N}.$

Esquema de los circuitos del algoritmo de Grover

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

El algoritmo de Grover puede dividirse en las siguientes etapas:

• Preparación de una superposición inicial (aplicando puertas Hadamard a todos los qubits)
• "Marcar" el estado o estados de destino con un cambio de fase
• Una etapa de "difusión" en la que se aplican puertas 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
• Medida

A menudo, la puerta de marcado $Z_f$ y las capas de difusión formadas por $H,$ $Z_{\text{OR}},$ y $H$ se denominan colectivamente "operador Grover". En este diagrama, sólo se muestra una repetición del operador Grover.

Las puertas Hadamard $H$ son bien conocidas y se utilizan ampliamente en la informática cuántica. La puerta de Hadamard crea estados de superposición. En concreto, se define por

Su funcionamiento en cualquier otro estado se define a través de la linealidad. En concreto, una capa de puertas Hadamard nos permite pasar del estado inicial con todos los qubits en $|0\rangle$ (denotado $|0\rangle^{\otimes n}$ ) a un estado en el que 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 forma diferente a la computación clásica.

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

Esto será importante dentro de un momento.

Comprueba tu comprensión

Partiendo de la definición de la puerta de Hadamard, demuestre que una segunda aplicación de la puerta de Hadamard deshace tales superposiciones como se ha afirmado anteriormente.

• Respuesta

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

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

Por último, la puerta $Z_f$ se define por

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

A un nivel muy alto y abstracto, puedes pensar en los pasos del circuito de la siguiente manera:

• Primera capa de Hadamard: coloca los qubits en una superposición de todos los estados posibles.
• $Z_f$ : marca el estado o estados de destino añadiendo un signo "-" delante. Esto no cambia inmediatamente las probabilidades de medición, pero cambia cómo se comportará el estado objetivo en pasos posteriores.
• Otra capa de Hadamard: El signo "-" introducido en el paso anterior cambiará el signo relativo entre algunos términos. Dado que las puertas de 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 relativa de signos puede ahora empezar a desempeñar un papel en los estados que se miden.
• Se aplica una última capa de puertas Hadamard y, a continuación, se realizan las mediciones. Veremos con más detalle cómo funciona en la siguiente sección.

Ejemplo

Para entender mejor cómo funciona el algoritmo de Grover, vamos a trabajar con un pequeño ejemplo de dos qubits. Esto puede considerarse opcional para aquellos que no estén centrados en la mecánica cuántica y la notación de Dirac. Pero para quienes esperan trabajar sustancialmente con ordenadores cuánticos, es muy recomendable.

Aquí está el diagrama del circuito con los estados cuánticos etiquetados en varias posiciones a lo largo del mismo. Obsérvese que con sólo dos qubits, sólo hay cuatro estados posibles que podrían medirse en 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 puertas cuánticas, incluido el oráculo, y veremos qué distribución de estados posibles sale en el momento de la medición. Al principio, tenemos

Utilizando la definición de puertas Hadamard, tenemos

Ahora el oráculo marca el estado objetivo:

Obsérvese que en este estado, los cuatro resultados posibles tienen la misma probabilidad de ser medidos. Todos ellos 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. Por lo tanto, aunque el estado $|01\rangle$ está marcado a través de la fase "-", esto aún no se ha traducido en un aumento de la probabilidad de medir ese estado. Continuamos aplicando la siguiente capa de puertas Hadamard.

Combinando términos similares, encontramos

Ahora $Z_{\text{OR}}$ le da la vuelta al cartel en todos los estados menos en $|00\rangle$ :

Y por último, aplicamos la última capa de puertas Hadamard:

Merece la pena trabajar la combinación de estos términos para convencerse de que el resultado lo es realmente:

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

Este ejemplo de dos qubits era un caso especialmente limpio; el algoritmo de Grover no siempre funcionará para obtener un 100% de probabilidades de medir el estado objetivo. Más bien, amplificará la probabilidad de medir el estado objetivo. Además, es posible que el operador Grover tenga que repetirse más de una vez.

En la siguiente sección, pondremos en práctica este algoritmo utilizando ordenadores cuánticos reales IBM®.

La imagen geométrica

El ejemplo anterior de dos qubits mostraba cómo funciona el álgebra en un caso sencillo, pero hay una forma 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 los algoritmos cuánticos» para obtener más detalles.

Preparación del avión. Podemos descomponer el estado de superposición inicial $|\psi\rangle$ en dos componentes. Al estado correcto —el que estamos buscando— lo llamamos « $|A_1\rangle$ ». Al resto de estados, considerados en su conjunto, 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. Dado que $|\psi\rangle$ es una combinación lineal de estos dos componentes, forma un ángulo pequeño $\theta$ con respecto al eje $|A_0\rangle$ —cercano a $|A_0\rangle$ —, ya que al principio solo una pequeña fracción del estado se encuentra en el componente correcto $|A_1\rangle$.

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

refleja cualquier estado sobre el eje definido por $|v\rangle.$. Para entender por qué, consideremos dos casos: un estado en la dirección de $|v\rangle$ permanece inalterado, y un estado perpendicular a $|v\rangle$ cambia de signo. Cualquier otro estado puede descomponerse en estos dos componentes, y el operador actúa sobre cada uno de ellos en consecuencia, lo que constituye precisamente una reflexión sobre $|v\rangle$.

Resulta que tanto la etapa del oráculo como la de difusión del algoritmo de Grover pueden expresarse como reflexiones en este esquema geométrico.

El oráculo como reflejo. El oráculo invierte el signo del estado « $|A_1\rangle$ » y deja todo lo demás tal cual. Es lo mismo que una reflexión sobre el eje « $|A_0\rangle$ ».

La difusión como reflejo. Resulta un poco más complicado ver cómo el operador de difusión es también una reflexión. El operador de difusión es

$Z_{\text{OR}}$ por sí misma es una reflexión sobre el estado «todo a cero», ya que invierte el signo de todos los estados que no son « $|0\rangle^{\otimes n}$ ». Esto se puede escribir como $2|0\rangle\langle 0| - I$. Las capas de Hadamard circundantes realizan, en la práctica, un cambio de base, transformando el eje de reflexión. Recordemos que $H^{\otimes n}$ mapea $|0\rangle^{\otimes n}$ a la superposición uniforme $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Dado que la transformada de Hadamard es su propia inversa, la expresión completa queda así:

lo cual es un reflejo de $|u\rangle$. Dado que $|u\rangle$ está muy cerca de $|\psi\rangle$ (ambas se encuentran prácticamente junto a $|A_0\rangle$ ), este segundo reflejo desvía el estado hacia un ángulo de $2\theta$ con respecto a su punto de partida.

Rotación de $2\theta$. El efecto combinado de estos dos reflejos es una rotación de $2\theta$ hacia $|A_1\rangle$. Cada iteración sucesiva del operador de Grover hace girar el estado otros $2\theta.$

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

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

De ahí proviene la famosa aceleración de « $\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.

En términos más generales, si hay $|A_1|$ estados de solución entre un total de $N$ estados, el número óptimo de iteraciones es

Ten en cuenta que, si aplicas demasiadas iteraciones, sobrepasarás el punto de equilibrio ( $|A_1\rangle$ ) y la probabilidad de encontrar el estado deseado comenzará a disminuir de nuevo. Es importante determinar el número adecuado de iteraciones, aunque en hardware cuántico con ruido el número óptimo según los experimentos puede diferir de esta fórmula ideal.

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

Llegados a este punto, quizá te estés preguntando: acabamos de crear un oráculo que indica un estado objetivo, pero para crearlo, teníamos que conocer ese estado objetivo. Entonces, ¿qué es lo que estamos buscando realmente?

Es una pregunta razonable, y hay varias respuestas válidas.

• El modelo de consulta es una herramienta teórica. El modelo de computación basado en consultas nunca se diseñó para tener una aplicación práctica directa. Su objetivo es ofrecernos una forma clara de analizar la complejidad algorítmica dividiendo un problema en dos partes: el oráculo y todo lo demás. ¿Es muy difícil la búsqueda, teniendo en cuenta que la verificación es gratuita? ¿Cómo varía el número de consultas en función del tamaño de los datos de entrada? Estas preguntas resultan útiles, aunque ningún sistema real funcione exactamente así.

• También se puede considerar como una actividad entre dos personas: una conoce el estado objetivo y crea el oráculo; la otra tiene que averiguar la respuesta utilizando el oráculo como una caja negra, sin poder ver lo que hay dentro. En la Actividad 2 que aparece a continuación, harás precisamente eso con un compañero.

• La amplificación de amplitud es una subrutina de gran utilidad. Aunque esta primera demostración pueda parecer circular, el mecanismo subyacente —denominado amplificación de amplitud — aparece una y otra vez en la computación cuántica. Lo que realmente estamos desarrollando aquí es una intuición sobre una herramienta que aparece como subrutina en muchos algoritmos cuánticos más complejos.

• Hay problemas en los que se puede crear un oráculo sin conocer la respuesta. La idea fundamental es que existe toda una clase de problemas para los que resulta muy difícil encontrar una solución, pero muy fácil comprobar que una solución determinada es correcta. El factorizado es un ejemplo: dado el producto de dos números primos grandes, resulta extremadamente difícil determinar cuáles son esos números primos, pero una vez que se conocen, basta con multiplicarlos para verificarlo. (Tenemos un algoritmo mejor que el de Grover para la factorización en concreto —véase el algoritmo de Shor—, pero este no es, ni mucho menos, el único problema de esta función.) El sudoku, la resolución de restricciones e incluso el clásico juego del Buscaminas son problemas difíciles de resolver, pero fáciles de verificar.

¿Por qué es eso relevante? Esto significa que podemos conocer todas las condiciones y requisitos que debe cumplir una solución, y que podemos codificar esos requisitos en un circuito cuántico que actúe como oráculo, aunque no conozcamos la solución en sí. El algoritmo de Grover lo encontrará por nosotros.

Teniendo esto en cuenta, veamos varios ejemplos. Comenzaremos con un ejemplo en el que el estado de la solución está claramente especificado, para que podamos seguir la lógica del algoritmo. A continuación, pasaremos a una actividad para dos participantes y, por último, a un ejemplo en el que el oráculo se construye a partir de las restricciones del problema, en lugar de a partir del conocimiento de la respuesta.

Importaciones generales y enfoque

Empezaremos 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, utilizaremos un marco para la computación cuántica conocido como "patrones Qiskit", que divide los flujos de trabajo en los siguientes pasos:

• Paso 1: Asignar entradas clásicas a un problema cuántico
• Paso 2: Optimizar el problema para la ejecución cuántica
• Paso 3: Ejecutar utilizando Qiskit Runtime Primitives
• Etapa 4: Tratamiento posterior y análisis clásico

Por lo general, seguiremos estos pasos, aunque no siempre los etiquetemos explícitamente.

Actividad 1: Encontrar un único estado objetivo dado

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

Necesitamos la puerta de consulta de fase para poner una fase global (-1) en los estados solución, y dejar los estados no solución no afectados. Otra forma de decir esto es que el algoritmo de Grover requiere un oráculo que especifique uno o más estados base computacionales marcados, donde "marcado" significa un estado con una fase de -1. Para ello se utiliza una puerta Z controlada, o su generalización multicontrolada sobre $N$ qubits. Para ver cómo funciona, consideremos un ejemplo concreto de cadena de bits {110}. Nos gustaría un circuito que actuara sobre un estado $|\psi\rangle = |q_2,q_1,q_0\rangle$ y aplicara una fase si $|\psi\rangle = |011\rangle$ (donde hemos invertido 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).

Por lo tanto, queremos un circuito $Z_f$ que logre

Podemos utilizar la puerta de control múltiple de objetivo múltiple (MCMTGate) para aplicar una puerta Z controlada por todos los qubits (invertir la fase si todos los qubits están en el estado $|1\rangle$ ). Por supuesto, algunos de los qubits en nuestro estado deseado pueden ser $|0\rangle$. Por lo tanto, para esos qubits debemos aplicar primero una puerta X, luego hacer la puerta Z controlada por multiplicación, y luego aplicar otra puerta X para deshacer nuestro cambio. El MCMTGate tiene este aspecto:

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

Output:

Nótese que muchos qubits pueden estar implicados en el proceso de control (aquí lo están tres qubits), pero ningún qubit individual se denota como objetivo. Esto se debe a que todo el estado recibe un signo global "-" (cambio de fase); la puerta afecta a todos los qubits de forma equivalente. Esto difiere de muchas otras puertas de múltiples qubits, como la puerta CX , que tiene un único qubit de control y un único qubit objetivo.

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

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 que sea nuestro objetivo, y aplicamos la función que acabamos de definir. Veamos qué tipo de circuito ha creado.

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

Output:

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 puerta X volteará el qubit 0 a $|1\rangle$ y todos los qubits estarán en $|1\rangle.$. Esto significa que la puerta MCMT aplicará un cambio de signo global o un volteo de fase, según se desee. Para cualquier otro caso, o bien los qubits 1-3 están en el estado $|0\rangle$, o bien el qubit 0 está volteado al estado $|0\rangle$, y el volteo de fase no se aplicará. Vemos que este circuito marca efectivamente nuestro estado deseado $|0111\rangle,$ o la cadena de bits {1110}.

El operador Grover completo consta de la puerta de consulta de fase (oráculo), las capas Hadamard y el operador $Z_\text{OR}$. Podemos utilizar la función grover_operator para construirlo a partir del oráculo que hemos definido anteriormente.

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

Output:

Como hemos comentado en la ilustración geométrica anterior, es posible que tengamos que aplicar el operador de Grover varias veces. El número óptimo de iteraciones $t$ para maximizar la amplitud del estado objetivo en ausencia de ruido es

donde $|A_1|$ es el número de estados de solución y $N=2^n$ es el número total de estados. En los ordenadores cuánticos modernos, que suelen presentar ruido, el número óptimo de iteraciones según los resultados experimentales podría ser diferente; sin embargo, en este caso calculamos y utilizamos este número óptimo teórico mediante el método « $|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)

Output:

3

Construyamos ahora un circuito que incluya las puertas Hadamard iniciales para crear una superposición de todos los estados posibles, y apliquemos el operador 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")

Output:

¡Hemos construido nuestro circuito Grover!

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

Hemos definido nuestro circuito cuántico abstracto, pero tenemos que reescribirlo en términos de puertas nativas del ordenador cuántico que realmente queremos utilizar. También debemos especificar qué qubits del ordenador cuántico deben utilizarse. Por estas y otras razones, ahora debemos transpilar nuestro circuito. En primer lugar, especifiquemos el ordenador cuántico que deseamos utilizar.

A continuación encontrará un código para guardar sus credenciales la primera vez que las utilice. Asegúrate de borrar esta información del cuaderno después de guardarlo en tu entorno, para que tus credenciales no se compartan accidentalmente cuando compartas el cuaderno. Consulte Configurar su cuenta IBM Cloud e Inicializar el servicio en un entorno no fiable para obtener 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

Output:

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 utilizamos un gestor de pases predefinido para optimizar nuestro circuito cuántico para el backend que hemos seleccionado.

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")

Cabe señalar en este momento que la profundidad del circuito cuántico transpilado es considerable.

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),
)

Output:

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

En realidad son cifras bastante grandes, incluso para este caso sencillo. Dado que todas las puertas cuánticas (y especialmente las de dos qubits) experimentan errores y están sujetas a ruido, una serie de más de 100 puertas de dos qubits no daría más resultado que ruido si los qubits no fueran de altísimo rendimiento. Veamos cómo funcionan.

Paso 3: Ejecutar utilizando Qiskit primitives

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

Observe 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 (circuito, valores_parámetro). Sin embargo, como mínimo, necesita una lista de circuitos cuánticos.

# 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 sacar el máximo partido a esta experiencia, le recomendamos encarecidamente que realice sus experimentos en los ordenadores cuánticos reales disponibles en IBM Quantum. Sin embargo, si ha agotado su tiempo de QPU, puede descomentar las líneas de abajo para completar esta actividad utilizando 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: Procesamiento posterior y devolución del resultado en el formato clásico deseado

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

plot_distribution(dist)

Output:

Vemos que el algoritmo de Grover devolvió el estado deseado con la mayor probabilidad con diferencia, al menos un orden de magnitud superior a otras opciones. En la siguiente actividad, utilizaremos el algoritmo de una forma más coherente con el flujo de trabajo bipartito de un algoritmo de consulta.

Comprueba tu comprensión

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

• Respuesta

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

  $$(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) De la expresión anterior se deduce que al aumentar el número de estados solución disminuiría el número de iteraciones. Siempre que la fracción $\frac{|\mathcal{A}_1|}{N}$ siga siendo pequeña, podemos describir cómo disminuiría $t$ : $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

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

Supongamos que pudiéramos aumentar el tamaño de la cadena de bits objetivo para que fuera arbitrariamente larga y aún así obtener 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 utilizar el algoritmo de Grover para encontrar de forma fiable el estado objetivo?

• Respuesta

  Núm. Supongamos 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 aunque sólo sea una vez. Si la probabilidad de medir el estado objetivo fuera 10 veces mayor que la de las no-soluciones (y la probabilidad de cada no-solución disminuyera ligeramente en consecuencia), sólo habría un 10% de posibilidades de medir el estado objetivo aunque sólo fuera una vez. Sería muy improbable medir el estado objetivo varias veces, lo que lo haría indistinguible de los muchos estados no resueltos obtenidos aleatoriamente. La buena noticia es que podemos obtener resultados aún más fieles utilizando la supresión y mitigación de errores.

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

Comenzaremos esta actividad exactamente igual que la primera, salvo que ahora formarás pareja con otro entusiasta del 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 funcione como un oráculo, y los 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: Asignar entradas clásicas a un problema cuántico

Utilizando la función grover_oracle definida anteriormente, 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 pueda aplicar el operador Grover el número óptimo de veces. No hagas la cadena de bits demasiado larga. 3-5 bits deberían funcionar sin mucha dificultad. Las cadenas de bits más largas darían lugar a circuitos profundos que requieren técnicas más avanzadas, como la 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 invierte la fase de tu estado objetivo. Puede guardar este circuito como my_circuit.qpy utilizando la sintaxis siguiente.

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íe este archivo a su socio (por correo electrónico, servicio de mensajería, un repositorio compartido, etc.). Pide a tu compañero que te envíe también su circuito. 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 (utilizar el circuito del oráculo) pero no examinarlo para determinar a qué estado se dirige.

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 ha codificado e introdúcelo a continuación.

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

Esto se utiliza en la siguiente expresión para determinar el número óptimo de iteraciones 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 la ejecución en hardware cuántico

Se procede exactamente igual que 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 utilizando Qiskit primitives

Este proceso también es idéntico al de 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: Procesamiento posterior y devolución del resultado en el formato clásico deseado

Visualice ahora un histograma de los resultados del muestreo. Uno o más estados deben tener una probabilidad de medición mucho mayor que los demás. Comunícaselo a tu compañero y comprueba si has determinado 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)

Output:

Comprueba tu comprensión

Deberías haber obtenido correctamente el/los estado(s) objetivo de tu pareja. Si no lo ha hecho, trabaje con su compañero para identificar qué ha fallado. Haga clic a continuación para ver algunas ideas.

• Sugerencias
  • Visualiza/dibuja el circuito de tu compañero y asegúrate de que se ha cargado correctamente.
  • Compara los circuitos utilizados y compara el resultado esperado con el que has obtenido.
  • Comprueba la profundidad de los circuitos utilizados para asegurarte de que la cadena de bits no sea demasiado larga o el número de iteraciones Grover prohibitivamente alto.

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

• Sugerencias
  • Recordemos que el trabajo del oráculo es voltear el signo del estado objetivo.
  • Recordemos que la MCMTGate invierte el signo de un estado si y sólo si todos los qubits implicados en el control están en el estado $|1\rangle$.
  • Si tu estado objetivo ya tiene un $|1\rangle$ en un qubit en particular, entonces no necesitas hacer nada a ese qubit. Si tu objetivo tiene un $|0\rangle$ en un qubit en particular y quieres que el MCMTGate invierta el signo, necesitas aplicar una puerta X a ese qubit en tu oráculo (y luego deshacer la puerta X después del MCMTGate).

Repita el experimento con una iteración menos del operador Grover. ¿Sigue obteniendo la respuesta correcta? ¿Por qué sí o por qué no?

• Orientación

  Probablemente sí, aunque podría depender del número de soluciones codificadas. Esto pone de relieve una sutileza: el número "óptimo" de iteraciones Grover es el número que hace que la probabilidad de medir el estado marcado sea lo más alta posible. Pero un número de iteraciones menor que ese podría hacer que el estado marcado fuera sustancialmente más probable que otros estados. Por lo tanto, es posible que pueda salirse con la suya con menos iteraciones que el número óptimo. Esto reduce la profundidad del circuito y, por tanto, la tasa de errores.

¿Por qué querría alguien utilizar 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 un número de iteraciones menor que ese podría hacer que el estado marcado fuera sustancialmente más probable que otros estados. Por lo tanto, es posible que pueda realizar menos iteraciones que el número óptimo. Esto reduce la profundidad del circuito y, por tanto, la tasa de errores.

Actividad 3: Resuelve un tablero de «Buscaminas» con el algoritmo de Grover

En la sección anterior, señalamos que el algoritmo de Grover resulta realmente útil cuando podemos construir un oráculo a partir de las restricciones de un problema, en lugar de a partir del conocimiento de la respuesta. El Buscaminas es un ejemplo perfecto: las casillas numeradas nos indican cuántas minas hay adyacentes, y esas restricciones determinan por completo dónde deben estar las minas, pero para encontrar la configuración hay que realizar una búsqueda.

Se ha demostrado que el Buscaminas es un problema NP-completo: es difícil de resolver, pero fácil de verificar. Eso lo convierte en un candidato ideal para el algoritmo de Grover. Por supuesto, todavía no podemos resolver una cuadrícula completa de 9 × $\times$ 9 en un ordenador cuántico con ruido; los circuitos serían demasiado complejos. En su lugar, utilizaremos una pequeña cuadrícula como ejemplo sencillo para mostrar 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 solo ofrece una aceleración cuadrática con respecto a la búsqueda clásica no estructurada. Es casi seguro que el «Buscaminas» tiene una estructura que se puede aprovechar y que un algoritmo clásico inteligente podría utilizar. Y en un espacio de búsqueda que crece exponencialmente, ni siquiera la mejora que supone el « $\sqrt{N}$ » es suficiente. Pero dejemos esas preocupaciones a un lado y utilicemos este problema hipotético para ilustrar cómo se codifican las restricciones del problema en un oráculo cuántico.

La red

Aquí está nuestro tablero del «Buscaminas»:

Cada casilla en blanco puede representarse mediante una variable binaria que indica si contiene una mina. Denominamos a estas celdas « $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 la hay:

Podríamos resolverlo mentalmente en medio segundo, pero estamos utilizando este problema sencillo para ilustrar cómo se podría abordar un problema mucho más complejo con un ordenador cuántico.

Codificar las restricciones

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

La casilla «1» situada junto a $x_0$ y $x_1$ indica que exactamente una de ellas contiene una mina. Esta es precisamente la operación «o exclusivo» (XOR), $\oplus$, que devuelve «verdadero» cuando exactamente una de sus entradas es verdadera:

Del mismo modo, la otra celda con un «1» (adyacente a $x_1$ y $x_2$ ) nos da:

La casilla «2» indica que dos de las tres casillas en blanco deben contener minas. Dado que la operación XOR es una operación de paridad, la expresión « $x_0 \oplus x_1 \oplus x_2$ » devuelve «verdadero» cuando un número impar de variables son verdaderas. Queremos que sea cierto un número par (concretamente dos), así que lo negamos con « $\lnot$ »:

Por sí sola, esta expresión se cumpliría tanto con cero como con dos qubits en el estado « $|1\rangle$ », ya que se trata de una afirmación sobre la paridad. Pero, si se combinan con las otras dos condiciones, cada una de las cuales exige al menos una mina, la única solución válida es aquella que tiene exactamente dos minas.

Las tres condiciones deben cumplirse simultáneamente, por lo que las unimos con los símbolos «y» $\land$ :

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

Ahora tenemos que codificar esta expresión booleana en un circuito cuántico que haga las veces de oráculo. La versión cuántica de la operación XOR se puede realizar con puertas CX (CNOT): al aplicar dos puertas CX desde los qubits de datos a un qubit del espacio de trabajo (ancilla), se calcula efectivamente su operación XOR y se almacena el resultado en el qubit ancilla.

Introducimos tres qubits de espacio de trabajo: uno para cada cláusula. Almacenamos el resultado de cada expresión booleana en su qubit del espacio de trabajo correspondiente y, a continuación, utilizamos una puerta Z multicontrolada para invertir la fase del estado de tres qubits que hace que los tres qubits del espacio de trabajo sean « $|1\rangle$ » (lo que significa que todas las cláusulas se cumplen simultáneamente).

En la primera celda de código que aparece a continuación, construimos la parte «computacional» del oráculo: la parte que evalúa cada cláusula y escribe el resultado en los qubits del 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 se almacena en el qubit del espacio de trabajo correspondiente. Ahora necesitamos el estado de datos de tres qubits que haga que los tres qubits del espacio de trabajo $|1\rangle$ adquieran un signo negativo. Para ello utilizamos una puerta Z multicontrolada (implementada como una puerta MCX flanqueada por puertas de Hadamard en el objetivo).

Tras aplicar la inversión de fase, debemos «descomputar» —es decir, deshacer todos los pasos de evaluación de cláusulas en orden inverso— para restablecer los qubits del espacio de trabajo a su estado inicial ( $|0\rangle.$ ). Esto es esencial para que los qubits del espacio de trabajo estén «limpios» de cara a 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 del qubit de datos que cumple las tres restricciones del «Buscaminas» y devuelve los qubits del espacio de trabajo a su estado original $|0\rangle.$

Ahora construimos el operador de Grover completo a partir de este oráculo. xFíjate en reflection_qubits el argumento: solo pasamos los qubits de datos, ya que los qubits del espacio de trabajo no forman parte del espacio de búsqueda. Su trabajo habrá terminado una vez que se haya 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 de $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, por lo que utilizamos dos iteraciones. Aplicamos puertas de Hadamard a los qubits de datos para crear la superposición inicial, aplicamos el operador de Grover dos veces y medimos únicamente 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 la ejecución en hardware cuántico

Al igual que antes, compilamos el circuito para el backend de destino.

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 comprobar la profundidad del circuito transpilado. Dado que el oráculo del Buscaminas utiliza qubits de espacio de trabajo y múltiples puertas CX, el circuito transpilado tendrá más capas 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 utilizando Qiskit primitives

# 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: Procesamiento posterior y devolución del resultado en el formato clásico deseado

plot_distribution(dist)

El 101 estado debería aparecer con una probabilidad mucho mayor que cualquier otro, lo que indica que las minas se encuentran en $x_0$ y $x_2$. ¡Hemos utilizado un ordenador cuántico para resolver una partida del «Buscaminas»!

Por supuesto, los mejores algoritmos clásicos para el Buscaminas son más eficaces que una búsqueda por fuerza bruta que recorra todas las configuraciones posibles de minas, ya que aprovechan la estructura del tablero. El algoritmo de Grover solo ofrecería una ventaja en tableros extremadamente difíciles, diseñados para ser lo más ambiguos posible, e incluso en ese caso, la aceleración cuadrática implica que no puede seguir el ritmo del crecimiento exponencial de forma indefinida. Pero lo realmente importante es la técnica: codificar las restricciones de un problema en un oráculo cuántico es un patrón muy eficaz que se aplica a la satisfacción de restricciones, la optimización combinatoria y muchos otros campos.

Preguntas y conceptos clave:

Conceptos fundamentales:

En este módulo hemos aprendido algunas características clave del algoritmo de Grover:

• Mientras que los algoritmos clásicos de búsqueda no estructurada requieren un número de consultas que escala linealmente en el tamaño del espacio, el algoritmo de $N,$ Grover requiere un número de consultas que escala como $\sqrt{N}.$
• El algoritmo de Grover consiste en repetir una serie de operaciones (comúnmente denominadas "operador Grover") un número de veces $t,$ elegido para que los estados objetivo tengan una probabilidad óptima de ser medidos.
• El algoritmo de Grover puede ejecutarse con menos de $t$ iteraciones y seguir amplificando los estados objetivo.
• El algoritmo de Grover encaja en el modelo de consulta de la 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 otros cálculos cuánticos.
• Un oráculo puede construirse a partir de las restricciones del problema, en lugar de a partir del conocimiento de la solución, tal y como se ha demostrado con el ejemplo del «Buscaminas».

Preguntas de verdadero o falso:

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 la búsqueda no estructurada.

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

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

Preguntas del moderador:

1. Seleccione la mejor opción para completar la frase. La mejor estrategia para utilizar con éxito el algoritmo de Grover en los ordenadores cuánticos modernos es iterar el operador de Grover...

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

2. Aquí se muestra un circuito de consulta de fase que funciona como un oráculo para marcar un determinado estado con un cambio de fase. ¿Cuál de los siguientes estados queda marcado por este circuito?

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

3. Supongamos que desea 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
• decir, 20
• f. 33

Preguntas para el debate:

1. ¿Qué otros problemas se podrían plantear como búsqueda de Grover? Piensa en problemas para los que es difícil encontrar una solución, pero fácil verificarla.

2. ¿Ve algún problema en escalar el algoritmo de Grover en los ordenadores cuánticos modernos?