快速入门:在 Q# 中实现 Grover 搜索算法Quickstart: Implement Grover's search algorithm in Q#

本快速入门介绍如何构建并运行 Grover 搜索,以便加快非结构化数据的搜索速度。In this Quickstart, you can learn how to build and run Grover search to speed up the search of unstructured data. Grover 搜索是最常用量子计算算法之一。这个相对较小的 Q# 实现可以让你感受一下使用高级 Q# 量子编程语言进行量子解决方案编程(用于表达量子算法)的部分优势。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. 在指南末尾,我们会看到模拟输出。该输出表明我们已经在未排序条目的列表中成功找到一个特定的字符串,所花时间远远少于在经典计算机上搜索整个列表所花的时间。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 算法在非结构化数据列表中搜索特定项。Grover's algorithm searches a list of unstructured data for specific items. 例如,它可以回答如下问题:从一副纸牌中抽出的这张纸牌是红桃 A 吗?For example, it can answer the question: Is this card drawn from a pack of cards an ace of hearts? 特定项的标签称为“标记输入” 。The labeling of the specific item is called marked input.

使用 Grover 搜索算法,可以保证量子计算机运行此搜索的步数少于所搜索列表中的项目数,这是经典算法无法做到的。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. 当从一副纸牌中抽一张纸牌时,提高的速度可以忽略不计,但在包含数百万或数十亿个项的列表中,这种效果是显而易见的。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 搜索算法。You can build Grover's search algorithm with just a few lines of code.

先决条件Prerequisites

Grover 搜索算法有什么作用?What does Grover's search algorithm do?

Grover 算法会询问列表中的某一项是否是我门正在搜索的项。Grover's algorithm asks whether an item in a list is the one we are searching for. 其实现方法是,通过每个系数(即概率幅度,表示该特定索引恰好是你所搜索索引的可能性)来构造列表索引的量子叠加。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.

该算法的核心是两个步骤,逐渐增加所搜索索引的系数,直到该系数的概率幅度接近 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.

增加的增量值应少于列表中的项数。The number of incremental boosts is fewer than the number of items in the list. 这就是 Grover 搜索算法执行搜索的步骤少于任何经典算法的原因。This is why Grover's search algorithm performs the search in fewer steps than any classical algorithm.

Grover 搜索算法的功能示意图

编写代码Write the code

  1. 使用 Quantum 开发工具包在你选择的开发坏境中创建一个新的 Q# 项目,并将其命名为 GroverUsing the Quantum Development Kit, create a new Q# project called Grover, in your development environment of choice.

  2. 在新项目中,将以下代码添加到 Operations.qs 文件中:Add the following code to the Operations.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.
        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. 要定义搜索列表,请创建一个新文件 Reflections.qs,并粘贴以下代码: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 运算定义要搜索的标记输入:0 和 1 交替的字符串。The ReflectAboutMarked operation defines the marked input that you are searching for: the string of alternating zeros and ones. 此示例对标记输入进行硬编码,并且可以扩展为搜索不同的输入或针对任何输入进行通用化。This sample hard-codes the marked input, and can be extended to search for different inputs or generalized for any input.

  4. 接下来,运行你的新 Q# 程序,以查找 ReflectAboutMarked 标记的项。Next, run your new Q# program to find the item marked by ReflectAboutMarked.

    要从 Python 运行你的新 Q# 程序,请将以下代码另存为 host.pyTo run your new Q# program from Python, save the following code as host.py:

    import qsharp
    from Microsoft.Quantum.Samples.SimpleGrover import SearchForMarkedInput
    
    n_qubits = 5
    result = SearchForMarkedInput.simulate(nQubits=n_qubits)
    print(result)
    

    然后便可以从命令行运行 Python 主机程序: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]
    

    ReflectAboutMarked 运算仅调用四次,但是 Q# 程序能够在 $2^{5} = 32$ 个可能的输入中找到“01010”输入!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!

后续步骤Next steps

如果喜欢本快速入门指南,请查看以下部分资源,详细了解有关使用 Q# 编写自己的量子应用程序: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: