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

En este tutorial aprenderá a implementar el algoritmo de Grover en Q# para resolver problemas basados en búsquedas.

El algoritmo de Grover es uno de los algoritmos más famosos de la computación cuántica. El problema que resuelve se conoce habitualmente como "búsqueda en una base de datos", pero es más preciso pensar en él en términos del problema de búsqueda.

Cualquier tarea 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 la tarea 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$.

Nota

Este tutorial está destinado a personas que ya están familiarizadas con el algoritmo de Grover y quieran aprender a implementarlo en Q#. Para ver un tutorial más detallado, se recomienda el módulo de Microsoft Learn Solución de problemas de coloreado de grafos mediante la búsqueda de Grover. Para obtener una explicación detallada sobre la teoría subyacente al algoritmo de Grover, consulte el artículo conceptual Teoría del algoritmo de Grover.

Requisitos previos

En este tutorial, aprenderá a:

  • Crear oráculos cuánticos que implementan funciones clásicas en un equipo cuántico.
  • Explicar los roles de superposición, interferencia y entrelazamiento en la creación de algoritmos cuánticos.
  • Escriba un programa Q# que use el algoritmo de Grover para resolver un problema de coloración de gráficos.
  • Reconocer los tipos de problemas para los que el algoritmo de Grover puede ofrecer más velocidad en comparación con los algoritmos clásicos.

Tarea de algoritmo de Grover

Dada una función clásica $f(x):\{0,1\}^n \rightarrow\{0,1\}$, donde $n$ es el tamaño en bits del espacio de búsqueda, busque una entrada $x_0$ para la cual $f(x_0)=1$.

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

  1. Transformar el problema al formato de una tarea de Grover: por ejemplo, supongamos que queremos encontrar los factores de un número entero $M$ utilizando 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 transformamos 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.

Introducción rápida al algoritmo de Grover

Supongamos que hay $N=2^n$ elementos aptos para la tarea 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. 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.
  4. Mide el registro para obtener el índice de un elemento que es una solución con una probabilidad muy alta.
  5. Comprueba si se trata de una solución válida. Si no es así, vuelve a empezar.

Escritura de código para el algoritmo de Grover

Ahora, veamos cómo implementar el algoritmo en Q#.

Operador de difusión de Grover

En primer lugar, escriba una operación que aplique los pasos b, c y d del bucle anterior. Juntos, estos pasos también se conocen como el operador de difusión de Grover $-H^{\otimes n} O_0 H^{\otimes n}$

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {

    within {
        ApplyToEachA(H, inputQubits);
        ApplyToEachA(X, inputQubits);
    } apply {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

}

En esta operación, use la instrucción within-apply que implementa la conjugación automática de las operaciones que se producen en el operador de difusión de Grover.

Nota

Para obtener más información sobre las conjugaciones en Q#, consulte el artículo sobre conjugaciones en la guía del lenguaje Q#.

Un buen ejercicio para comprender el código y las operaciones es comprobar con lápiz y papel que la operación ReflectAboutUniform aplica el operador de difusión de Grover. Para verlo, tenga en cuenta que la operación Controlled Z(Most(inputQubits),Tail(inputQubits)) solo tiene un efecto diferente de la identidad si y solo si todos los cúbits están en el estado $\ket{1}$.

Para comprobar qué es cada una de las operaciones y funciones utilizadas, consulte la documentación de la API:

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.

Número de iteraciones

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 la iteración más allá de ese número empieza a reducir la probabilidad hasta llegar a una probabilidad de éxito casi nula en la iteración $2 N_{\text{optimal}}$. Después de eso, la probabilidad vuelve a crecer y utiliza $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}}$.

Operación de Grover completa

Ahora ya está todo listo para escribir una operación de Q# para el algoritmo de búsqueda de Grover. Tendrá tres entradas:

  • Una matriz de cúbits de register : Qubit[] que se debe inicializar en el estado todo Zero. Este registro codificará la solución provisional al problema de búsqueda. Después de la operación, se medirá.
  • Una operación phaseOracle : (Qubit[]) => Unit is Adj 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.
  • Un número entero iterations : Int que representa las iteraciones del algoritmo.
