Compartir a través de

Tutorial: Implementación del algoritmo de búsqueda de Grover en Q#

  • Artículo

En este tutorial, implementará el algoritmo de Grover en para resolver problemas basados en Q# búsquedas. Para obtener una explicación detallada de la teoría subyacente al algoritmo de Grover, consulte la Teoría del algoritmo de Grover.

En este tutorial ha:

  • Definición del algoritmo de Grover para un problema de búsqueda
  • Implementación del algoritmo de Grover en Q#

Sugerencia

Si desea acelerar el recorrido de la computación cuántica, consulte Código con Azure Quantum, una característica única del sitio web de Azure Quantum. Aquí puede ejecutar ejemplos integrados Q# o sus propios Q# programas, generar código nuevo Q# a partir de las indicaciones, abrir y ejecutar el código en VS Code para la Web con un solo clic y hacer preguntas a Copilot sobre la computación cuántica.

Requisitos previos

Definir el problema

El algoritmo de Grover es uno de los algoritmos más famosos de la computación cuántica. El tipo de problema que resuelve suele denominarse "búsqueda de una base de datos", pero es más preciso pensarlo en términos del problema de búsqueda.

Cualquier problema de búsqueda se puede formular matemáticamente con una función abstracta $f(x)$ que acepta elementos de búsqueda $x$. Si el elemento $x$ es una solución para el problema de búsqueda, entonces $f(x)=1$. Si el elemento $x$ no es una solución, $f(x)=0$. El problema de búsqueda consiste en buscar cualquier elemento $x_0$ de manera que $f(x_0)=1$.

Por lo tanto, puede formular cualquier problema de búsqueda como: dada una función clásica $f(x):\{0,1\}^n \rightarrow\{0,1\}$, donde $n$ es el tamaño de bits del espacio de búsqueda, busque una entrada $x_0$ para la que $f(x_0)=1$.

Para implementar el algoritmo de Grover para resolver un problema de búsqueda, debe:

  1. Transformar el problema en una tarea de Grover. Por ejemplo, suponga que quiere encontrar los factores de un entero $M$ mediante el algoritmo de Grover. Puede transformar el problema de factorización de enteros en una tarea de Grover mediante la creación de una función $$f_M(x)=1[r],$$ en la que $1[r]=1$ si $r=0$ y $1[r]=0$ si $r\neq0$, y $r$ es el resto de $M/x$. De este modo, los enteros $x_i$ que hacen $f_M(x_i)=1$ son los factores de $M$ y ha transformado el problema en una tarea de Grover.
  2. Implementar la función de la tarea de Grover como un oráculo cuántico. Para implementar el algoritmo de Grover, debe implementar la función $f(x)$ de la tarea de Grover como un oráculo cuántico.
  3. Usar el algoritmo de Grover con el oráculo para resolver la tarea. Una vez que tenga un oráculo cuántico, puede conectarlo a la implementación del algoritmo de Grover para resolver el problema e interpretar la salida.

Algoritmo de Grover

Supongamos que hay $N=2^n$ elementos aptos para el problema de búsqueda y se indexan asignando a cada elemento un entero de $0$ a $N-1$. Pasos generales del algoritmo

  1. Comienza con un registro de $n$ cúbits inicializados en el estado $\ket{0}$.
  2. Prepara el registro en una superposición uniforme aplicando $H$ a cada cúbit del registro: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
  3. Aplique las siguientes operaciones al registro $N_{\text{optimal}}$ veces:
    1. El oráculo de fase $O_f$ que aplica un cambio de fase condicional de $-1$ para los elementos de la solución.
    2. Aplica $H$ a cada cúbit del registro.
    3. Aplica $-O_0$, un cambio de fase condicional de $-1$ a cada estado de base computacional, excepto $\ket{0}$.
    4. Aplica $H$ a cada cúbit del registro.
  4. Mide el registro para obtener el índice de un elemento que es una solución con una probabilidad muy alta.
  5. Compruebe el elemento para ver si es una solución válida. Si no es así, vuelve a empezar.

Escribir el código para el algoritmo de Grover en Q#

En esta sección se describe cómo implementar el algoritmo en Q#. Hay algunas cosas que se deben tener en cuenta al implementar el algoritmo de Grover. Debe definir el estado marcado, cómo reflejarlo y cuántas iteraciones ejecutar el algoritmo. También debe definir el oráculo que implementa la función de la tarea de Grover.

Definir el estado marcado

En primer lugar, debe definir qué entrada está intentando encontrar en la búsqueda. Para ello, escriba una operación que aplique los pasos b, c y d del algoritmo de Grover.

Juntos, estos pasos también se conocen como el operador de difusión de Grover $-H^{\otimes n} O_0 H^{\otimes n}$.

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use outputQubit = Qubit();
    within {
        // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
        // toggling it results in a (-1) phase.
        X(outputQubit);
        H(outputQubit);
        // Flip the outputQubit for marked states.
        // Here, we get the state with alternating 0s and 1s by using the X
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

La ReflectAboutMarked operación refleja el estado base marcado por ceros y otros. Para ello, aplica el operador de difusión de Grover a los cúbits de entrada. La operación usa un cúbit auxiliar, , outputQubitque se inicializa en el estado $\ket{-}=\frac{1}{\sqrt{2}}(\ket-\ket{0}{1})$ aplicando las puertas $X$ y $H$. A continuación, la operación aplica la puerta de $X$ a todos los demás cúbits del registro, que voltea el estado del cúbit. Por último, aplica la puerta $X$ controlada al cúbit auxiliar y a los cúbits de entrada. Esta operación invierte el cúbit auxiliar si y solo si todos los cúbits de entrada están en el estado $\ket{1}$, que es el estado marcado.

Definir el número de iteraciones óptimas

La búsqueda de Grover tiene un número óptimo de iteraciones que produce la mayor probabilidad de medir una salida válida. Si el problema tiene $N=2^n$ posibles asignaciones de variables y $M$ de ellas son soluciones al problema, el número óptimo de iteraciones es:

$$N_{\text{optimal}}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}$$

Continuando iterando más allá del número óptimo de iteraciones comienza a reducir esa probabilidad hasta alcanzar una probabilidad de éxito casi cero en la iteración $2 N_{\text{optimal}}$. Después de eso, la probabilidad vuelve a crecer hasta $3 N_{\text{optimal}}$, y así sucesivamente.

En las aplicaciones prácticas, normalmente no se sabe cuántas soluciones tiene el problema antes de resolverlo. Una estrategia eficaz para controlar este problema es "suponer" el número de soluciones $M$ aumentando progresivamente en potencias de dos (es decir, 1, 2, 4, 8, 16, ..., 2^n$). Una de estas suposiciones estará lo suficientemente cerca como para que el algoritmo todavía encuentre la solución con un número promedio de iteraciones en torno a $\sqrt{\frac{N}{M}}$.

La función siguiente Q# calcula el número óptimo de iteraciones para un número determinado de cúbits en un registro.

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

La CalculateOptimalIterations función usa la fórmula anterior para calcular el número de iteraciones y, a continuación, la redondea al entero más cercano.

Definición de la operación de Grover

La Q# operación para el algoritmo de búsqueda de Grover tiene tres entradas:

  • Número de cúbits, nQubits : Int, en el registro de cúbits. Este registro codificará la solución provisional al problema de búsqueda. Después de la operación, se medirá.
  • Número de iteraciones óptimas, iterations : Int.
  • Una operación, phaseOracle : Qubit[] => Unit) : Result[], que representa el oráculo de fase para la tarea de Grover. Esta operación aplica una transformación unitaria a un registro de cúbit genérico.
operation GroverSearch( nQubits : Int, iterations : Int, phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];
    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

La GroverSearch operación inicializa un registro de $n$ cúbits en el estado $\ket{0}$, prepara el registro en una superposición uniforme y, a continuación, aplica el algoritmo de Grover para el número especificado de iteraciones. La propia búsqueda consta de reflejar repetidamente el estado marcado y el estado inicial, que puede escribir en Q# como bucle for. Por último, mide el registro y devuelve el resultado.

