文档反馈

问题文档片段

问题文档片段包含公式时，显示为空格。

提交类型

issue

有点复杂...

找人问问吧。

PR

小问题，全程线上修改...

一键搞定！

请选择提交类型

问题类型

规范和低错类

- 规范和低错类：

- 错别字或拼写错误，标点符号使用错误、公式错误或显示异常。

- 链接错误、空单元格、格式错误。

- 英文中包含中文字符。

- 界面和描述不一致，但不影响操作。

- 表述不通顺，但不影响理解。

- 版本号不匹配：如软件包名称、界面版本号。

易用性

- 易用性：

- 关键步骤错误或缺失，无法指导用户完成任务。

- 缺少主要功能描述、关键词解释、必要前提条件、注意事项等。

- 描述内容存在歧义指代不明、上下文矛盾。

- 逻辑不清晰，该分类、分项、分步骤的没有给出。

正确性

- 正确性：

- 技术原理、功能、支持平台、参数类型、异常报错等描述和软件实现不一致。

- 原理图、架构图等存在错误。

- 命令、命令参数等错误。

- 代码片段错误。

- 命令无法完成对应功能。

- 界面错误，无法指导操作。

- 代码样例运行报错、运行结果不符。

风险提示

- 风险提示：

- 对重要数据或系统存在风险的操作，缺少安全提示。

内容合规

- 内容合规：

- 违反法律法规，涉及政治、领土主权等敏感词。

- 内容侵权。

请选择问题类型

问题描述

点击输入详细问题描述，以帮助我们快速定位问题。

文档反馈

基于MindQuantum的Grover搜索算法

概述

如果你听过量子计算，那么你一定听说过Grover搜索算法。1996年，Lov Grover [1] 提出了Grover搜索算法，它是一种利用量子状态的叠加性进行并行计算并实现加速的算法。Grover搜索算法被公认为是继Shor算法后的第二大量子算法，也是第一个被完整的实验实现的量子算法，它解决的是无序数据库搜索问题。1997年，Bennett [2] 等人证明，对于非结构化的量子搜索问题，至少需要 $Ω (\sqrt{N})$ 次量子查询，因此Grover搜索算法对于该问题是渐进意义下的最优算法。

无序数据库搜索问题（Unordered Database Search problem）就是从一个海量元素的无序数据库中，找到某些满足要求的元素。由于数据库中元素的数量是巨大的且这些元素是无序排列的，所以，要验证给定的元素是否满足要求很容易，但反过来，要找到这些元素却不是一件容易的事。

求解无序数据库搜索问题（不妨假设只有一个目标搜索数据），经典算法所需的时间复杂度为 $O (N)$ ，而Grover搜索算法所需的时间复杂度仅为 $O (\sqrt{N})$ ，相比经典算法具有平方加速，展示了量子计算的强大性能。此外，Grover搜索算法中用到的振幅扩大技巧，对许多启发式的经典搜索算法可以实现加速，因而具有广泛的应用。

本文档将会介绍Grover搜索算法的基本原理，以及通过两个具体的小例子来展示如何利用MindQuantum实现该算法。

问题描述

我们需要在一组无序的 $N$ 元素集合（数据库）中进行搜索。将数据库中的元素与索引（从 $0$ 到 $N - 1$ 之间的整数）建立一一对应，我们关注于搜索这些元素的索引。考虑将该搜索问题表示为一个关于输入 $x$ 的函数 $f (x)$ ，其中 $x$ 为 $0$ 到 $N - 1$ 之间的整数。那么，函数 $f$ 定义为：

\begin{array}{r} f (x) = {\begin{cases} 0, x \neq x_{t a r g e t} \\ 1, x = x_{t a r g e t} \end{cases} . \end{array}

不失一般性，假设 $N = 2^{n}$ ，那么在量子系统中，索引以量子态 $| 0 ⟩, | 1 ⟩, . . ., | N - 1 ⟩$ （或 $| 00. . .0 ⟩, | 00. . .1 ⟩, . . ., | 11. . .1 ⟩$ ）表示，也即我们可以使用 $n$ 个量子比特存储这些索引。

同时假设搜索问题只有一个目标态 $| ω ⟩$ 。Grover搜索算法的目标就是以极大的概率将 $| ω ⟩$ 搜索出来。

Grover搜索算法的基本原理

Grover搜索算法的基本原理：首先通过Hadamard门产生均匀叠加态，然后反复调用Grover迭代（或称为 $G$ 算子），以放大目标项的概率振幅同时抑制非目标项的概率振幅（该方法称之为振幅放大），最后对末态进行测量，那么就能以极大的概率得到目标态 $| ω ⟩$ 。

Grover搜索算法主要包括以下步骤：

Step 1：数据库初始化

对 $| 0 ⟩^{\otimes n}$ 执行 $H^{\otimes n}$ 操作，使得数据库被初始为一个均匀叠加态，即

$| ψ_{0} ⟩ = H^{\otimes n} | 0 ⟩^{\otimes n} = \frac{1}{\sqrt{N}} \sum_{i = 0}^{N - 1} | i ⟩ .$
Step 2：Grover迭代

Grover迭代又可以分解为四步：
1. 执行Oracle算子 $U_{ω}$ ，翻转目标态 $| ω ⟩$ 的相位
为了将需要寻找的数据和其它的数据区别开，最简单的方法就是翻转目标态的相位（增加一个负号），此时我们需要构造一个Oracle算子 $U_{ω}$ ，其作用如下：

$\begin{array}{r} U_{ω} | x ⟩ = {\begin{cases} | x ⟩, x \neq ω \\ - & | x ⟩, x = ω \end{cases} . \end{array}$

由于当 $x = ω$ 时， $f (ω) = 1$ ，那么 $U_{ω}$ 的作用还可以表示成：

$U_{ω} | x ⟩ = (- 1)^{f (x)} | x ⟩,$

其矩阵表达式为

$\begin{array}{r} U_{ω} = [\begin{array}{ccc} (- 1)^{f (0)} & 0 & \dots & 0 \\ 0 & (- 1)^{f (1)} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & (- 1)^{f (N - 1)} \end{array}] . \end{array}$
1. 执行 $H^{\otimes n}$ 操作
对 $n$ 位量子比特执行 $H^{\otimes n}$ 操作。
1. 执行条件相移算子 $P$
条件相移算子 $P$ 能使 $| 0 ⟩$ 态以外的每个态的相位都翻转，其作用如下：

$\begin{array}{r} P | x ⟩ = {\begin{cases} | 0 ⟩, x = 0 \\ - & | x ⟩, x \neq 0 \end{cases} . \end{array}$

其矩阵表达式为

$\begin{array}{r} P = 2 (| 0 ⟩ ⟨ 0 |)^{\otimes n} - I_{n} = [\begin{array}{ccc} 1 & 0 & \dots & 0 \\ 0 & - 1 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & - 1 \end{array}] . \end{array}$
1. 再次执行 $H^{\otimes n}$ 操作
至此，完整的 $G$ 算子可以表示为

$G = H^{\otimes n} [2 (| 0 ⟩ ⟨ 0 |)^{\otimes n} - I_{n}] H^{\otimes n} U_{ω} .$

注意： $G$ 算子需要迭代的次数为

$r = [\frac{π}{4} \sqrt{\frac{N}{M}}] \sim O (\sqrt{N}),$

其中，M表示目标态的个数。
Step 3：测量

对末态进行 $| 0 ⟩, | 1 ⟩$ 基测量，就能以极大的概率得到目标态 $| ω ⟩$ 。

Grover搜索算法的完整量子线路模型如下所示：

grover algorithm circuit

构造翻转量子比特相位的酉算子

通过上述介绍，我们发现，Grover搜索算法中最关键的部分就是存在可以翻转量子比特相位的酉算子，Oracle算子 $U_{ω}$ 可以翻转目标态的相位，条件相移算子 $P$ 可以翻转 $| 0 ⟩$ 态以外的每个态的相位。

接下来，我们将构造可以翻转某一位量子比特相位的酉算子，定义如下：

[1]:

def bitphaseflip_operator(phase_inversion_qubit, n_qubits):   # 定义可以翻转某一位量子比特相位的函数
    s = [1 for i in range(1 << n_qubits)]
    for i in phase_inversion_qubit:
        s[i] = -1
    if s[0] == -1:
        for i in range(len(s)):
            s[i] = -1 * s[i]
    circuit = Circuit()
    length = len(s)
    cz = []
    for i in range(length):
        if s[i] == -1:
            cz.append([])
            current = i
            t = 0
            while current != 0:
                if (current & 1) == 1:
                    cz[-1].append(t)
                t += 1
                current = current >> 1
            for j in range(i + 1, length):
                if i & j == i:
                    s[j] = -1 * s[j]
    for i in cz:
        if i:
            if len(i) > 1:
                circuit += Z.on(i[-1], i[:-1])
            else:
                circuit += Z.on(i[0])

    return circuit

现在， bitphaseflip_operator() 函数就可以实现翻转某一位量子比特的相位，只需要输入需要翻转相位的目标量子态和量子比特总数即可。

举个例子，我们现在生成3量子比特的均匀叠加态，运行如下代码：

[2]:

# pylint: disable=W0104
from mindquantum import Circuit, UN, H, Z
from mindquantum.simulator import Simulator

n_qubits = 3                                 # 设定量子比特数为3
sim = Simulator('projectq', n_qubits)        # 使用projectq模拟器，命名为sim

circuit = Circuit()                          # 初始化量子线路，命名为circuit
circuit += UN(H, n_qubits)                   # 每位量子比特上执行H门操作

sim.apply_circuit(circuit)                   # 通过模拟器sim运行搭建好的量子线路circuit

circuit                                      # 打印此时的量子线路circuit

[2]:

q0: ──H──
         
q1: ──H──
         
q2: ──H──

[3]:

print(sim.get_qs(True))                      # 打印模拟器sim中运行量子线路circuit后的末态

√2/4¦000⟩
√2/4¦001⟩
√2/4¦010⟩
√2/4¦011⟩
√2/4¦100⟩
√2/4¦101⟩
√2/4¦110⟩
√2/4¦111⟩

从运行的结果看到此时的量子线路，以及我们成功生成了3量子比特的均匀叠加态。

假设我们需要翻转 $| 4 ⟩$ 态的相位，只需调用我们定义好的bitphaseflip_operator()函数即可，运行如下代码：

[4]:

# pylint: disable=W0104
sim.reset()                                                      # 重置模拟器sim维护好的量子态，使得初始化的量子态为|000>

phase_inversion_qubit = [4]                                      # 翻转|4>态的相位
operator = bitphaseflip_operator(phase_inversion_qubit, n_qubits)# 调用我们定义好的bitphaseflip_operator()函数

circuit += operator                                              # 在量子线路circuit中添加翻转|4>态的相位所需的量子门

sim.apply_circuit(circuit)                                       # 通过模拟器sim再次运行搭建好的量子线路circuit

circuit                                                          # 打印此时的量子线路circuit

[4]:

q0: ──H─────────●─────────●──
                │         │  
q1: ──H─────────┼────●────●──
                │    │    │  
q2: ──H────Z────Z────Z────Z──

[5]:

print(sim.get_qs(True))                                          # 打印模拟器sim中运行量子线路circuit后的末态

√2/4¦000⟩
√2/4¦001⟩
√2/4¦010⟩
√2/4¦011⟩
-√2/4¦100⟩
√2/4¦101⟩
√2/4¦110⟩
√2/4¦111⟩

从运行的结果看到此时的量子线路，以及 $| 100 ⟩$ 的相位翻转为-1，运行如下代码：

[6]:

print(int('100', 2))

从运行的结果看到，发生相位翻转的 $| 100 ⟩$ 态即为我们希望相位翻转的 $| 4 ⟩$ 态。

假设我们需要翻转除 $| 0 ⟩$ 态以外的每个态的相位，运行如下代码：

[7]:

# pylint: disable=W0104
n_qubits = 3                                                     # 设定量子比特数为3
sim1 = Simulator('projectq', n_qubits)                           # 使用projectq模拟器，命名为sim1

operator1 = bitphaseflip_operator([i for i in range(1, pow(2, n_qubits))], n_qubits) # 调用我们定义好的bitphaseflip_operator()函数，翻转除|0>态以外的每个态的相位，命名为operator1

circuit1 = Circuit()                                             # 初始化量子线路，命名为circuit1
circuit1 += UN(H, n_qubits)                                      # 每位量子比特上执行H门操作
circuit1 += operator1                                            # 在量子线路circuit1中添加翻转除|0>态以外的每个态的相位所需的量子门

sim1.apply_circuit(circuit1)                                     # 通过模拟器sim1运行搭建好的量子线路circuit1

circuit1                                                         # 打印此时的量子线路circuit1

[7]:

q0: ──H────Z────●────●─────────●──
                │    │         │  
q1: ──H────Z────Z────┼────●────●──
                     │    │    │  
q2: ──H────Z─────────Z────Z────Z──

[8]:

print(sim1.get_qs(True))                                         # 打印模拟器sim1中运行量子线路circuit1后的末态

√2/4¦000⟩
-√2/4¦001⟩
-√2/4¦010⟩
-√2/4¦011⟩
-√2/4¦100⟩
-√2/4¦101⟩
-√2/4¦110⟩
-√2/4¦111⟩

从运行的结果看到此时的量子线路，以及我们成功翻转除 $| 0 ⟩$ 态以外的每个态的相位。

也就是说，我们定义的函数bitphaseflip_operator()可以实现Grover搜素算法中的Oracle算子 $U_{ω}$ 和条件相移算子 $P$ 。

利用MindQuantum实现Grover搜素算法实例

实例1： $n = 3$ ， $| ω ⟩ = | 2 ⟩$ （单目标）

首先，我们需要定义 $G$ 算子，运行如下代码：

[9]:

def G(phase_inversion_qubit, n_qubits):           # 定义Grover搜索算法中的G算子
    operator = bitphaseflip_operator(phase_inversion_qubit, n_qubits)
    operator += UN(H, n_qubits)
    operator += bitphaseflip_operator([i for i in range(1, pow(2, n_qubits))], n_qubits)
    operator += UN(H, n_qubits)
    return operator

然后，我们根据Grover搜索算法的量子线路模型在MindQuantum中搭建对应的量子线路：

[10]:

# pylint: disable=W0104
from numpy import pi, sqrt

n_qubits = 3                                      # 设定量子比特数为3
phase_inversion_qubit = [2]                       # 设定需要翻转相位的目标态，在这里翻转|2>态的相位

N = 2 ** (n_qubits)                               # 计算出数据库中元素的总个数
M = len(phase_inversion_qubit)                    # 计算出目标态的总个数

r = int(pi / 4 * sqrt(N / M))                     # 设定G算子迭代次数为r

sim2 = Simulator('projectq', n_qubits)            # 使用projectq模拟器，命名为sim2

circuit2 = Circuit()                              # 初始化量子线路，命名为circuit2
circuit2 += UN(H, n_qubits)                       # 每位量子比特上执行H门操作

for i in range(r):                                # 循环执行G算子r次
    circuit2 += G(phase_inversion_qubit, n_qubits)

sim2.apply_circuit(circuit2)                      # 通过模拟器sim2运行搭建好的量子线路circuit2

circuit2                                          # 打印此时的量子线路circuit2

[10]:

q0: ──H─────────●─────────●────H────Z────●────●─────────●────H─────────●─────────●────H────Z────●────●─────────●────H──
                │         │              │    │         │              │         │              │    │         │       
q1: ──H────Z────Z────●────●────H────Z────Z────┼────●────●────H────Z────Z────●────●────H────Z────Z────┼────●────●────H──
                     │    │                   │    │    │                   │    │                   │    │    │       
q2: ──H──────────────Z────Z────H────Z─────────Z────Z────Z────H──────────────Z────Z────H────Z─────────Z────Z────Z────H──

[11]:

print(sim2.get_qs(True))                          # 打印模拟器sim2中运行量子线路circuit2后的末态

-√2/16¦000⟩
-√2/16¦001⟩
0.9722718241315036¦010⟩
-√2/16¦011⟩
-√2/16¦100⟩
-√2/16¦101⟩
-√2/16¦110⟩
-√2/16¦111⟩

从运行的结果看到， $| 010 ⟩$ 态的振幅为0.9722718241315036，相比于其它的量子态，这是极大的振幅，也就是说，若我们测量此时的状态，将会以极大的概率得到目标态 $| 010 ⟩$ ，运行如下代码进行测量：

[12]:

# pylint: disable=W0104
from mindquantum import Measure

sim2.reset()                                      # 重置模拟器sim2维护好的量子态，使得初始化的量子态为|000>

circuit2 += UN(Measure(), circuit2.n_qubits)      # 对量子线路circuit2中的每一位量子比特添加测量门

result = sim2.sampling(circuit2, shots=1000)      # 通过模拟器sim2对量子线路circuit2进行1000次的采样
result                                            # 打印采样结果

[12]:

shots: 1000
Keys: q2 q1 q0│0.00     0.2         0.4         0.6         0.8         1.0
──────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴
           000│▒
              │                                                            
           001│▒
              │                                                            
           010│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
              │                                                            
           011│▒
              │                                                            
           100│▒
              │                                                            
           101│▒
              │                                                            
           110│▒
              │                                                            
           111│▒
              │                                                            
{'000': 9, '001': 10, '010': 947, '011': 4, '100': 8, '101': 8, '110': 8, '111': 6}

从运行的结果看到，1000次采样中有947次的采样结果为010，将其转化为10进制数，运行如下代码：

[13]:

print(int('010', 2))

从运行的结果看到，我们成功地搜索出 $| 2 ⟩$ 态。

实例2： $n = 5$ ， $| ω ⟩ = | 5 ⟩$ 和 $| 11 ⟩$ （多目标）

实例1中实现的是单目标搜索，现在我们尝试实现多目标搜索。首先， $G$ 算子已经定义好了，我们只需设定量子比特数和需要翻转相位的目标态，然后搭建对应的量子线路即可，运行如下代码：

[14]:

# pylint: disable=W0104
n_qubits = 5                                      # 设定量子比特数为5
phase_inversion_qubit = [5, 11]                   # 设定需要翻转相位的目标态，在这里翻转|5>态和|11>态的相位

N = 2 ** (n_qubits)                               # 计算出数据库中元素的总个数
M = len(phase_inversion_qubit)                    # 计算出目标态的总个数

r = int(pi / 4 * sqrt(N / M))                     # 设定G算子迭代次数为r

sim3 = Simulator('projectq', n_qubits)            # 使用projectq模拟器，命名为sim3

circuit3 = Circuit()                              # 初始化量子线路，命名为circuit3
circuit3 += UN(H, n_qubits)                       # 每位量子比特上执行H门操作

for i in range(r):                                # 循环执行G算子r次
    circuit3 += G(phase_inversion_qubit, n_qubits)

sim3.apply_circuit(circuit3)                      # 通过模拟器sim3运行搭建好的量子线路circuit3

circuit3                                          # 打印此时的量子线路circuit3

[14]:

q0: ──H────●────●────●────●────●────●────●────●────H────Z────●────●─────────●────●─────────●─────────●─────────●────●─────────●─────────●─────────●─────────●─────────●─────────●─────────●────H────●────●────●────●────●────●────●────●────H────Z────●────●─────────●────●─────────●─────────●─────────●────●─────────●─────────●─────────●─────────●─────────●─────────●─────────●────H────●────●────●────●────●────●────●────●────H────Z────●────●─────────●────●─────────●─────────●─────────●────●─────────●─────────●─────────●─────────●─────────●─────────●─────────●────H──
           │    │    │    │    │    │    │    │              │    │         │    │         │         │         │    │         │         │         │         │         │         │         │         │    │    │    │    │    │    │    │              │    │         │    │         │         │         │    │         │         │         │         │         │         │         │         │    │    │    │    │    │    │    │              │    │         │    │         │         │         │    │         │         │         │         │         │         │         │       
q1: ──H────┼────●────●────┼────┼────●────●────┼────H────Z────Z────┼────●────●────┼────●────●─────────┼────●────●────┼────●────●─────────┼────●────●─────────┼────●────●─────────┼────●────●────H────┼────●────●────┼────┼────●────●────┼────H────Z────Z────┼────●────●────┼────●────●─────────┼────●────●────┼────●────●─────────┼────●────●─────────┼────●────●─────────┼────●────●────H────┼────●────●────┼────┼────●────●────┼────H────Z────Z────┼────●────●────┼────●────●─────────┼────●────●────┼────●────●─────────┼────●────●─────────┼────●────●─────────┼────●────●────H──
           │    │    │    │    │    │    │    │                   │    │    │    │    │    │         │    │    │    │    │    │         │    │    │         │    │    │         │    │    │         │    │    │    │    │    │    │    │                   │    │    │    │    │    │         │    │    │    │    │    │         │    │    │         │    │    │         │    │    │         │    │    │    │    │    │    │    │                   │    │    │    │    │    │         │    │    │    │    │    │         │    │    │         │    │    │         │    │    │       
q2: ──H────Z────Z────┼────●────●────●────┼────●────H────Z─────────Z────Z────Z────┼────┼────┼────●────●────●────●────┼────┼────┼────●────●────●────●─────────┼────┼────┼────●────●────●────●────H────Z────Z────┼────●────●────●────┼────●────H────Z─────────Z────Z────Z────┼────┼────┼────●────●────●────●────┼────┼────┼────●────●────●────●─────────┼────┼────┼────●────●────●────●────H────Z────Z────┼────●────●────●────┼────●────H────Z─────────Z────Z────Z────┼────┼────┼────●────●────●────●────┼────┼────┼────●────●────●────●─────────┼────┼────┼────●────●────●────●────H──
                     │    │    │    │    │    │                                  │    │    │    │    │    │    │    │    │    │    │    │    │    │         │    │    │    │    │    │    │                   │    │    │    │    │    │                                  │    │    │    │    │    │    │    │    │    │    │    │    │    │         │    │    │    │    │    │    │                   │    │    │    │    │    │                                  │    │    │    │    │    │    │    │    │    │    │    │    │    │         │    │    │    │    │    │    │       
q3: ──H──────────────Z────Z────┼────┼────●────●────H────Z────────────────────────Z────Z────Z────Z────Z────Z────Z────┼────┼────┼────┼────┼────┼────┼────●────●────●────●────●────●────●────●────H──────────────Z────Z────┼────┼────●────●────H────Z────────────────────────Z────Z────Z────Z────Z────Z────Z────┼────┼────┼────┼────┼────┼────┼────●────●────●────●────●────●────●────●────H──────────────Z────Z────┼────┼────●────●────H────Z────────────────────────Z────Z────Z────Z────Z────Z────Z────┼────┼────┼────┼────┼────┼────┼────●────●────●────●────●────●────●────●────H──
                               │    │    │    │                                                                     │    │    │    │    │    │    │    │    │    │    │    │    │    │    │                             │    │    │    │                                                                     │    │    │    │    │    │    │    │    │    │    │    │    │    │    │                             │    │    │    │                                                                     │    │    │    │    │    │    │    │    │    │    │    │    │    │    │       
q4: ──H────────────────────────Z────Z────Z────Z────H────Z───────────────────────────────────────────────────────────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────H────────────────────────Z────Z────Z────Z────H────Z───────────────────────────────────────────────────────────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────H────────────────────────Z────Z────Z────Z────H────Z───────────────────────────────────────────────────────────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────Z────H──

[15]:

print(sim3.get_qs(True))                          # 打印模拟器sim3中运行量子线路circuit3后的末态

-0.03590776623212942¦00000⟩
-0.03590776623212939¦00001⟩
-0.03590776623212932¦00010⟩
-0.03590776623212946¦00011⟩
-0.03590776623212935¦00100⟩
0.6932961018664991¦00101⟩
-0.035907766232129434¦00110⟩
-0.03590776623212945¦00111⟩
-0.035907766232129434¦01000⟩
-0.03590776623212945¦01001⟩
-0.03590776623212935¦01010⟩
0.6932961018664991¦01011⟩
-0.03590776623212932¦01100⟩
-0.03590776623212946¦01101⟩
-0.03590776623212939¦01110⟩
-0.03590776623212939¦01111⟩
-0.0359077662321294¦10000⟩
-0.03590776623212941¦10001⟩
-0.035907766232129414¦10010⟩
-0.035907766232129434¦10011⟩
-0.03590776623212944¦10100⟩
-0.035907766232129434¦10101⟩
-0.03590776623212944¦10110⟩
-0.035907766232129434¦10111⟩
-0.03590776623212943¦11000⟩
-0.035907766232129434¦11001⟩
-0.03590776623212943¦11010⟩
-0.035907766232129434¦11011⟩
-0.0359077662321294¦11100⟩
-0.035907766232129434¦11101⟩
-0.035907766232129414¦11110⟩
-0.03590776623212941¦11111⟩

从运行的结果看到， $| 00101 ⟩$ 和 $| 01011 ⟩$ 态的振幅均为0.6932961018664989，相比于其它的量子态，这是极大的振幅，也就是说，若我们测量此时的状态，将会以极大的概率得到目标态 $| 00101 ⟩$ 和 $| 01011 ⟩$ 态，运行如下代码进行测量：

[16]:

# pylint: disable=W0104
sim3.reset()                                      # 重置模拟器sim3维护好的量子态，使得初始化的量子态为|00000>

circuit3 += UN(Measure(), circuit3.n_qubits)      # 对量子线路circuit3中的每一位量子比特添加测量门

result1 = sim3.sampling(circuit3, shots=1000)     # 通过模拟器sim3对量子线路circuit3进行1000次的采样
result1                                           # 打印采样结果

[16]:

shots: 1000
Keys: q4 q3 q2 q1 q0│0.00   0.126       0.251       0.377       0.503       0.629
────────────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴
               00000│▒
                    │                                                            
               00001│▒
                    │                                                            
               00100│▒
                    │                                                            
               00101│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
                    │                                                            
               00110│▒
                    │                                                            
               00111│▒
                    │                                                            
               01000│▒
                    │                                                            
               01001│▒
                    │                                                            
               01010│▒
                    │                                                            
               01011│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
                    │                                                            
               01100│▒
                    │                                                            
               01101│▒
                    │                                                            
               01111│▒
                    │                                                            
               10000│▒
                    │                                                            
               10001│▒
                    │                                                            
               10011│▒
                    │                                                            
               10100│▒
                    │                                                            
               10101│▒
                    │                                                            
               10111│▒
                    │                                                            
               11000│▒
                    │                                                            
               11011│▒
                    │                                                            
               11100│▒
                    │                                                            
               11101│▒
                    │                                                            
               11111│▒
                    │                                                            
{'00000': 2, '00001': 2, '00100': 1, '00101': 463, '00110': 2, '00111': 3, '01000': 1, 
'01001': 1, '01010': 1, '01011': 503, '01100': 1, '01101': 1, '01111': 1, '10000': 1, 
'10001': 1, '10011': 2, '10100': 2, '10101': 2, '10111': 1, '11000': 3, '11011': 1, '11100': 
2, '11101': 2, '11111': 1}

从运行的结果看到，1000次采样中有463次的采样结果为00101和503次的采样结果为01011，将其转化为10进制数，运行如下代码：

[17]:

print(int('00101', 2))
print(int('01011', 2))

5
11

从运行的结果看到，我们成功地搜索出 $| 5 ⟩$ 和 $| 11 ⟩$ 态。

至此，我们介绍了Grover搜索算法的基本原理，以及通过两个具体的小例子来展示如何利用MindQuantum实现该算法！赶紧动手体验一下量子编程的乐趣吧！

若想查询更多关于MindQuantum的API，请点击：https://mindspore.cn/mindquantum/。

参考文献：

[1] L. K. Grover, A fast quantum mechanical algorithm for database search[C]// Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996: 212-219.

[2] G. Brassard, P. Hoyer, M. Mosca, et al. Quantum amplitude amplification and estimation[J]. Contemporary Mathematics, 2002, 305: 53-74.

文档反馈

基于MindQuantum的Grover搜索算法

概述

问题描述

Grover搜索算法的基本原理

构造翻转量子比特相位的酉算子

利用MindQuantum实现Grover搜素算法实例

实例1：n=3​，|ω⟩=|2⟩（单目标）

实例2：n=5，|ω⟩=|5⟩和|11⟩（多目标）

参考文献：

实例1： $n = 3$ ， $| ω ⟩ = | 2 ⟩$ （单目标）

实例2： $n = 5$ ， $| ω ⟩ = | 5 ⟩$ 和 $| 11 ⟩$ （多目标）