operation RunGroversSearch(register : Qubit[], phaseOracle : (Qubit[]) => Unit is Adj, iterations : Int) : Unit {
    // Prepare register into uniform superposition.
    ApplyToEach(H, register);
    // Start Grover's loop.
    for _ in 1 .. iterations {
        // Apply phase oracle for the task.
        phaseOracle(register);
        // Apply Grover's diffusion operator.
        ReflectAboutUniform(register);
    }
}

Sugerencia

Este código es genérico; se puede usar para resolver cualquier problema de búsqueda. Pasamos el oráculo cuántico -la única operación que se basa en el conocimiento de la instancia del problema que queremos resolver -como un parámetro al código de búsqueda.

Implementación del oráculo

Una de las propiedades clave que hace que el algoritmo de Grover sea más rápido es la capacidad de los equipos cuánticos de realizar cálculos no solo sobre entradas individuales sino también sobre superposiciones de entradas. Es necesario calcular la función $f(x)$ que describe la instancia de un problema de búsqueda usando solo operaciones cuánticas. De este modo, se puede calcular con una superposición de entradas.

Lamentablemente, no hay una manera automática de traducir funciones clásicas a operaciones cuánticas. Es un campo que se está investigando y que se denomina computación reversible.

Sin embargo, hay algunas directrices que pueden ayudarle a traducir la función $f(x)$ en un oráculo cuántico:

  1. Divida la función clásica en pequeños bloques de creación que resulten fáciles de implementar. Por ejemplo, puede intentar descomponer la función $f(x)$ en una serie de operaciones aritméticas o puertas lógicas booleanas.
  2. Use los bloques de creación de nivel superior de la biblioteca de Q# para implementar las operaciones intermedias. Por ejemplo, si descompone la función en una combinación de operaciones aritméticas simples, puede usar la biblioteca de valores numéricos para implementar las operaciones intermedias.

La siguiente tabla de equivalencia puede resultar útil al implementar funciones booleanas en Q#.

Puerta lógica clásica Operation de Q#:
$NOT$ X
$XOR$ CNOT
$AND$ CCNOT con un cúbit auxiliar

Ejemplo: Operación cuántica para comprobar si un número es un divisor

Importante

En este tutorial, se factoriza un número mediante el algoritmo de búsqueda de Grover como un ejemplo didáctico para mostrar cómo traducir un problema matemático simple en una tarea de Grover. Sin embargo, el algoritmo de Grover NO es un algoritmo eficaz para resolver el problema de factorización de enteros. Para explorar un algoritmo cuántico que resuelva el problema de factorización de enteros más rápido que cualquier algoritmo clásico, consulte el ejemplo del algoritmo de Shor.

Por ejemplo, veamos cómo expresaríamos la función $f_M(x)=1[r]$ del problema de factoración como una operación cuántica en Q#.

De forma clásica, calcularía el resto de la división $M/x$ y comprobaría si es igual a cero. Si es así, el programa genera 1; de lo contrario, genera 0. Necesita:

  • Calcular el resto de la división.
  • Aplicar una operación controlada sobre el bit de salida para que si es 1, el resto sea 0.

Por lo tanto, es necesario calcular una división de dos números con una operación cuántica. Afortunadamente, no es necesario escribir el circuito que implementa la división desde cero; puede usar la operación DivideI de la biblioteca de valores numéricos en su lugar.

Si observamos la descripción de DivideI, vemos que necesita tres registros de cúbits: el dividendo de $n$ bits xs, el divisor de $n$ bits ys, y el result de $n$ bits que se debe inicializar en el estado Zero. La operación es Adj + Ctl, por lo que se puede conjugar y usar en instrucciones within-apply. Además, en la descripción indica que el dividendo del registro de entrada xs se reemplaza por el resto. Esto es perfecto, porque nos interesa exclusivamente el resto y no el resultado de la operación.