El código usa tres operaciones auxiliares: PrepareUniform, ReflectAboutUniformy ReflectAboutAllOnes.

Dado un registro en el estado de todos los ceros, la PrepareUniform operación prepara una superposición uniforme en todos los estados de base.

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

La operación ''ReflectAboutAllOnes' refleja el estado de todos los usuarios.

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

La operación ReflectAboutUniform refleja el estado uniforme de la superposición. En primer lugar, transforma la superposición uniforme en todo cero. A continuación, transforma el estado todo cero en todos los usuarios. Por último, refleja sobre el estado de todos los usuarios. La operación se llama ReflectAboutUniform porque se puede interpretar geométricamente como una reflexión en el espacio vectorial del estado uniforme de la superposición.

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        ReflectAboutAllOnes(inputQubits);
    }
}

Ejecución del código final

Ahora, tiene todos los ingredientes para implementar una instancia determinada del algoritmo de búsqueda de Grover y resolver el problema de factorización. Para finalizar, la Main operación configura el problema especificando el número de cúbits y el número de iteraciones.

operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");
    
    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
}

Ejecución del programa

Seleccione la plataforma deseada para ejecutar el programa.

Puede probar el Q# código con Copilot en Azure Quantum de forma gratuita: todo lo que necesita es una cuenta de correo electrónico de Microsoft (MSA). Para más información sobre Copilot en Azure Quantum, consulte Exploración de Azure Quantum.

  1. Abra Copilot en Azure Quantum en el explorador.

  2. Copie y pegue el código siguiente en el editor de código.

    import Microsoft.Quantum.Convert.*;
import Microsoft.Quantum.Math.*;
import Microsoft.Quantum.Arrays.*;
import Microsoft.Quantum.Measurement.*;
import Microsoft.Quantum.Diagnostics.*;

operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");

    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
}

operation GroverSearch(
    nQubits : Int,
    iterations : Int,
    phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];

    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use outputQubit = Qubit();
    within {
        // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
        // toggling it results in a (-1) phase.
        X(outputQubit);
        H(outputQubit);
        // Flip the outputQubit for marked states.
        // Here, we get the state with alternating 0s and 1s by using the X
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        // Transform the uniform superposition to all-zero.
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        // Now that we've transformed the uniform superposition to the
        // all-ones state, reflect about the all-ones state, then let the
        // within/apply block transform us back.
        ReflectAboutAllOnes(inputQubits);
    }
}

Sugerencia

Desde Copilot en Azure Quantum, puede abrir el programa en VS Code para web seleccionando el botón logotipo de VS Code en la esquina derecha del editor de código.

Ejecución del programa mediante el simulador en memoria

  1. Seleccione Simulador en memoria.
  2. Seleccione el número de capturas que se van a ejecutar y seleccione Ejecutar.
  3. Los resultados se muestran en el histograma y en los campos Resultados .
  4. Seleccione Explicar código para preguntar a Copilot para explicarle el código.

Ejecución del programa mediante el emulador de la serie H de Quantinuum

También puede enviar su programa al emulador gratuito de la serie H-Series quantinuum. El emulador simula un equipo cuántico con 20 cúbits.

  1. Seleccione la lista desplegable Simulador en memoria y seleccione Emulador de la serie H de Quantinuum.
  2. Seleccione el número de shots (actualmente limitados a 20) y seleccione Ejecutar.

Contenido relacionado

Explore otros tutoriales de Q#:

  • El entrelazamiento cuántico muestra cómo escribir un Q# programa que manipula y mide cúbits y muestra los efectos de la superposición y el entrelazamiento.
  • El generador de números aleatorios cuánticos muestra cómo escribir un Q# programa que genera números aleatorios fuera de cúbits en superposición.
  • Quantum Fourier Transform explora cómo escribir un Q# programa que direccione directamente los cúbits específicos.
  • Quantum Katas son tutoriales autodirigido y ejercicios de programación dirigidos a enseñar los elementos de la computación cuántica y Q# la programación al mismo tiempo.