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

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

项目
04/17/2024

注意

2024 年 6 月 30 日之后，将不再支持 Microsoft Quantum Development Kit (经典 QDK) 。如果你是现有的 QDK 开发人员，建议过渡到新的 Azure Quantum Development Kit (新式 QDK) ，以继续开发量子解决方案。有关详细信息，请参阅将 Q# 代码迁移到新式 QDK。

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

在本教程中，你将：

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

提示

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

先决条件

在 Azure Quantum 的 Copilot 中运行代码示例：
- Microsoft (MSA) 电子邮件帐户。
在 Visual Studio Code 中开发和运行代码示例：
- 最新版本的 Visual Studio Code 或打开 WEB 上的 VS Code。
- 最新版本的 Azure Quantum Development Kit 扩展。有关安装详细信息，请参阅在 VS Code 上安装新式 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{0}-\ket{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 反映统一叠加状态。首先，它将统一叠加转换为全零。然后，它将全零状态转换为所有状态。最后，它反映了所有状态。该运算称为 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 免费测试 Q# 代码 - 只需一个 Microsoft (MSA) 电子邮件帐户即可。有关 Azure Quantum 中的 Copilot 的详细信息，请参阅探索 Azure Quantum。

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

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

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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 the Web 中打开程序。

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

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

使用 Quantinuum H 系列模拟器运行程序

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

选择 “内存中模拟器 ”下拉列表，然后选择“ Quantinuum H 系列模拟器”。
选择当前限制为 20) (拍摄数，然后选择“运行”。

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

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

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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#：设置 Azure Quantum QIR target 配置文件”，然后选择“ Q#不受限制”。
若要运行程序，请从右上角的播放图标下拉列表中选择“ 运行 Q# 文件 ”，或按 Ctrl+F5。程序在默认模拟器上运行用 @EntryPoint() 属性标记的操作或函数。
输出将显示在调试控制台中。

注意

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

后续步骤

浏览其他 Q# 教程：

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

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

先决条件

定义问题

Grover 算法

在中编写 Grover 算法的代码 Q#

定义标记状态

定义最佳迭代数

定义 Grover 的操作

运行最终代码

运行程序

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

使用 Quantinuum H 系列模拟器运行程序

后续步骤

反馈

反馈

其他资源

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

先决条件

定义问题

Grover 算法

在 中编写 Grover 算法的代码 Q#

定义标记状态

定义最佳迭代数

定义 Grover 的操作

运行最终代码

运行程序

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

使用 Quantinuum H 系列模拟器运行程序

后续步骤

反馈

反馈

其他资源

在中编写 Grover 算法的代码 Q#