Después, puede crear una operación cuántica que haga lo siguiente:

  1. Tomar tres entradas:
    • El dividendo, number : Int. Es $M$ en $f_M(x)$.
    • Una matriz de cúbits que codifica el divisor, divisorRegister : Qubit[]. Esto es $x$ en $f_M(x)$, posiblemente en un estado de superposición.
    • Un cúbit de destino, target : Qubit, que se invierte si la salida de $f_M(x)$ es $1$.
  2. Calcula la división $M/x$ usando solo operaciones cuánticas reversibles e invierte el estado de target si y solo si el resto es cero.
  3. Revierte todas las operaciones, excepto la inversión de target, para devolver los cúbits auxiliares usados al estado cero sin introducir operaciones irreversibles, como la medida. Este paso es importante para conservar el entrelazamiento y la superposición durante el proceso.

El código para implementar esta operación cuántica es:

operation MarkDivisor (
    dividend : Int,
    divisorRegister : Qubit[],
    target : Qubit
) : Unit is Adj + Ctl {
    // Calculate the bit-size of the dividend.
    let size = BitSizeI(dividend);
    // Allocate two new qubit registers for the dividend and the result.
    use dividendQubits = Qubit[size];
    use resultQubits = Qubit[size];
    // Create new LittleEndian instances from the registers to use DivideI
    let xs = LittleEndian(dividendQubits);
    let ys = LittleEndian(divisorRegister);
    let result = LittleEndian(resultQubits);

    // Start a within-apply statement to perform the operation.
    within {
        // Encode the dividend in the register.
        ApplyXorInPlace(dividend, xs);
        // Apply the division operation.
        DivideI(xs, ys, result);
        // Flip all the qubits from the remainder.
        ApplyToEachA(X, xs!);
    } apply {
        // Apply a controlled NOT over the flipped remainder.
        Controlled X(xs!, target);
        // The target flips if and only if the remainder is 0.
    }
}

Nota

El programa aprovecha la instrucción within-apply para lograr el paso 3. Como alternativa, se pueden escribir explícitamente los elementos contiguos de cada una de las operaciones dentro del bloque within después de la inversión controlada de target. La instrucción within-apply lo hace por nosotros y hace que el código sea más corto y legible. Uno de los objetivos principales de Q# es facilitar la escritura y lectura de programas cuánticos.

Transformación de la operación en un oráculo de fase

La operación MarkDivisor es lo que se conoce como un oráculo de marcado, porque marca los elementos válidos con un cúbit auxiliar entrelazado (target). Sin embargo, el algoritmo de Grover necesita un oráculo de fase, es decir, un oráculo que aplique un cambio de fase condicional de $-1$ a los elementos de la solución. Pero no se preocupe, la operación anterior no se escribió en vano. Cambiar de un tipo de oráculo a otro en Q# es muy fácil.

Puede aplicar cualquier oráculo de marcado como un oráculo de fase con la siguiente operación:

operation ApplyMarkingOracleAsPhaseOracle(
    markingOracle : (Qubit[], Qubit) => Unit is Adj,
    register : Qubit[]
) : Unit is Adj {
    use target = Qubit();
    within {
        X(target);
        H(target);
    } apply {
        markingOracle(register, target);
    }
}

Esta famosa transformación se conoce también como retroceso de fase y es muy utilizada en numerosos algoritmos de computación cuántica. Encontrará una explicación detallada de esta técnica en este módulo de Microsoft Learn.

Ahora, tiene todos los ingredientes para implementar una instancia determinada del algoritmo de búsqueda de Grover y resolver el problema de factorización.

Vamos a usar el programa siguiente para encontrar un factor de 21. Para simplificar el código, supongamos que conocemos el número $M$ de elementos válidos. En este caso, $M=4$, porque hay dos factores, 3 y 7, más 1 y 21.

namespace GroversTutorial {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Preparation;

