Rychlý start: Implementace Groverova vyhledávacího algoritmu v jazyku Q#Quickstart: Implement Grover's search algorithm in Q#

V tomto rychlém startu se dozvíte, jak zkompilovat a spustit Groverovo hledání a urychlit hledání nestrukturovaných dat.In this Quickstart, you can learn how to build and run Grover search to speed up the search of unstructured data. Groverovo hledání je jedním z nejoblíbenějších kvantových výpočetních algoritmů a tato poměrně malá implementace v jazyce Q# poskytuje představu o některých výhodách programování kvantových řešení pomocí kvantového programovacího jazyka Q# vysoké úrovně při vyjádření kvantových algoritmů.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. Na konci průvodce se zobrazí výstup simulace, který ukazuje úspěšné vyhledání konkrétního řetězce v seznamu neuspořádaných položek za zlomek času, než by trvalo prohledání celého seznamu v klasickém počítači.At the end of the guide, you will see the simulation output demonstrates successfully finding a specific string among a list of onordered entries in a fraction of the time it would take to search the whole list on a classical computer.

Groverův algoritmus hledá konkrétní položky v seznamu nestrukturovaných dat.Grover's algorithm searches a list of unstructured data for specific items. Může například odpovědět na otázku: Je tato karta vytažená z balíčku karet srdcové eso?For example, it can answer the question: Is this card drawn from a pack of cards an ace of hearts? Popisek konkrétní položky se nazývá označený vstup.The labeling of the specific item is called marked input.

S použitím Groverova vyhledávacího algoritmu je zaručeno, že kvantový počítač toto hledání spustí v méně krocích, než je počet položek seznamu, ve kterém hledáte – něco, co žádný klasický algoritmus nedokáže.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. Zvýšení rychlosti je v případě balíčku karet zanedbatelné; u seznamů obsahujících milióny nebo miliardy položek je však značné.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.

Groverův vyhledávací algoritmus je možné sestavit s pouhými několika řádky kódu.You can build Grover's search algorithm with just a few lines of code.

PožadavkyPrerequisites

Co Groverův vyhledávací algoritmus dělá?What does Grover's search algorithm do?

Groverův algoritmus se ptá, jestli je určitá položka v seznamu tou, kterou hledáme.Grover's algorithm asks whether an item in a list is the one we are searching for. Dosáhne toho sestrojením kvantové superpozice indexů seznamu s každým koeficientem (amplitudou pravděpodobnosti), který představuje pravděpodobnost toho, že daný index je hledaným indexem.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.

Jádrem algoritmu jsou dva kroky, které postupně zvyšují koeficient indexu, který hledáme, dokud se amplituda pravděpodobnosti tohoto koeficientu nepřiblíží k hodnotě 1.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.

Počet postupných zvýšení je menší než počet položek v seznamu.The number of incremental boosts is fewer than the number of items in the list. Proto Groverův algoritmus provádí hledání v méně krocích než jakýkoli klasický algoritmus.This is why Grover's search algorithm performs the search in fewer steps than any classical algorithm.

Funkční schéma Groverova vyhledávacího algoritmu

Psaní kóduWrite the code

  1. S použitím sady Quantum Development Kit vytvořte nový projekt v jazyku Q# s názvem Grover ve vývojovém prostředí podle vašeho výběru.Using the Quantum Development Kit, create a new Q# project called Grover, in your development environment of choice.

  2. Do souboru Operations.qs v projektu přidejte tento kód:Add the following code to the Operations.qs file in your new project:

    // Copyright (c) Microsoft Corporation. All rights reserved.
    // Licensed under the MIT License.
    
    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.
        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. Definujte seznam, ve kterém hledáme, tak, že vytvoříte nový soubor Reflections.qs a vložíte do něj tento kód:To define the list that we're searching, create a new file Reflections.qs, and paste in the following code:

    // Copyright (c) Microsoft Corporation. All rights reserved.
    // Licensed under the MIT License.
    
    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);
        }
    
    }
    

    Operace ReflectAboutMarked definuje označený vstup, který hledáte: řetězec střídajících se nul a jedniček.The ReflectAboutMarked operation defines the marked input that you are searching for: the string of alternating zeros and ones. V tomto příkladu je zadán pevný označený vstup. Je možné rozšířit ho a hledat jiné vstupy nebo obecně jakýkoli vstup.This sample hard-codes the marked input, and can be extended to search for different inputs or generalized for any input.

  4. Dále spusťte nový program v jazyku Q# a vyhledejte položku označenou operací ReflectAboutMarked.Next, run your new Q# program to find the item marked by ReflectAboutMarked.

    Pokud chcete nový program v jazyku Q# spustit z Pythonu, uložte jako soubor host.py tento kód:To run your new Q# program from Python, save the following code as host.py:

    ## Copyright (c) Microsoft Corporation. All rights reserved.
    ## Licensed under the MIT License.
    
    # This Python script calls the ApplyGrover Q# operation
    # defined in the SimpleGrover.qs file.
    
    # For instructions on how to install the qsharp package,
    # see: https://docs.microsoft.com/quantum/install-guide/python
    import qsharp
    from Microsoft.Quantum.Samples.SimpleGrover import SearchForMarkedInput
    
    n_qubits = 5
    result = SearchForMarkedInput.simulate(nQubits=n_qubits)
    print(result)
    

    Pak můžete hostitelský program Pythonu spustit z příkazového řádku:You can then run your Python host program from the command line:

    $ python host.py
    Preparing Q# environment...
    Reflecting about marked state...
    Reflecting about marked state...
    Reflecting about marked state...
    Reflecting about marked state...
    [0, 1, 0, 1, 0]
    

    Operace ReflectAboutMarked se volá jen čtyřikrát, program v jazyku Q# však našel vstup „01010“ mezi $2^{5} = 32$ možnými vstupy!The ReflectAboutMarked operation is called only four times, but your Q# program was able to find the "01010" input amongst $2^{5} = 32$ possible inputs!

Další krokyNext steps

Pokud se vám tento rychlý start líbil, podívejte se na některé prostředky níže, ze kterých se dozvíte víc o tom, jak můžete v jazyku Q# psát vlastní kvantové aplikace:If you enjoyed this quickstart, check out some of the resources below to learn more about how you can use Q# to write your own quantum applications: