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

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 搜索算法有什么作用？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. ## 编写代码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) {
}
// 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 {
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.
// 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.
}
}

/// # 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!