Öğretici: Q# dilinde Grover arama algoritmasını uygulamaTutorial: Implement Grover's search algorithm in Q#

Bu öğreticide, yapılandırılmamış veri aramasını hızlandırmak için Grover araması oluşturmayı ve çalıştırmayı öğrenebilirsiniz.In this tutorial, you can learn how to build and run Grover search to speed up the search of unstructured data. Grover araması en popüler kuantum bilişimi algoritmalarından biridir ve görece küçük olan bu Q# uygulaması, kuantum algoritmalarını ifade etmek için üst düzey Q# kuantum programlama dili ile kuantum çözümü programlamanın avantajlarını sunar.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. Kılavuzun sonunda, klasik bir bilgisayara kıyasla çok daha kısa sürede, sıralı olmayan girişlerden oluşan bir listede belirli bir dizeyi başarıyla bulma sonucunu gösteren simülasyon çıktısını göreceksiniz.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.

Grover algoritması belirli öğeleri bulmak için yapılandırılmamış bir veri listesinde arama yapar.Grover's algorithm searches a list of unstructured data for specific items. Örneğin şu soruyu yanıtlayabilir: Bir deste iskambil kağıdından çekilen bu kağıt kupa ası mı?For example, it can answer the question: Is this card drawn from a pack of cards an ace of hearts? Belirli öğenin etiketlenmesi işaretlenmiş giriş olarak adlandırılır.The labeling of the specific item is called marked input.

Grover arama algoritması kullanıldığında, kuantum bilgisayarın bu aramayı aradığınız listedeki öğelerin sayısından daha az adımda çalıştıracağı garantidir; bu klasik algoritmanın yapamayacağı bir şeydir.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. Bir deste iskambil kağıdı örneğinde hız artışı göz ardı edilebilir ama milyonlarca veya milyarlarca öğe içeren listelerde ciddi bir artış anlamına gelir.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 arama algoritmasını yalnızca birkaç kod satırıyla oluşturabilirsiniz.You can build Grover's search algorithm with just a few lines of code.

Ön koşullarPrerequisites

Grover arama algoritması ne yapar?What does Grover's search algorithm do?

Grover algoritması, listedeki bir öğenin bizim aradığımız öğe olup olmadığını sorar.Grover's algorithm asks whether an item in a list is the one we are searching for. Bunu yapmak için listenin dizinlerinin bir kuantum süper konumunu oluşturur; burada her katsayı veya olasılık genliği belirli bir dizinin aradığınız dizin olma olasılığını temsil eder.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.

Algoritmanın merkezinde aradığımız dizinin katsayısını, bu katsayının olasılık genliği bire yaklaşana kadar aşamalı olarak artıran iki adım vardır.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.

Aşamalı artışların sayısı listedeki öğelerin sayısından azdır.The number of incremental boosts is fewer than the number of items in the list. İşte bundan dolayı Grover arama algoritması aramayı klasik algoritmalardan daha az adımda gerçekleştirir.This is why Grover's search algorithm performs the search in fewer steps than any classical algorithm.

Grover arama algoritmasının işlevsel diyagramı

Kodu yazmaWrite the code

  1. Quantum Development Kit'i kullanarak tercih ettiğiniz geliştirme ortamında Grover adlı yeni bir Q# projesi oluşturun.Using the Quantum Development Kit, create a new Q# project called Grover, in your development environment of choice.

  2. Yeni projenizin Program.qs dosyasına aşağıdaki kodu ekleyin: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. Arama yaptığımız listeyi tanımlamak için yeni bir dosya (Reflections.qs) oluşturun ve aşağıdaki kodu yapıştırın: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);
        }
    
    }
    

    ReflectAboutMarked işlemi aradığınız işaretlenmiş girişi tanımlar: değişen sıfırlar ve birler dizesi.The ReflectAboutMarked operation defines the marked input that you are searching for: the string of alternating zeros and ones. Bu örnek işaretlenmiş girişin sabit kodlamasını yapar ve farklı girişleri aramak veya herhangi bir giriş için genelleştirmek üzere genişletilebilir.This sample hard-codes the marked input, and can be extended to search for different inputs or generalized for any input.

  4. Ardından ReflectAboutMarked ile işaretlenmiş öğeyi bulmak için yeni Q# programınızı çalıştırın.Next, run your new Q# program to find the item marked by ReflectAboutMarked.

Visual Studio veya Visual Studio Code ile Q# komut satırı uygulamalarıQ# command line applications with Visual Studio or Visual Studio Code

Yürütülebilir dosya, proje yapılandırmasına ve komut satırı seçeneklerine bağlı olarak simülatör veya kaynak tahmini aracında @EntryPoint() özniteliğiyle işaretlenmiş işlemi ya da işlevi çalıştırır.The executable 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.

Visual Studio’da betiği yürütmek için Ctrl + F5 tuşlarına basmanız yeterlidir.In Visual Studio, simply press Ctrl + F5 to execute the script.

VS Code’da terminale aşağıdakileri yazarak Program.qs dosyasını ilk kez derleyin:In VS Code, build the Program.qs the first time by typing the below in the terminal:

dotnet build

Sonraki çalıştırmalar için tekrar derlenmesi gerekmez.For subsequent runs, there is no need to build it again. Çalıştırmak için aşağıdaki komutu girin ve Enter tuşuna basın:To run it, type the following command and press enter:

dotnet run --no-build

Terminalde şu ileti görüntülenmelidir: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:

Bu, kullanmak istediğiniz kubit sayısını belirtmemeniz nedeniyle terminalin yürütülebilir dosya için kullanılabilir olan komutları size bildirmesinden kaynaklanır.This is because you didn't specify the number of qubits you wanted to use, so the terminal tells you the commands available for the executable. 5 kubit kullanmak istiyorsak şunu yazmamız gerekir:If we want to use 5 qubits we should type:

dotnet run --n-qubits 5

Enter tuşuna bastığınızda şu çıktıyı görmeniz gerekir: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]

Sonraki adımlarNext steps

Bu öğreticiden keyif aldıysanız, Q# kullanarak kendi kuantum uygulamalarınızı nasıl yazabileceğiniz hakkında daha fazla bilgi edinmek için aşağıdaki kaynaklardan bazılarını gözden geçirin: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: