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

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

Neste tutorial:

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 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 AzureQuantum Development Kit. Para obter detalhes da instalação, consulte Instalando o QDK no VS Code.

Definir o problema

O algoritmo de Grover é um dos algoritmos mais famosos da computação quântica. O tipo de problema que resolve é muitas vezes referido como "pesquisar uma base de dados", mas é mais preciso pensá-lo em termos do problema de pesquisa.

Qualquer problema de pesquisa pode ser matematicamente formulado 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, 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 encontrar qualquer item $x_0$ tal 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\}$, onde $n$ é o tamanho de 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:

1. 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 inteiros em uma tarefa de Grover criando uma função $$f_M(x)=1[r],$$ onde $1[r]=1$ se $r=0$ e $1[r]=0$ se $r\neq0$ e $r$ é o restante de $M/x$. Desta forma, os inteiros $x_i$ que fazem $f_M(x_i)=1$ são os fatores de $M$ e você transformou o problema em uma tarefa de Grover.
2. Implementar a função da tarefa do Grover como um oráculo quântico. Para implementar o algoritmo de Grover, você precisa implementar a função $f(x)$ da tarefa do seu Grover como um oráculo quântico.
3. Use o algoritmo de Grover com seu oráculo para resolver a tarefa. Depois de ter um oráculo quântico, você pode conectá-lo à implementação do algoritmo do Grover para resolver o problema e interpretar a saída.

O algoritmo do 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$. Os passos do algoritmo são:

1. Comece com um registro de $n$ qubits inicializados no estado $\ket{0}$.
2. Prepare o registro em uma superposição uniforme aplicando $H$ a cada qubit no registro: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
3. Aplique as seguintes operações ao registro $N_{\text{optimal}}$ vezes:
   1. O oráculo de fase $O_f$ que aplica um deslocamento de fase condicional de $-1$ para os itens de solução.
   2. Aplique $H$ a cada qubit no registro.
   3. Aplique $-O_0$, um deslocamento de fase condicional de $-1$ para todos os estados de base computacional, exceto $\ket{0}$.
   4. Aplique $H$ a cada qubit no registro.
4. Meça o registro para obter o índice de um item que é uma solução com probabilidade muito alta.
5. Verifique o item para ver se é uma solução válida. Se não, comece de novo.

Escreva 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 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, você define qual entrada 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 base marcado por zeros e uns alternados. Ele faz isso aplicando o operador de difusão do Grover aos qubits de entrada. A operação usa um qubit auxiliar, outputQubitque é inicializado no estado $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ aplicando as portas $X$ e $H$. A operação então aplica a porta $X$ a todos os outros qubits no registro, o que inverte o estado do qubit. Finalmente, ele aplica a porta controlada de $X$ ao qubit auxiliar e aos qubits de entrada. Esta 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 produz a maior probabilidade de medir uma saída válida. Se o problema tiver $N=2^n$ possíveis itens elegíveis, e $M$ deles 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 além do número ideal de iterações começa a reduzir essa probabilidade até atingir probabilidade de sucesso quase zero na iteração $2 N_{\text{optimal}}$. Depois disso, a probabilidade cresce novamente até $3 N_{\text{optimal}}$, e assim por diante.

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 esta questão é "adivinhar" o número de soluções $M$ aumentando progressivamente o palpite em poderes de dois (ou seja, $1, 2, 4, 8, 16, ..., 2^n$). Um desses palpites será próximo o suficiente para que o algoritmo ainda encontre a solução com um número médio de iterações em torno 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 número inteiro mais próximo.

Definir a operação do Grover

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

• O número de qubits, nQubits : Int, no registro de qubit. Este registo codificará a solução provisória para o problema de pesquisa. Após a operação, será medido.
• O número de iterações ótimas, 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 sobre um registro 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 registro de qubits de $n$ no estado $\ket{0}$, prepara o registro em uma superposiçã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 inicial, que você pode escrever como Q# um loop for. Por fim, mede o registo e devolve o resultado.

O código faz uso de três operações auxiliares: PrepareUniform, ReflectAboutUniform, e ReflectAboutAllOnes.

Dado um registo no estado de todos os zeros, a PrepareUniform operação prepara uma sobreposição uniforme sobre 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.

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, transforma o estado de todos zero em todos. Por fim, reflete sobre o estado de todos. A operação é chamada ReflectAboutUniform porque pode ser geometricamente interpretada como uma reflexão no espaço vetorial sobre o estado de superposiçã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);
    }
}

Execute o código final

Agora você tem todos os ingredientes para implementar uma instância específica do algoritmo de pesquisa de Grover e resolver o problema de factoring. 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;
}

Execute o programa

Selecione a plataforma desejada para executar seu programa.

Conteúdos relacionados

Explore outros Q# tutoriais:

• O entrelaçamento quântico mostra como escrever um Q# programa que manipula e mede qubits e demonstra os efeitos da sobreposição e do emaranhamento.
• Quantum random number generator mostra como escrever um Q# programa que gera números aleatórios a partir de qubits em superposição.
• Quantum Fourier Transform explora como escrever um Q# programa que aborda diretamente qubits específicos.
• Os Quantum Katas são tutoriais individualizados e exercícios de programação destinados a ensinar os elementos da computação quântica e Q# programação ao mesmo tempo.