Tutorial: Implementar o algoritmo de pesquisa de Grover no Q#

Artigo
04/17/2024

Nota

O Microsoft Quantum Development Kit (QDK Clássico) deixará de ser suportado após 30 de junho de 2024. Se for um programador de QDK existente, recomendamos que faça a transição para o novo Azure Quantum Development Kit (QDK Moderno) para continuar a desenvolver soluções quânticas. Para obter mais informações, veja Migrar o código Q# para o QDK Moderno.

Neste tutorial, vai implementar o algoritmo de Grover para resolver problemas baseados em Q# pesquisa. Para obter uma explicação aprofundada da teoria por trás do algoritmo de Grover, veja a Teoria do algoritmo de Grover.

Neste tutorial, irá:

Defina o algoritmo de Grover para um problema de pesquisa.
Implemente o algoritmo de Grover em Q#.

Dica

Se quiser acelerar o seu percurso de computação quântica, consulte Código com o Azure Quantum, uma funcionalidade exclusiva do site do Azure Quantum. Aqui, pode executar exemplos incorporados Q# ou os seus próprios Q# programas, gerar novo Q# código a partir das suas instruções, abrir e executar o código no VS Code para a Web com um clique e fazer perguntas sobre computação quântica ao Copilot.

Pré-requisitos

Para executar o exemplo de código no Copilot no Azure Quantum:
- Uma conta de e-mail da Microsoft (MSA).
Para desenvolver e executar o exemplo de código no Visual Studio Code:
- A versão mais recente do Visual Studio Code ou abra o VS Code na Web.
- A versão mais recente da extensão do Azure Quantum Development Kit . Para obter detalhes sobre a instalação, veja Instalar o QDK Moderno no VS Code.

Definir o problema

O algoritmo de Grover é um dos algoritmos mais famosos na computação quântica. O tipo de problema que resolve é frequentemente referido como "procurar numa base de dados", mas é mais preciso pensar no problema de pesquisa.

Qualquer problema de pesquisa pode ser formulado matematicamente com uma função abstrata $f(x)$ que aceita itens de pesquisa $x$. Se o item $x$ for uma solução para o problema de pesquisa, $f(x)=1$. Se o item $x$ não for uma solução, $f(x)=0$. O problema de pesquisa consiste em localizar qualquer item $x_0$ de modo a $f(x_0)=1$.

Assim, pode formular qualquer problema de pesquisa como: dada uma função clássica $f(x):\{0,1\}^n \rightarrow\{0,1\}$, em que $n$ é o tamanho do bit do espaço de pesquisa, localize uma entrada $x_0$ para a qual $f(x_0)=1$.

Para implementar o algoritmo de Grover para resolver um problema de pesquisa, tem de:

Transforme o problema na forma de uma tarefa de Grover. Por exemplo, suponha que pretende encontrar os fatores de um número inteiro $M$ com o algoritmo de Grover. Pode transformar o problema de fatorização de número inteiro numa tarefa de Grover ao criar uma função $$f_M(x)=1[r],$$ em que $1[r]=1$ se $r=0$ e $1[r]=0$ se $r\neq0$ e $r$ for o resto de $M/x$. Desta forma, os números inteiros $x_i$ que fazem $f_M(x_i)=1$ são os fatores de $M$ e transformou o problema numa tarefa de Grover.
Implemente a função da tarefa de Grover como um oráculo quântico. Para implementar o algoritmo de Grover, tem de implementar a função $f(x)$ da tarefa de Grover como um oráculo quântico.
Utilize o algoritmo de Grover com o oráculo para resolver a tarefa. Assim que tiver um oráculo quântico, pode ligá-lo à implementação do algoritmo de Grover para resolver o problema e interpretar o resultado.

O algoritmo de Grover

Suponha que existem itens elegíveis $N=2^n$ para o problema de pesquisa e que são indexados ao atribuir a cada item um número inteiro de $0$ a $N-1$. Os passos do algoritmo são:

Comece com um registo de qubits $n$ inicializados no estado $\ket{0}$.
Prepare o registo numa sobreposição uniforme ao aplicar $H$ a cada qubit no registo: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
Aplique as seguintes operações ao registo $N_{\text{optimal}}$ vezes:
1. A fase oracle $O_f$ que aplica uma mudança de fase condicional de $-1$ para os itens da solução.
2. Aplique $H$ a cada qubit no registo.
3. Aplique $-O_0$, uma mudança de fase condicional de $-1$ a cada estado de base computacional, exceto $\ket{0}$.
4. Aplique $H$ a cada qubit no registo.
Meça o registo para obter o índice de um item que é uma solução com uma probabilidade muito elevada.
Verifique o item para ver se é uma solução válida. Caso contrário, comece de novo.

Escrever o código para o algoritmo de Grover no Q#

Esta secção aborda como implementar o algoritmo no Q#. Existem poucos aspetos a considerar ao implementar o algoritmo de Grover. Tem de definir qual é o seu estado marcado, como refletir sobre o mesmo e quantas iterações para executar o algoritmo. Também tem de definir o oráculo que implementa a função da tarefa de Grover.

Definir o estado marcado

Primeiro, define a entrada que está a tentar encontrar na pesquisa. Para tal, escreva uma operação que aplique os passos b, c e d do algoritmo de Grover.

Em conjunto, estes passos também são conhecidos como operador de difusão 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);
    }
}

