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

Artigo
01/13/2024

Observação

O Microsoft Quantum Development Kit (QDK clássico) não terá mais suporte após 30 de junho de 2024. Se você for um desenvolvedor de QDK existente, recomendamos fazer a transição para o novo QDK (QDK Moderno) do Azure Quantum Development Kit para continuar desenvolvendo soluções quânticas. Para obter mais informações, consulte Migrar seu Q# código para o QDK moderno.

Neste tutorial, você implementa o algoritmo de Grover no para resolver problemas baseados em Q# pesquisa. Para obter uma explicação detalhada da teoria por trás do algoritmo do Grover, consulte a Teoria do algoritmo do Grover.

Neste tutorial, você aprenderá a:

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

Dica

Se você quiser acelerar sua jornada de computação quântica, marcar Código com o Azure Quantum, um recurso exclusivo do site do Azure Quantum. Aqui, você pode executar exemplos internos Q# ou seus próprios Q# programas, gerar um novo Q# código de seus prompts, abrir e executar seu código no VS Code para a Web com um clique e fazer perguntas ao Copilot sobre computação quântica.

Pré-requisitos

Para executar o exemplo de código no Copilot no Azure Quantum:
- Uma conta de email da Microsoft (MSA).
Para desenvolver e executar o exemplo de código em Visual Studio Code:
- A versão mais recente do Visual Studio Code ou abrir o VS Code na Web.
- A versão mais recente da extensão do Azure Quantum Development Kit . Para obter detalhes de instalação, consulte Instalando 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 ele resolve geralmente é chamado de "pesquisa de um banco de dados", mas é mais preciso pensar nele em termos do problema de pesquisa.

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

Assim, você 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, encontre uma entrada $x_0$ para a qual $f(x_0)=1$.

Para implementar o algoritmo de Grover para resolver um problema de pesquisa, você precisa:

Transforme o problema na forma de uma tarefa de Grover. Por exemplo, suponha que você queira encontrar os fatores de um inteiro $M$ usando o algoritmo de Grover. Você pode transformar o problema de fatoração de inteiro em uma tarefa de Grover criando 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$ é o resto de $M/x$. Dessa forma, os inteiros $x_i$ que compõem $f_M(x_i)=1$ são os fatores de $M$, e você trasformou o problema na tarefa de Grover.
Implemente a função da tarefa do Grover como um oráculo de quantum. Para implementar o algoritmo de Grover, você precisa implementar a função $f(x)$ da tarefa de Grover como um oráculo de quantum.
Use o algoritmo do Grover com seu oráculo para resolver a tarefa. Quando você tiver um oráculo quântico, poderá conectá-lo à implementação do algoritmo de Grover para resolver o problema e interpretar a saída.

O algoritmo de Grover

Suponha que há $N=2^n$ itens qualificados para o problema de pesquisa, e eles são indexados atribuindo a cada item um inteiro de $0$ a $N-1$. As etapas do algoritmo são:

Comece com um registro de $n$ qubits inicializados no estado $\ket{0}$.
Prepare o registro em uma sobreposição uniforme aplicando $H$ a cada qubit no registro: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
Aplique as seguintes operações ao registro $N_{\Text{optimal}}$ vezes:
1. A fase $O_f$ do oráculo que aplica uma mudança de fase condicional de $-1$ para os itens da solução.
2. Aplique $H$ a cada qubit no registro.
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 registro.
Meça o registro para obter o índice de um item que é uma solução com uma probabilidade muito alta.
Verifique o item para ver se é uma solução válida. Caso contrário, comece novamente.

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

Esta seção discute como implementar o algoritmo no Q#. Há poucas coisas a considerar ao implementar o algoritmo de Grover. Você precisa definir qual é o seu estado marcado, como refletir sobre ele e para quantas iterações executar o algoritmo. Você também precisa definir o oráculo que implementa a função da tarefa do Grover.

Definir o estado marcado

Primeiro, defina qual entrada você está tentando encontrar na pesquisa. Para fazer isso, escreva uma operação que aplique as etapas b, c e d do algoritmo de Grover.

