Tutorial: implementar o algoritmo de pesquisa de Grover em Q#Tutorial: Implement Grover's search algorithm in Q#

Neste tutorial, pode aprender a compilar e executar a pesquisa de Grover para acelerar a pesquisa de dados não estruturados.In this tutorial, you can learn how to build and run Grover search to speed up the search of unstructured data. A pesquisa de Grover é um dos algoritmos de computação quântica mais populares, e esta implementação relativamente pequena Q# dá-lhe uma sensação de algumas das vantagens de programar soluções quânticas com uma linguagem de programação quântica de alto nível Q# para expressar algoritmos quânticos.Grover's search is one of the most popular quantum computing algorithms, and this relatively small Q# implementation gives you a sense of some of the advantages of programming quantum solutions with a high-level Q# quantum programming language to express quantum algorithms. No final do guia, verá o resultado da simulação que demonstra como encontrar com êxito uma cadeia específica numa lista de entradas desordenadas numa fração do tempo que levaria a pesquisar toda a lista num computador clássico.At the end of the guide, you will see the simulation output demonstrates successfully finding a specific string among a list of unordered entries in a fraction of the time it would take to search the whole list on a classical computer.

O algoritmo de Grover procura itens específicos numa lista de dados não estruturados.Grover's algorithm searches a list of unstructured data for specific items. Por exemplo, pode responder à pergunta: Esta carta tirada de um baralho de cartas é um ás de copas?For example, it can answer the question: Is this card drawn from a pack of cards an ace of hearts? A identificação do item específico é chamada entrada marcada.The labeling of the specific item is called marked input.

Com o algoritmo de pesquisa de Grover, é garantido que um computador quântico executa esta pesquisa em menos passos do que o número de itens contidos na lista onde está a efetuar a pesquisa — algo que nenhum algoritmo clássico consegue fazer.Using Grover's search algorithm, a quantum computer is guaranteed to run this search in fewer steps than the number of items in the list that you're searching — something no classical algorithm can do. A maior velocidade no caso de um baralho de cartas é insignificante; no entanto, em listas que contenham milhões ou milhares de milhões de itens, torna-se significativa.The increased speed in the case of a pack of cards is negligible; however, in lists containing millions or billions of items, it becomes significant.

Pode criar o algoritmo de pesquisa de Grover com apenas algumas linhas de código.You can build Grover's search algorithm with just a few lines of code.

Pré-requisitosPrerequisites

O que é que algoritmo de pesquisa de Grover faz?What does Grover's search algorithm do?

O algoritmo de Grover pergunta se um item contido na lista é aquele de que estamos à procura.Grover's algorithm asks whether an item in a list is the one we are searching for. O algoritmo faz isto ao construir uma sobreposição quântica dos índices da lista com cada coeficiente ou amplitude de probabilidade, de forma a representar a probabilidade desse índice específico ser aquele de que está à procura.It does this by constructing a quantum superposition of the indexes of the list with each coefficient, or probability amplitude, representing the probability of that specific index being the one you are looking for.

No centro do algoritmo existem dois passos que aumentam incrementalmente o coeficiente do índice de que estamos à procura, até que a amplitude de probabilidade desse coeficiente se aproxime de um.At the heart of the algorithm are two steps that incrementally boost the coefficient of the index that we are looking for, until the probability amplitude of that coefficient approaches one.

O número de aumentos incrementais é inferior ao número de itens contidos na lista.The number of incremental boosts is fewer than the number of items in the list. É por isso que o algoritmo de pesquisa de Grover executa a pesquisa em menos passos do que qualquer algoritmo clássico.This is why Grover's search algorithm performs the search in fewer steps than any classical algorithm.

Diagrama funcional do algoritmo de pesquisa de Grover

