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

Artículo
01/13/2024

Nota

Microsoft Quantum Development Kit (QDK clásico) ya no se admitirá después del 30 de junio de 2024. Si es un desarrollador de QDK existente, se recomienda realizar la transición al nuevo Azure Quantum Development Kit (QDK moderno) para seguir desarrollando soluciones cuánticas. Para obtener más información, consulte Migración Q# del código al QDK moderno.

En este tutorial, implementará el algoritmo de Grover en Q# para resolver problemas basados en 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, hará lo siguiente:

Defina el algoritmo de Grover para un problema de búsqueda.
Implemente el 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

Para ejecutar el ejemplo de código en Copilot en Azure Quantum:
- Una cuenta de correo electrónico de Microsoft (MSA).
Para desarrollar y ejecutar el ejemplo de código en Visual Studio Code:
- La versión más reciente de Visual Studio Code o abra VS Code en la Web.
- La versión más reciente de la extensión de Azure Quantum Development Kit . Para obtener más información sobre la instalación, consulte Instalación del QDK moderno en VS Code.

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 considerarlo 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 hacer lo siguiente:

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

Comienza con un registro de $n$ cúbits inicializados en el estado $\ket{0}$.
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$$
Aplica 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.
Mide el registro para obtener el índice de un elemento que es una solución con una probabilidad muy alta.
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 el número de iteraciones para las que 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 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 sobre el estado de base marcado por ceros alternativos y unos. 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{0}-\ket{1})$ aplicando las puertas $X$ y $H$. A continuación, la operación aplica la puerta $X$ a todos los demás cúbits del registro, lo que voltea el estado del cúbit. Por último, aplica la puerta $X$ controlada al cúbit auxiliar y 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}}$$

Continuar 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 siguiente Q# función 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 de 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 de inicio, 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 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 uno. Por último, refleja 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;
}

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.

Abra Copilot en Azure Quantum en el explorador.

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

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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 haciendo clic en el botón del logotipo de VS Code en la esquina derecha del editor de código.

Ejecución del programa mediante el simulador en memoria

Seleccione Simulador en memoria.
Seleccione el número de capturas que se van a ejecutar y haga clic en Ejecutar.
Los resultados se muestran en el histograma y en los campos Resultados .
Haga clic en Explicar código para pedir a Copilot que le explique 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.

Seleccione la lista desplegable Simulador en memoria y seleccione Quantinuum H-Series Emulator.
Seleccione el número de tomas (actualmente limitadas a 20) y seleccione Ejecutar.

Abra Visual Studio Code y seleccione Archivo > nuevo archivo de texto para crear un nuevo archivo.
Guarde el archivo como GroversAlgorithm.qs. Este archivo contendrá el Q# código del programa.

Copie el código siguiente en el GroversAlgorithm.qs archivo.

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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);
        }
    }
}

Antes de ejecutar el programa, debe establecer el target perfil en Sin restricciones. Seleccione Ver-> Paleta de comandos, busque QIR, seleccione Q#: Establezca el perfil de Azure Quantum QIR targety, a continuación, seleccione Q#: sin restricciones.
Para ejecutar el programa, seleccione Ejecutar Q# archivo en la lista desplegable icono de reproducción en la parte superior derecha o presione Ctrl+F5. El programa ejecuta la operación o función marcada con el @EntryPoint() atributo en el simulador predeterminado.
La salida aparecerá en la consola de depuración.