    @EntryPoint()
    operation FactorizeWithGrovers(number : Int) : Unit {

        // Define the oracle that for the factoring problem.
        let markingOracle = MarkDivisor(number, _, _);
        let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
        // Bit-size of the number to factorize.
        let size = BitSizeI(number);
        // Estimate of the number of solutions.
        let nSolutions = 4;
        // The number of iterations can be computed using the formula.
        let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

        // Initialize the register to run the algorithm
        use (register, output) = (Qubit[size], Qubit());
        mutable isCorrect = false;
        mutable answer = 0;
        // Use a Repeat-Until-Succeed loop to iterate until the solution is valid.
        repeat {
            RunGroversSearch(register, phaseOracle, nIterations);
            let res = MultiM(register);
            set answer = BoolArrayAsInt(ResultArrayAsBoolArray(res));
            // Check that if the result is a solution with the oracle.
            markingOracle(register, output);
            if MResetZ(output) == One and answer != 1 and answer != number {
                set isCorrect = true;
            }
            ResetAll(register);
        } until isCorrect;

        // Print out the answer.
        Message($"The number {answer} is a factor of {number}.");

    }

    operation MarkDivisor (
        dividend : Int,
        divisorRegister : Qubit[],
        target : Qubit
    ) : Unit is Adj+Ctl {
        let size = BitSizeI(dividend);
        use (dividendQubits, resultQubits) = (Qubit[size], Qubit[size]);
        let xs = LittleEndian(dividendQubits);
        let ys = LittleEndian(divisorRegister);
        let result = LittleEndian(resultQubits);
        within{
            ApplyXorInPlace(dividend, xs);
            DivideI(xs, ys, result);
            ApplyToEachA(X, xs!);
        }
        apply{
            Controlled X(xs!, target);
        }
    }

    operation PrepareUniformSuperpositionOverDigits(digitReg : Qubit[]) : Unit is Adj + Ctl {
        PrepareArbitraryStateCP(ConstantArray(10, ComplexPolar(1.0, 0.0)), LittleEndian(digitReg));
    }

    operation ApplyMarkingOracleAsPhaseOracle(
        markingOracle : (Qubit[], Qubit) => Unit is Adj,
        register : Qubit[]
    ) : Unit is Adj {
        use target = Qubit();
        within {
            X(target);
            H(target);
        } apply {
            markingOracle(register, target);
        }
    }

    operation RunGroversSearch(register : Qubit[], phaseOracle : ((Qubit[]) => Unit is Adj), iterations : Int) : Unit {
        ApplyToEach(H, register);
        for _ in 1 .. iterations {
            phaseOracle(register);
            ReflectAboutUniform(register);
        }
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            ApplyToEachA(H, inputQubits);
            ApplyToEachA(X, inputQubits);
        } apply {
            Controlled Z(Most(inputQubits), Tail(inputQubits));
        }
    }
}

Importante

Para poder usar operaciones de la biblioteca de valores numéricos (o cualquier otra biblioteca además de la biblioteca estándar), debe asegurarse de que se ha agregado al proyecto el paquete correspondiente. Para ver una manera rápida de hacerlo en VS Code, abra el terminal desde el proyecto y ejecute el siguiente comando: dotnet add package Microsoft.Quantum.Numerics

Ejecución con Visual Studio2019 o Visual Studio Code

El programa anterior ejecutará la operación o función marcada con el atributo @EntryPoint() en un simulador o una calculadora de recursos, en función de la configuración del proyecto y de las opciones de línea de comandos.

En general, ejecutar un programa de Q# en Visual Studio es tan sencillo como pulsar Ctrl + F5. Pero en primer lugar, hay que proporcionar los argumentos de la línea de comandos adecuados a nuestro programa.

Los argumentos de la línea de comandos se pueden configurar mediante la página de depuración de las propiedades del proyecto. Puede consultar la guía Página Depuración, Diseñador de proyectos para más información al respecto, o bien siga estos pasos:

  1. En el explorador de soluciones de la derecha, haga clic con el botón derecho en el nombre del proyecto (el nodo del proyecto, un nivel por debajo de la solución) y seleccione Propiedades.

  2. En la nueva ventana que se abre, vaya a la pestaña Depurar.

  3. En el campo Argumentos de la aplicación, puede especificar los argumentos que quiere pasar al punto de entrada del programa. Escriba --number 21 en el campo de argumentos.

