你当前正在访问 Microsoft Azure Global Edition 技术文档网站。如果需要访问由世纪互联运营的 Microsoft Azure 中国技术文档网站，请访问 https://docs.azure.cn。

教程：在 Q# 中实现 Grover 的搜索算法

项目
01/16/2025

在本教程中，你将实现 Grover 算法 Q# 来解决基于搜索的问题。有关 Grover 算法背后理论的深入说明，请参阅 Grover 算法的理论。

在本教程中，你将了解：

定义 Grover 的搜索问题的算法
在中实现 Grover 算法 Q#

提示

若要加速量子计算之旅，请查看 Azure Quantum 代码，这是 Azure Quantum 网站的独特功能。在这里，你可以运行内置Q#示例或你自己的Q#程序，通过提示生成新Q#代码，在 VS Code for the Web 中打开并运行代码，只需单击一下，并询问 Copilot 有关量子计算的任何问题。

先决条件

若要在 Azure Quantum 的 Copilot 中运行代码示例，
- Microsoft（MSA）电子邮件帐户。
若要在 Visual Studio Code 中开发和运行代码示例，请执行以下操作：
- 最新版本的 Visual Studio Code 或打开网页版 VS Code。
- 最新版本的 Azure Quantum Development Kit 扩展。有关安装方面的详细信息，请参阅设置 QDK 扩展。

定义问题

Grover 算法是量子计算中最著名的算法之一。它解决的问题类型通常称为“搜索数据库”，但从搜索问题的角度来看待它更为准确。

任何搜索问题都可以使用抽象函数 $f(x)$ 以数学方式进行表达，该函数接受搜索项 $x$。如果项 $x$ 是搜索问题的解决方案，则 $f(x)=1$。如果项 $x$ 不是解，则 $f(x)=0$。搜索问题包括查找使 $f(x_0)=1$ 的任何项 $x_0$。

因此，可以将任何搜索问题表述为：给定经典函数$f（x）：\{0,1\}^n \rightarrow\{0,1\}$，其中$n$ 是搜索空间的位大小，请查找$f（x_0）=1$ 的输入$x_0$ 。

若要实现 Grover 算法来解决搜索问题，需要：

将问题转换为 Grover 的任务的形式。例如，假设想使用 Grover 算法找到整数 $M$ 的因数。可以通过创建函数 $$f_M(x)=1[r],$$（其中如果 $r=0$，则 $1[r]=1$，并且如果 $r\neq0$ 和 $r$ 是 $M/x$ 的余数，则 $1[r]=0$）来将整数因式分解问题转换为 Grover 任务。这样，使 $f_M(x_i)=1$ 的整数 $x_i$ 是 $M$ 的因数，并且已将问题转化为 Grover 的任务。
将 Grover 的任务的函数实现为量子黑盒。要实现 Grover 算法，需要将 Grover 任务的函数 $f(x)$ 实现为量子黑盒。
使用 Grover 的算法和黑盒解决该任务。一旦拥有量子黑盒，就可以将它插入 Grover 的算法实现中来解决问题并解释输出。

Grover 算法

假设搜索问题有 $N=2^n$ 个符合条件的项目，并且通过为每个项目分配一个从 $0$ 到 $N-1$ 的整数来对它们进行索引。算法的步骤如下所示：

从以状态 $\ket{0}$ 初始化的 $n$ 个量子比特的寄存器开始。
通过对寄存器中的每个量子比特应用 $H$ 来将寄存器准备成统一的叠加：$$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
将以下操作应用于寄存器 $N_{\text{optimal}}$ 次：
1. 为求解项应用条件相移为 $-1$ 的相位黑盒 $O_f$。
2. 向寄存器中的每个量子比特应用 $H$。
3. 向除 $\ket{0}$ 之外的每个计算基础状态应用 $-O_0$ （$-1$ 的条件相移）。
4. 向寄存器中的每个量子比特应用 $H$。
度量寄存器以获取具有很高概率为解的项的索引。
检查该项是否为有效的解决方案。如果不是，则再次开始运算。

编写 Grover 算法的代码 Q#

本部分讨论如何在 Q# 中实现算法。实现 Grover 算法时，需要考虑几个事项。需要定义标记的状态、如何反映其内容以及运行算法的迭代数。还需要定义实现 Grover 任务函数的 oracle。

定义标记状态

首先，定义在搜索中尝试查找的输入。为此，请编写一个操作，该操作应用 Grover 算法中的步骤 b、c 和 d。

这些步骤也称为 Grover 的扩散运算符 $-H^{\otimes n} O_0 H^{\otimes n}$。

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use 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
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

该 ReflectAboutMarked 操作反映由交替零和 1 标记的基础状态。它通过将 Grover 的扩散运算符应用于输入量子比特来执行此操作。该操作使用辅助量子比特，outputQubit该量子比特通过应用 $X$ 和 $H$ 门，在状态 $\ket{-}=\frac{1}{\sqrt{2}}（\ket-\ket{0}{1}）$ 中初始化。然后，该操作将 $X$ 门应用于寄存器中所有其他量子位，这会翻转量子比特的状态。最后，它将受控的 $X$ 门应用于辅助量子比特和输入量子比特。如果并且仅当所有输入量子比特都处于状态 $\ket{1}$（标记为状态）时，此操作才会翻转辅助量子比特。

定义最佳迭代数

Grover 的搜索具有理想的迭代次数，可以产生测量有效输出的最大概率。如果问题有 $N=2^n$ 个可能符合条件的项，而其中 $M$ 个是问题的解，那么最佳迭代次数为：

$$N_{\text{optimal}}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}$$

继续循环访问最佳迭代次数开始减少该概率，直到在迭代 $2 N_{\text{optimal}}$上达到近零成功概率为止。之后，概率将再次增长，直至 $3 N_{\text{optimal}}$ 次迭代，以此类推。

在实际应用程序中，在解决问题之前，你通常不知道你的问题有多少种答案。解决此问题的一种高效策略是“猜测”解的数量 $M$，方法是逐步以二的次幂增加猜测的数量（即 $1、2、4、8、16、…、2^n$）。其中一项猜测将足够接近，算法仍会在接近 $\sqrt{\frac{N}{M}}$ 的平均迭代次数时找到解。

以下 Q# 函数计算寄存器中给定量子比特数的最佳迭代次数。

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

该 CalculateOptimalIterations 函数使用上面的公式计算迭代数，然后将其舍入到最接近的整数。

定义 Grover 的操作

Q# Grover 搜索算法的操作有三个输入：

量子比特寄存器中的量子比特 nQubits : Int数。此寄存器会将暂定的解编码为搜索问题。操作后，将对其进行度量。
最佳迭代数。 iterations : Int
一个操作， phaseOracle : Qubit[] => Unit) : Result[]表示 Grover 任务的阶段 oracle。此运算会对通用量子比特寄存器应用单一转换。

operation GroverSearch( nQubits : Int, iterations : Int, phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];
    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

该 GroverSearch 操作初始化状态为 $\ket{0}$ 中的 $n$ 量子比特的寄存器，将寄存器准备成统一叠加，然后将 Grover 的算法应用于指定的迭代数。搜索本身由反复反映标记状态和开始状态组成，你可以将其写 Q# 成 for 循环。最后，它会度量寄存器并返回结果。

该代码使用三个帮助程序操作： PrepareUniform、 ReflectAboutUniform和 ReflectAboutAllOnes。

给定处于全零状态的寄存器，该 PrepareUniform 操作会为所有基状态准备统一叠加。

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

“ReflectAboutAllOnes”操作反映所有状态。

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

该操作 ReflectAboutUniform 反映统一叠加状态。首先，它将统一叠加转换为全零。然后，它将全零状态转换为 all-one。最后，它反映了所有状态。该运算称为 ReflectAboutUniform，因为它可以通过几何方式解释为矢量空间中关于均匀叠加状态的反射。

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        ReflectAboutAllOnes(inputQubits);
    }
}

运行最终代码

现在，你就有了实现特定 Grover 搜索算法实例并解决分解问题的所有组成部分。若要完成，该 Main 操作通过指定量子比特数和迭代数来设置问题

operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");
    
    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
}

运行程序

选择要运行程序所需的平台。

Azure Quantum 中的 Copilot
Visual Studio Code

可以使用 Azure Quantum 中的 Copilot 免费测试 Q# 代码 - 只需Microsoft（MSA）电子邮件帐户即可。有关 Azure Quantum 中的 Copilot 的详细信息，请参阅探索 Azure Quantum。

在浏览器中打开 Azure Quantum 中的 Copilot。

将以下代码复制并粘贴到代码编辑器中。

import Microsoft.Quantum.Convert.*;
import Microsoft.Quantum.Math.*;
import Microsoft.Quantum.Arrays.*;
import Microsoft.Quantum.Measurement.*;
import Microsoft.Quantum.Diagnostics.*;

operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");

    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
}

operation GroverSearch(
    nQubits : Int,
    iterations : Int,
    phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];

    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use 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
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        // Transform the uniform superposition to all-zero.
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } 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);
    }
}

提示

在 Azure Quantum 中的 Copilot 中，可以通过选择代码编辑器右侧角的 VS Code 徽标按钮，在 VS Code for Web 中打开程序。

使用内存中模拟器运行程序

选择 内存中模拟器。
选择要运行的镜头数，然后选择“ 运行”。
结果显示在直方图和结果字段中。
选择 “解释代码 ”以提示 Copilot 向你解释代码。

使用 Quantinuum 模拟器运行程序

还可以将程序提交到免费的 Quantinuum 模拟器。仿真器模拟具有 20 个量子比特的量子计算机。

选择 In-Memory 模拟器 下拉列表，然后选择 Quantinuum Emulator。
选择快照数（当前限制为 20），然后选择“Run”。

打开 Visual Studio Code 并选择“文件”>“新建文本文件”以创建新文件。
将文件另存为 GroversAlgorithm.qs。此文件将包含 Q# 程序的代码。

将以下代码复制到 GroversAlgorithm.qs 文件中。


import Microsoft.Quantum.Convert.*;
import Microsoft.Quantum.Math.*;
import Microsoft.Quantum.Arrays.*;
import Microsoft.Quantum.Measurement.*;
import Microsoft.Quantum.Diagnostics.*;


operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");

    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
}

operation GroverSearch(
    nQubits : Int,
    iterations : Int,
    phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];

    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use 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
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        // Transform the uniform superposition to all-zero.
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } 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);
    }
}

在运行程序之前，请确保配置文件 target 设置为 “不受限制”。选择视图 >，搜索 QIR，选择，然后选择Q#target。
若要运行程序，请从操作上方的命令列表中选择“运行”，或按 Main。默认情况下，编译器 Main 在默认模拟器上运行操作或函数。
输出将显示在终端的调试控制台中。

注意

target如果配置文件未设置为“不受限制”，则运行程序时会出现错误。

浏览其他 Q# 教程：

量子纠缠演示如何编写一个 Q# 程序来操作和测量量子比特，并演示叠加和纠缠的影响。
量子随机数生成器演示如何编写一个 Q# 程序，以在叠加中从量子比特中生成随机数。
Quantum Fourier Transform 探索了如何编写 Q# 直接处理特定量子比特的程序。
Quantum Katas 是自我节奏的教程和编程练习，旨在同时教授量子计算和Q#编程的元素。

通过

教程：在 Q# 中实现 Grover 的搜索算法

先决条件

定义问题

Grover 算法

编写 Grover 算法的代码 Q#

定义标记状态

定义最佳迭代数

定义 Grover 的操作

运行最终代码

运行程序

使用内存中模拟器运行程序

使用 Quantinuum 模拟器运行程序

反馈

其他资源

通过

教程：在 Q# 中实现 Grover 的搜索算法

先决条件

定义问题

Grover 算法

编写 Grover 算法的代码 Q#

定义标记状态

定义最佳迭代数

定义 Grover 的操作

运行最终代码

运行程序

使用内存中模拟器运行程序

使用 Quantinuum 模拟器运行程序

相关内容

反馈

其他资源