Juntas, essas etapas também são conhecidas como o 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 uns alternados. Ele faz isso aplicando o operador de difusão de Grover aos qubits de entrada. A operação usa um qubit auxiliar, outputQubit, que é inicializado no estado $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ aplicando os portões $X$ e $H$. Em seguida, a operação aplica o portão $X$ a cada outro qubit no registro, o que inverte o estado do qubit. Por fim, ele aplica o portão $X$ controlado ao qubit auxiliar e aos qubits de entrada. Essa operação inverte o qubit auxiliar se e somente 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 geram a maior probabilidade de medir uma saída válida. Se o nosso problema tiver $N=2^n$ itens elegíveis possíveis e $M$ deles forem soluções para o problema, o número ideal de iterações será:

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

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

Em aplicações práticas, você geralmente não sabe quantas soluções seu problema tem antes de resolvê-lo. Uma estratégia eficiente para lidar com esse problema é "adivinhar" o número de soluções $M$ aumentando progressivamente a estimativa nas potências de dois (ou seja, $1, 2, 4, 8, 16,..., 2^n$). Um desses palpites será suficientemente próximo, pois o algoritmo ainda encontrará a solução com um número médio de iterações em cerca de $\sqrt{\frac{N}{M}}$.

A função a seguir Q# calcula o número ideal de iterações para um determinado número de qubits em um 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;
}

A CalculateOptimalIterations função usa a fórmula acima para calcular o número de iterações e, em seguida, arredonda-a para o 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 registro qubit. Esse registro codificará a solução provisória para o problema de pesquisa. Após a operação, ela será medida.
O número de iterações ideais, iterations : Int.
Uma operação, phaseOracle : Qubit[] => Unit) : Result[], que representa o oráculo de fase para a tarefa do Grover. Esta operação aplica uma transformação unitária em um registro 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 registro de qubits $n$ no estado $\ket{0}$, prepara o registro em uma superposição uniforme e 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 inicial, que você pode escrever Q# como um loop for. Por fim, ele mede o registro e retorna o resultado.

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

Dado um registro no estado de todos os zeros, a PrepareUniform operação prepara uma superposiçã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 de todos os usuários.

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

A operação ReflectAboutUniform reflete sobre o estado de superposição uniforme. Primeiro, transforma a superposição uniforme em zero. Em seguida, ele transforma o estado de todos os zeros em todos os itens. Por fim, ele reflete sobre o estado de todos os itens. A operação é chamada ReflectAboutUniform porque pode ser interpretada de modo geométrico 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 você tem todos os ingredientes para implementar uma determinada instância do algoritmo de pesquisa de Grover e resolver o problema de fatoração. Para concluir, a Main operação configura o problema especificando 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;
}

Você pode testar seu Q# código com o Copilot no Azure Quantum gratuitamente – tudo o que você precisa é de uma conta de email da Microsoft (MSA). Para obter mais informações sobre o Copilot no Azure Quantum, consulte Explorar o Azure Quantum.

Abra o Copilot no Azure Quantum em seu navegador.

Copie e cole o código a seguir 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

No Copilot no Azure Quantum, você pode abrir seu programa no VS Code para a Web clicando no botão do logotipo do VS Code no canto direito do editor de código.

Executar o programa usando o simulador na memória

Selecione Simulador na memória.
Selecione o número de capturas a serem executadas e clique em Executar.
Os resultados são exibidos no histograma e nos campos Resultados .
Clique em Explicar código para solicitar que o Copilot explique o código para você.

Executar o programa usando o Emulador Quantinuum H-Series

Você também pode enviar seu programa para o Emulador gratuito do Quantinuum H-Series. O emulador simula um computador quântico com 20 qubits.

Selecione a lista suspensa Simulador na Memória e selecione Emulador da Série H do Quantinuum.
Selecione o número de capturas (atualmente limitado a 20) e selecione Executar.

Abra Visual Studio Code e selecione Arquivo > Novo Arquivo de Texto para criar um novo arquivo.
Salve o arquivo como GroversAlgorithm.qs. Esse arquivo conterá o código do Q# programa.

Copie o código a seguir no GroversAlgorithm.qs arquivo.

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, você precisa definir o target perfil como Irrestrito. Selecione Exibir –> Paleta de Comandos, pesquise QIR, selecioneQ# : Defina o perfil qir target do Azure Quantum e selecione Q#: irrestrito.
Para executar o programa, clique em Executar na lista de comandos abaixo @EntryPoint()ou pressione Ctrl+F5. O programa executa a operação ou função marcada com o @EntryPoint() atributo no simulador padrão.
A saída será exibida no console de depuração.