Escrever o códigoWrite the code

  1. Utilizando o Kit de Desenvolvimento Quântico, crie um novo projeto para a Q# aplicação.Using the Quantum Development Kit, create a new Q# project for the application. Dê um título ao projeto Grover.Title the project Grover.

  2. Adicione o seguinte código ao ficheiro Program.qs no novo projeto:Add the following code to the Program.qs file in your new project:

    namespace Microsoft.Quantum.Samples.SimpleGrover {
        open Microsoft.Quantum.Convert;
        open Microsoft.Quantum.Math;
        open Microsoft.Quantum.Arrays;
        open Microsoft.Quantum.Measurement;
    
        /// # Summary
        /// This operation applies Grover's algorithm to search all possible inputs
        /// to an operation to find a particular marked state.
        @EntryPoint()
        operation SearchForMarkedInput(nQubits : Int) : Result[] {
            using (qubits = Qubit[nQubits]) {
                // Initialize a uniform superposition over all possible inputs.
                PrepareUniform(qubits);
                // The search itself consists of repeatedly reflecting about the
                // marked state and our start state, which we can write out in Q#
                // as a for loop.
                for (idxIteration in 0..NIterations(nQubits) - 1) {
                    ReflectAboutMarked(qubits);
                    ReflectAboutUniform(qubits);
                }
                // Measure and return the answer.
                return ForEach(MResetZ, qubits);
            }
        }
    
        /// # Summary
        /// Returns the number of Grover iterations needed to find a single marked
        /// item, given the number of qubits in a register.
        function NIterations(nQubits : Int) : Int {
            let nItems = 1 <<< nQubits; // 2^numQubits
            // compute number of iterations:
            let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
            let nIterations = Round(0.25 * PI() / angle - 0.5);
            return nIterations;
        }
    
    }
    
  3. Para definir a lista que estamos a pesquisar, crie um novo ficheiro Reflections.qs e cole no seguinte código:To define the list that we're searching, create a new file Reflections.qs, and paste in the following code:

    namespace Microsoft.Quantum.Samples.SimpleGrover {
        open Microsoft.Quantum.Intrinsic;
        open Microsoft.Quantum.Convert;
        open Microsoft.Quantum.Math;
        open Microsoft.Quantum.Canon;
        open Microsoft.Quantum.Arrays;
        open Microsoft.Quantum.Measurement;
    
        /// # Summary
        /// Reflects about the basis state marked by alternating zeros and ones.
        /// This operation defines what input we are trying to find in the main
        /// search.
        operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
            Message("Reflecting about marked state...");
            using (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 instruction on every other qubit.
                    ApplyToEachA(X, inputQubits[...2...]);
                } apply {
                    Controlled X(inputQubits, outputQubit);
                }
            }
        }
    
        /// # Summary
        /// Reflects about the uniform superposition state.
        operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
            within {
                // Transform the uniform superposition to all-zero.
                Adjoint PrepareUniform(inputQubits);
                // Transform the all-zero state to all-ones
                PrepareAllOnes(inputQubits);
            } 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);
            }
        }
    
        /// # Summary
        /// Reflects about the all-ones state.
        operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
            Controlled Z(Most(inputQubits), Tail(inputQubits));
        }
    
        /// # Summary
        /// Given a register in the all-zeros state, prepares a uniform
        /// superposition over all basis states.
        operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
            ApplyToEachCA(H, inputQubits);
        }
    
        /// # Summary
        /// Given a register in the all-zeros state, prepares an all-ones state
        /// by flipping every qubit.
        operation PrepareAllOnes(inputQubits : Qubit[]) : Unit is Adj + Ctl {
            ApplyToEachCA(X, inputQubits);
        }
    
    }
    

    A operação ReflectAboutMarked define a entrada marcada que está a pesquisar: a cadeia de zeros e uns alternados.The ReflectAboutMarked operation defines the marked input that you are searching for: the string of alternating zeros and ones. Esta amostra codifica a entrada marcada e pode ser expandida para pesquisar entradas diferentes ou generalizadas para qualquer entrada.This sample hard-codes the marked input, and can be extended to search for different inputs or generalized for any input.

  4. Em seguida, execute o seu novo Q# programa para encontrar o item marcado por ReflectAboutMarked .Next, run your new Q# program to find the item marked by ReflectAboutMarked.

Q# aplicações com Visual Studio ou Visual Studio CodeQ# applications with Visual Studio or Visual Studio Code

O programa executará a operação ou função marcada com o @EntryPoint() atributo num simulador ou estimador de recursos, dependendo da configuração do projeto e das opções de linha de comando.The program will run the operation or function marked with the @EntryPoint() attribute on a simulator or resource estimator, depending on the project configuration and command-line options.

No Visual Studio, basta premir Ctrl + F5 para executar o script.In Visual Studio, simply press Ctrl + F5 to run the script.

No VS Code, crie o ficheiro Program.qs pela primeira vez ao escrever o seguinte no terminal:In VS Code, build the Program.qs the first time by typing the below in the terminal:

dotnet build

Para as execuções subsequentes, não há necessidade de o criar novamente.For subsequent runs, there is no need to build it again. Para o executar, escreva o seguinte comando e prima Enter:To run it, type the following command and press enter:

dotnet run --no-build

Deverá ser apresentada a seguinte mensagem no terminal:You should see the following message displayed in the terminal:

operations.qs:
This operation applies Grover's algorithm to search all possible inputs to an operation to find a particular marked state.
Usage:
operations.qs [options] [command]

--n-qubits <n-qubits> (REQUIRED)
-s, --simulator <simulator>         The name of the simulator to use.
--version                           Show version information
-?, -h, --help                      Show help and usage information
Commands:

Isto porque não especificou o número de qubits que queria utilizar, pelo que o terminal mostra-lhe os comandos disponíveis para o programa executável.This is because you didn't specify the number of qubits you wanted to use, so the terminal shows you the commands available for the executable program. Se quisermos usar 5 qubits, devemos escrever:If we want to use 5 qubits, we should type:

dotnet run --n-qubits 5

Deverá ver o resultado seguinte quando premir Enter:Pressing enter you should see the following output:

Reflecting about marked state...
Reflecting about marked state...
Reflecting about marked state...
Reflecting about marked state...
[Zero,One,Zero,One,Zero]

Passos seguintesNext steps

Se gostou deste tutorial, confira alguns dos recursos abaixo para saber mais sobre como pode usar Q# para escrever as suas próprias aplicações quânticas:If you enjoyed this tutorial, check out some of the resources below to learn more about how you can use Q# to write your own quantum applications: