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 puede 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.

Matemáticas

Suponga 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. Considere 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.

Compruebe su comprensión

Lea la pregunta a continuación, piense en su respuesta, luego haga clic en el triángulo para revelar la solución.

Partiendo de la definición de la compuerta Hadamard, demuestre 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$$

Note 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. Note 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)$$

Note 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.

Advertencia obvia

Para aplicar el algoritmo de Grover, tuvimos que construir el operador de Grover, lo que significa que debemos poder voltear la fase en estados que satisfagan nuestros criterios de solución. Esto plantea la pregunta: si conocemos nuestro conjunto de soluciones tan bien que podemos diseñar un circuito cuántico para etiquetar cada uno, ¿qué estamos buscando?! La respuesta es triple, y revisaremos esto a lo largo del tutorial:

(1) Este tipo de algoritmos de consulta a menudo involucran a dos partes: una que tiene el oráculo que establece los criterios de solución, y otra que está intentando adivinar/encontrar un estado de solución. El hecho de que una persona pueda construir el oráculo no niega la necesidad de búsqueda.

(2) Hay problemas para los cuales es más fácil especificar un criterio de solución que encontrar la solución. El ejemplo más conocido de esto es probablemente identificar factores primos de números grandes. El algoritmo de Grover no es particularmente efectivo para resolver ese problema específico; usaríamos el algoritmo de Shor para factorización prima. Este es solo un ejemplo para señalar que conocer el criterio sobre el comportamiento de un estado no siempre es lo mismo que conocer el estado.

(3) El algoritmo de Grover no solo devuelve datos clásicos. Es cierto, si hacemos una medición del estado final después de $t$ repeticiones del operador de Grover, es probable que obtengamos información clásica identificando el estado de solución. Pero ¿qué pasa si no queremos información clásica; qué pasa si queremos un estado de solución preparado en una computadora cuántica para uso posterior en otro algoritmo? El algoritmo de Grover en realidad produce un estado cuántico con las soluciones fuertemente ponderadas. Por lo tanto, puede esperar encontrar el algoritmo de Grover como una subrutina en algoritmos cuánticos más complicados.

Con esto 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, y pasaremos a ejemplos en los que la utilidad del algoritmo de Grover se vuelve más clara.

Importaciones generales y enfoque

Comenzamos importando varios paquetes necesarios.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
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, considere 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")

Note 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 argumentamos arriba, 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 puede obtenerse de esta expresión:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

Aquí $A_1$ es el número de soluciones o estados objetivo. 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 sus credenciales en el primer uso. Asegúrese de eliminar esta información del notebook después de guardarla en su entorno, para que sus credenciales no se compartan accidentalmente cuando comparta 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.

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.

Note 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 ejecute sus experimentos en las computadoras cuánticas reales disponibles de IBM Quantum. Sin embargo, si ha agotado su tiempo de QPU, puede 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.

Compruebe su comprensión

Lea las preguntas a continuación, piense en su respuesta, luego haga 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:

Recuerde 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}$.

Suponga 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. Suponga 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 se emparejará con otro entusiasta de Qiskit. Elegirá una cadena de bits secreta, y su 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á el algoritmo de Grover con ese oráculo para determinar la cadena de bits secreta de su compañero.

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

Usando la función grover_oracle definida arriba, construya un circuito oráculo para uno o más estados marcados. Asegúrese de decirle a su compañero cuántos estados ha marcado, para que puedan aplicar el operador de Grover el número óptimo de veces. No haga su 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 ha creado un circuito cuántico que voltea la fase de su estado objetivo. Puede 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íe este archivo a su compañero (por correo electrónico, servicio de mensajería, un repositorio compartido, y demás). Haga que su compañero le envíe su circuito también. Asegúrese de guardar el archivo en algún lugar donde pueda encontrarlo fácilmente. Una vez que tenga el circuito de su compañero, podría visualizarlo - pero eso rompe el modelo de consulta. Es decir, estamos modelando una situación en la que puede 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")

Pregunte a su compañero cuántos estados objetivo codificaron e ingréselo 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 muestre un histograma de sus resultados de muestreo. Uno o más estados deberían tener una probabilidad de medición mucho más alta que los demás. Reporte estos a su compañero y verifique si determinó correctamente los estados objetivo. Por defecto, el histograma mostrado es del mismo circuito de la primera actividad. Debería obtener resultados diferentes del circuito de su compañero.

plot_distribution(dist)

Compruebe su comprensión

Lea las preguntas o indicaciones a continuación, piense en su respuesta o discuta el proceso con su compañero. Haga clic en el triángulo para sugerencias o pistas.

Debería haber obtenido correctamente el(los) estado(s) objetivo de su compañero. Si no lo hizo, trabaje con su compañero para identificar qué salió mal. Haga clic a continuación para algunas ideas.

Sugerencias:

• Visualice/dibuje el circuito de su compañero y asegúrese de que se cargó correctamente.
• Compare los circuitos usados y compare el resultado esperado con el que obtuvo.
• Verifique la profundidad de los circuitos usados para asegurarse 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 ha hecho, dibuje el circuito oráculo que su compañero le envió. Vea si puede 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:

• Recuerde que el trabajo del oráculo es voltear el signo en el estado objetivo.
• Recuerde 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 su estado objetivo ya tendrá un $|1\rangle$ en un qubit particular, entonces no necesita hacer nada con ese qubit. Si su objetivo tiene un $|0\rangle$ en un qubit particular y quiere que la MCMTGate voltee el signo, necesita aplicar una compuerta X a ese qubit en su oráculo (y luego deshacer la compuerta X después de la MCMTGate).

Repita el experimento con una iteración menos del operador de Grover. ¿Aún obtiene 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: Criterio distinto a una cadena de bits específica

Como ilustración final de cómo el algoritmo de Grover podría ser útil en el contexto de una subrutina, imaginemos que necesitamos estados cuánticos con un cierto número de 1s en la representación de cadena de bits. Esto es común en situaciones donde están involucradas leyes de conservación. Por ejemplo, en el contexto de química cuántica, a menudo se mapea un estado 1 de un qubit a una ocupación de un orbital electrónico. Para que la carga se conserve, el número total de 1s también debe permanecer constante. Las restricciones como esta son tan comunes que tienen un nombre especial: restricciones de peso de Hamming, y el número de 1s en el estado se llama peso de Hamming.

Paso 1:

Primero escribamos una función que marque estados con el peso de Hamming deseado. Lo escribiremos en general para un número no especificado de qubits num_qubits y peso de Hamming objetivo target_weight.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

Desde aquí todo el proceso es idéntico al de las dos actividades anteriores. Por brevedad, los pasos de patrones Qiskit se muestran solo en comentarios de código aquí.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(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()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

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)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

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

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

ibm_brisbane

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  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

Aquí el algoritmo de Grover efectivamente preparó los estados con peso de Hamming 2 para que sean mucho más probables de ser medidos que cualquier otro estado, aproximadamente un orden de magnitud más probable.

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.

Preguntas

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. Seleccione 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. Suponga que quiere 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é otras condiciones podría usar en un oráculo cuántico? Considere condiciones que son fáciles de establecer o imponer en una cadena de bits pero que no son meramente escribir las cadenas de bits marcadas.

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