Ahora, pulse Ctrl + F5 para ejecutar el programa.

Con cualquiera de los entornos, ahora debería ver el siguiente mensaje en el terminal:

The number 7 is a factor of 21.

Extra: comprobación de las estadísticas con Python

¿Cómo puede comprobar que el algoritmo se comporta correctamente? Por ejemplo, si reemplazamos la búsqueda de Grover por un generador de números aleatorios en el código anterior, después de ~$N$ intentos, también encontrará un factor.

Vamos a escribir un pequeño script de Python para comprobar que el programa funciona como debería.

Sugerencia

Si necesita ayuda para ejecutar aplicaciones de Q# en Python, puede echar un vistazo a nuestra guía sobre cómo ejecutar un programa de Q# y la guía de instalación de Python.

En primer lugar, modifique la operación principal para deshacernos del bucle "repetir hasta el obtener el resultado correcto" y, en su lugar, generar el primer resultado de la medida después de ejecutar la búsqueda de Grover:

@EntryPoint()
operation FactorizeWithGrovers2(number : Int) : Int {

    let markingOracle = MarkDivisor(number, _, _);
    let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
    let size = BitSizeI(number);
    let nSolutions = 4;
    let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

    use register = Qubit[size] {
        RunGroversSearch(register, phaseOracle, nIterations);
        let res = MultiM(register);
        return ResultArrayAsInt(res);
        // Check whether the result is correct.
    }

}

Tenga en cuenta que el tipo de salida ha cambiado de Unit a Int, esto será útil para el programa de Python. El programa de Python es muy simple: tan solo llama a la operación FactorizeWithGrovers2 varias veces y traza los resultados en un histograma.

El código es el siguiente:

import qsharp
qsharp.packages.add("Microsoft.Quantum.Numerics")
qsharp.reload()
from GroversTutorial import FactorizeWithGrovers2
import matplotlib.pyplot as plt
import numpy as np

def main():

    # Instantiate variables
    frequency =  {}
    N_Experiments = 1000
    results = []
    number = 21

    # Run N_Experiments times the Q# operation.
    for i in range(N_Experiments):
        print(f'Experiment: {i} of {N_Experiments}')
        results.append(FactorizeWithGrovers2.simulate(number = number))

    # Store the results in a dictionary
    for i in results:
        if i in frequency:c
            frequency[i]=frequency[i]+1
        else:
            frequency[i]=1

    # Sort and print the results
    frequency = dict(reversed(sorted(frequency.items(), key=lambda item: item[1])))
    print('Output,  Frequency' )
    for k, v in frequency.items():
        print(f'{k:<8} {v}')

    # Plot an histogram with the results
    plt.bar(frequency.keys(), frequency.values())
    plt.xlabel("Output")
    plt.ylabel("Frequency of the outputs")
    plt.title("Outputs for Grover's factoring. N=21, 1000 iterations")
    plt.xticks(np.arange(1, 33, 2.0))
    plt.show()

if __name__ == "__main__":
    main()

Nota

La línea from GroversTutorial import FactorizeWithGrovers2 del programa de Python importa el código de Q# que hemos escrito anteriormente. Tenga en cuenta que el nombre del módulo de Python (GroversTutorial) debe ser idéntico al espacio de nombres de la operación que queremos importar (en este caso, FactorizeWithGrovers2).

El programa genera el siguiente histograma:

Histograma con los resultados de la ejecución repetida del algoritmo de Grover

Como puede ver en el histograma, el algoritmo genera las soluciones al problema de búsqueda (1, 3, 7 y 21) con una probabilidad mucho mayor que las no soluciones. Puede pensar en el algoritmo de Grover como un generador aleatorio cuántico que se sesga a propósito hacia los índices que son soluciones al problema de búsqueda.

Pasos siguientes

Ahora que sabe cómo implementar el algoritmo de Grover, intente transformar un problema matemático en una tarea de búsqueda y resolverlo con Q# y el algoritmo de Grover.