A ReflectAboutMarked operação reflete sobre o estado de base marcado por zeros e zeros alternados. Fá-lo ao aplicar o operador de difusão de Grover aos qubits de entrada. A operação utiliza um qubit auxiliar, outputQubit, que é inicializado no estado $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ ao aplicar as portas $X$ e $H$. Em seguida, a operação aplica a porta $X$ a todos os outros qubits no registo, o que inverte o estado do qubit. Por fim, aplica a porta de $X$ controlada ao qubit auxiliar e aos qubits de entrada. Esta operação inverte o qubit auxiliar se e apenas se todos os qubits de entrada estiverem no estado $\ket{1}$, que é o estado marcado.

Definir o número de iterações ideais

A pesquisa de Grover tem um número ideal de iterações que produzem a maior probabilidade de medir uma saída válida. Se o problema tiver $N=2^n$ possíveis itens elegíveis e $M$ dos mesmos forem soluções para o problema, o número ideal de iterações é:

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

Continuar a iterar para além do número ideal de iterações começa a reduzir essa probabilidade até atingir quase zero probabilidade de sucesso na iteração $2 N_{\text{optimal}}$. Depois disso, a probabilidade volta a aumentar até $3 N_{\text{optimal}}$, etc.

Em aplicações práticas, normalmente não sabe quantas soluções o problema tem antes de o solucionar. Uma estratégia eficiente para lidar com este problema é "adivinhar" o número de soluções $M$ ao aumentar progressivamente o palpite em potências de dois (ou seja, $1, 2, 4, 8, 16, ..., 2^n$). Uma destas estimativas será suficientemente próxima para que o algoritmo continue a encontrar a solução com um número médio de iterações em torno de $\sqrt{\frac{N}{M}}$.

A função seguinte Q# calcula o número ideal de iterações para um determinado número de qubits num registo.

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;
}

A CalculateOptimalIterations função utiliza a fórmula acima para calcular o número de iterações e, em seguida, arredonda-a para o número inteiro mais próximo.

Definir a operação de Grover

A Q# operação para o algoritmo de pesquisa de Grover tem três entradas:

O número de qubits, nQubits : Int, no registo qubit. Este registo codificará a solução tentativa para o problema de pesquisa. Após a operação, será medido.
O número de iterações ideais, iterations : Int.
Uma operação, phaseOracle : Qubit[] => Unit) : Result[], que representa o oráculo de fase da tarefa de Grover. Esta operação aplica uma transformação unitária através de um registo de qubit 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);
}

A GroverSearch operação inicializa um registo de qubits de $n$ no estado $\ket{0}$, prepara o registo para uma sobreposição uniforme e, em seguida, aplica o algoritmo de Grover para o número especificado de iterações. A pesquisa em si consiste em refletir repetidamente sobre o estado marcado e o estado de início, que pode escrever como Q# um ciclo. Por fim, mede o registo e devolve o resultado.

O código utiliza três operações auxiliares: PrepareUniform, ReflectAboutUniforme ReflectAboutAllOnes.

Tendo em conta um registo no estado de todos os zeros, a PrepareUniform operação prepara uma sobreposição uniforme em todos os estados de base.

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

A operação "'ReflectAboutAllOnes' reflete sobre o estado all-ones.

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

A operação ReflectAboutUniform reflete sobre o estado de sobreposição uniforme. Primeiro, transforma a sobreposição uniforme em all-zero. Em seguida, transforma o estado all-zero em all-ones. Por fim, reflete sobre o estado all-ones. A operação é chamada ReflectAboutUniform porque pode ser interpretada geometricamente como uma reflexão no espaço de vetor sobre o estado de sobreposição uniforme.

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);
    }
}

Executar o código final

Agora, tem todos os ingredientes para implementar uma instância específica do algoritmo de pesquisa de Grover e resolver o problema de fatorização. Para concluir, a Main operação configura o problema ao especificar o número de qubits e o número de iterações

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;
}

Pode testar o seu Q# código com o Copilot no Azure Quantum gratuitamente- tudo o que precisa é de uma conta de e-mail da Microsoft (MSA). Para obter mais informações sobre o Copilot no Azure Quantum, veja Explorar o Azure Quantum.

Abra o Copilot no Azure Quantum no browser.

Copie e cole o seguinte código no 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);
        }
    }
}

Dica

A partir do Copilot no Azure Quantum, pode abrir o seu programa no VS Code para a Web ao clicar no botão do logótipo do VS Code no canto direito do editor de código.

Executar o programa com o simulador dentro da memória

Selecione Simulador dentro da memória.
Selecione o número de capturas a executar e clique em Executar.
Os resultados são apresentados no histograma e nos campos Resultados .
Clique em Explicar código para pedir a Copilot para lhe explicar o código.

Executar o programa com o Emulador da Série H de Quantinuum

Também pode submeter o seu programa para o Emulador gratuito da Série H do Quantinuum. O emulador simula um computador quântico com 20 qubits.

Selecione a lista pendente Simulador dentro da Memória e selecione Quantinuum H-Series Emulator.
Selecione o número de capturas (atualmente limitado a 20) e selecione Executar.

Abra o Visual Studio Code e selecione Ficheiro > Novo Ficheiro de Texto para criar um novo ficheiro.
Guarde o ficheiro como GroversAlgorithm.qs. Este ficheiro irá conter o Q# código do seu programa.

Copie o seguinte código no GroversAlgorithm.qs ficheiro.

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 executar o programa, tem de definir o target perfil como Sem Restrições. Selecione Ver -> Paleta de Comandos, procure QIR, selecione Q#: Defina o perfil QIR target do Azure Quantum e, em seguida, selecione Q#: sem restrições.
Para executar o programa, clique em Executar a partir da lista de comandos abaixo @EntryPoint()ou prima Ctrl+F5. O programa executa a operação ou função marcada com o @EntryPoint() atributo no simulador predefinido.
O resultado será apresentado na consola de depuração.