{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 基于MindQuantum的Grover搜索算法\n",
"\n",
"[](https://gitee.com/mindspore/docs/blob/r1.7/docs/mindquantum/docs/source_zh_cn/grover_search_algorithm.ipynb)\n",
"\n",
"## 概述\n",
"\n",
"如果你听过量子计算，那么你一定听说过Grover搜索算法。1996年，Lov Grover \\[1\\] 提出了Grover搜索算法，它是一种利用量子状态的叠加性进行并行计算并实现加速的算法。Grover搜索算法被公认为是继Shor算法后的第二大量子算法，也是第一个被完整的实验实现的量子算法，它解决的是无序数据库搜索问题。1997年，Bennett \\[2\\] 等人证明，对于非结构化的量子搜索问题，至少需要$\\Omega(\\sqrt{N})$次量子查询，因此Grover搜索算法对于该问题是渐进意义下的最优算法。\n",
"\n",
"无序数据库搜索问题（Unordered Database Search problem）就是从一个海量元素的无序数据库中，找到某些满足要求的元素。由于数据库中元素的数量是巨大的且这些元素是无序排列的，所以，要验证给定的元素是否满足要求很容易，但反过来，要找到这些元素却不是一件容易的事。\n",
"\n",
"求解无序数据库搜索问题（不妨假设只有一个目标搜索数据），经典算法所需的时间复杂度为$\\mathcal{O}(N)$，而Grover搜索算法所需的时间复杂度仅为$\\mathcal{O}(\\sqrt{N})$，相比经典算法具有平方加速，展示了量子计算的强大性能。此外，Grover搜索算法中用到的振幅扩大技巧，对许多启发式的经典搜索算法可以实现加速，因而具有广泛的应用。\n",
"\n",
"本文档将会介绍Grover搜索算法的基本原理，以及通过两个具体的小例子来展示如何利用MindQuantum实现该算法。\n",
"\n",
"## 问题描述\n",
"\n",
"我们需要在一组无序的$N$元素集合（数据库）中进行搜索。将数据库中的元素与索引（从$0$到$N-1$之间的整数）建立一一对应，我们关注于搜索这些元素的索引。考虑将该搜索问题表示为一个关于输入$x$的函数$f(x)$，其中$x$为$0$到$N-1$之间的整数。那么，函数$f$定义为：\n",
"\n",
"$$\n",
"\\begin{equation}\n",
"f(x)=\\begin{cases}0,x\\neq x_{target}\\\\\\\\\n",
"1,x=x_{target}\n",
"\\end{cases}\n",
"\\end{equation}.\n",
"$$\n",
"\n",
"不失一般性，假设$N=2^n$，那么在量子系统中，索引以量子态$|0\\rangle,|1\\rangle,...,|N-1\\rangle$（或$|00...0\\rangle,|00...1\\rangle,...,|11...1\\rangle$）表示，也即我们可以使用$n$个量子比特存储这些索引。\n",
"\n",
"同时假设搜索问题只有一个目标态$|\\omega\\rangle$。Grover搜索算法的目标就是以极大的概率将$|\\omega\\rangle$搜索出来。\n",
"\n",
"## Grover搜索算法的基本原理\n",
"\n",
"Grover搜索算法的基本原理：首先通过`Hadamard`门产生均匀叠加态，然后反复调用Grover迭代（或称为$G$算子），以放大目标项的概率振幅同时抑制非目标项的概率振幅（该方法称之为振幅放大），最后对末态进行测量，那么就能以极大的概率得到目标态$|\\omega\\rangle$。\n",
"\n",
"Grover搜索算法主要包括以下步骤：\n",
"\n",
"- Step 1：数据库初始化\n",
"\n",
" 对$|0\\rangle^{\\otimes n}$执行$H^{\\otimes n}$操作，使得数据库被初始为一个均匀叠加态，即\n",
"\n",
" $$\n",
" |\\psi_0\\rangle=H^{\\otimes n}|0\\rangle^{\\otimes n}=\\frac{1}{\\sqrt{N}}\\sum_{i=0}^{N-1}|i\\rangle.\n",
" $$\n",
"\n",
"- Step 2：Grover迭代\n",
"\n",
" Grover迭代又可以分解为四步：\n",
"\n",
" 1. 执行Oracle算子$U_{\\omega}$，翻转目标态$|\\omega \\rangle$的相位\n",
"\n",
" 为了将需要寻找的数据和其它的数据区别开，最简单的方法就是翻转目标态的相位（增加一个负号），此时我们需要构造一个Oracle算子$U_{\\omega}$，其作用如下：\n",
"\n",
" $$\n",
" \\begin{equation}\n",
" U_{\\omega}|x\\rangle=\\begin{cases}\n",
" &|x\\rangle,x\\neq \\omega&\\\\\\\\\n",
" -&|x\\rangle,x=\\omega&\n",
" \\end{cases}\n",
" \\end{equation}.\n",
" $$\n",
"\n",
" 由于当$x=\\omega$时，$f(\\omega)=1$，那么$U_{\\omega}$的作用还可以表示成：\n",
"\n",
" $$\n",
" U_{\\omega}|x\\rangle=(-1)^{f(x)}|x\\rangle,\n",
" $$\n",
"\n",
" 其矩阵表达式为\n",
"\n",
" $$\n",
" \\begin{equation}\n",
" U_{\\omega}=\n",
" \\left[\n",
" \\begin{array}{ccc}\n",
" (-1)^{f(0)} & 0 & \\dots & 0 \\\\\\\\\n",
" 0 & (-1)^{f(1)} & \\dots & 0 \\\\\\\\\n",
" \\vdots & \\vdots & \\ddots & \\vdots \\\\\\\\\n",
" 0 & 0 & \\dots & (-1)^{f(N-1)}\n",
" \\end{array}\n",
" \\right]\n",
" \\end{equation}.\n",
" $$\n",
"\n",
" 2. 执行$H^{\\otimes n}$操作\n",
"\n",
" 对$n$位量子比特执行$H^{\\otimes n}$操作。\n",
"\n",
" 3. 执行条件相移算子$P$\n",
"\n",
" 条件相移算子$P$能使$|0\\rangle$态以外的每个态的相位都翻转，其作用如下：\n",
"\n",
" $$\n",
" \\begin{equation}\n",
" P|x\\rangle=\\begin{cases}&|0\\rangle,x= 0&\\\\\\\\\n",
" -&|x\\rangle,x\\neq0&\n",
" \\end{cases}\n",
" \\end{equation}.\n",
" $$\n",
"\n",
" 其矩阵表达式为\n",
"\n",
" $$\n",
" \\begin{equation}\n",
" P = 2(|0\\rangle\\langle0|)^{\\otimes n} - I_n =\n",
" \\left[\n",
" \\begin{array}{ccc}\n",
" 1 & 0 & \\dots & 0 \\\\\\\\\n",
" 0 & -1 & \\dots & 0 \\\\\\\\\n",
" \\vdots & \\vdots & \\ddots & \\vdots \\\\\\\\\n",
" 0 & 0 & \\dots & -1\n",
" \\end{array}\n",
" \\right]\n",
" \\end{equation}.\n",
" $$\n",
"\n",
" 4. 再次执行$H^{\\otimes n}$操作\n",
"\n",
" 至此，完整的$G$算子可以表示为\n",
"\n",
" $$\n",
" G = H^{\\otimes n} [2(|0\\rangle\\langle0|)^{\\otimes n} - I_n] H^{\\otimes n} U_{\\omega}.\n",
" $$\n",
"\n",
" 注意：$G$算子需要迭代的次数为\n",
"\n",
" $$\n",
" r = \\left[ \\frac{\\pi}{4} \\sqrt{\\frac{N}{M}} \\right] \\sim O(\\sqrt{N}),\n",
" $$\n",
"\n",
" 其中，M表示目标态的个数。\n",
"\n",
"- Step 3：测量\n",
"\n",
" 对末态进行$\\\\{|0\\rangle,|1\\rangle\\\\}$基测量，就能以极大的概率得到目标态$|\\omega \\rangle$。\n",
"\n",
"Grover搜索算法的完整量子线路模型如下所示：\n",
"\n",
"\n",
"\n",
"## 构造翻转量子比特相位的酉算子\n",
"\n",
"通过上述介绍，我们发现，Grover搜索算法中最关键的部分就是存在可以翻转量子比特相位的酉算子，Oracle算子$U_{\\omega}$可以翻转目标态的相位，条件相移算子$P$可以翻转$|0\\rangle$态以外的每个态的相位。\n",
"\n",
"接下来，我们将构造可以翻转某一位量子比特相位的酉算子，定义如下："
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"def bitphaseflip_operator(phase_inversion_qubit, n_qubits): # 定义可以翻转某一位量子比特相位的函数\n",
" s = [1 for i in range(1 << n_qubits)]\n",
" for i in phase_inversion_qubit:\n",
" s[i] = -1\n",
" if s[0] == -1:\n",
" for i in range(len(s)):\n",
" s[i] = -1 * s[i]\n",
" circuit = Circuit()\n",
" length = len(s)\n",
" cz = []\n",
" for i in range(length):\n",
" if s[i] == -1:\n",
" cz.append([])\n",
" current = i\n",
" t = 0\n",
" while current != 0:\n",
" if (current & 1) == 1:\n",
" cz[-1].append(t)\n",
" t += 1\n",
" current = current >> 1\n",
" for j in range(i + 1, length):\n",
" if i & j == i:\n",
" s[j] = -1 * s[j]\n",
" for i in cz:\n",
" if i:\n",
" if len(i) > 1:\n",
" circuit += Z.on(i[-1], i[:-1])\n",
" else:\n",
" circuit += Z.on(i[0])\n",
"\n",
" return circuit"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"现在， `bitphaseflip_operator()` 函数就可以实现翻转某一位量子比特的相位，只需要输入需要翻转相位的目标量子态和量子比特总数即可。\n",
"\n",
"举个例子，我们现在生成3量子比特的均匀叠加态，运行如下代码："
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"tags": []
},
"outputs": [
{
"data": {
"text/html": [
"q0: ──H──\n",
" \n",
"q1: ──H──\n",
" \n",
"q2: ──H──\n",
"\n"
],
"text/plain": [
"q0: ──H──\n",
" \n",
"q1: ──H──\n",
" \n",
"q2: ──H──"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"from mindquantum import Circuit, UN, H, Z\n",
"from mindquantum.simulator import Simulator\n",
"\n",
"n_qubits = 3 # 设定量子比特数为3\n",
"sim = Simulator('projectq', n_qubits) # 使用projectq模拟器，命名为sim\n",
"\n",
"circuit = Circuit() # 初始化量子线路，命名为circuit\n",
"circuit += UN(H, n_qubits) # 每位量子比特上执行H门操作\n",
"\n",
"sim.apply_circuit(circuit) # 通过模拟器sim运行搭建好的量子线路circuit\n",
"\n",
"circuit # 打印此时的量子线路circuit"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"√2/4¦000⟩\n",
"√2/4¦001⟩\n",
"√2/4¦010⟩\n",
"√2/4¦011⟩\n",
"√2/4¦100⟩\n",
"√2/4¦101⟩\n",
"√2/4¦110⟩\n",
"√2/4¦111⟩\n"
]
}
],
"source": [
"print(sim.get_qs(True)) # 打印模拟器sim中运行量子线路circuit后的末态"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到此时的量子线路，以及我们成功生成了3量子比特的均匀叠加态。\n",
"\n",
"假设我们需要翻转$|4\\rangle$态的相位，只需调用我们定义好的`bitphaseflip_operator()`函数即可，运行如下代码："
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"tags": []
},
"outputs": [
{
"data": {
"text/html": [
"q0: ──H─────────●─────────●──\n",
" │ │ \n",
"q1: ──H─────────┼────●────●──\n",
" │ │ │ \n",
"q2: ──H────Z────Z────Z────Z──\n",
"\n"
],
"text/plain": [
"q0: ──H─────────●─────────●──\n",
" │ │ \n",
"q1: ──H─────────┼────●────●──\n",
" │ │ │ \n",
"q2: ──H────Z────Z────Z────Z──"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"sim.reset() # 重置模拟器sim维护好的量子态，使得初始化的量子态为|000>\n",
"\n",
"phase_inversion_qubit = [4] # 翻转|4>态的相位\n",
"operator = bitphaseflip_operator(phase_inversion_qubit, n_qubits)# 调用我们定义好的bitphaseflip_operator()函数\n",
"\n",
"circuit += operator # 在量子线路circuit中添加翻转|4>态的相位所需的量子门\n",
"\n",
"sim.apply_circuit(circuit) # 通过模拟器sim再次运行搭建好的量子线路circuit\n",
"\n",
"circuit # 打印此时的量子线路circuit"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"√2/4¦000⟩\n",
"√2/4¦001⟩\n",
"√2/4¦010⟩\n",
"√2/4¦011⟩\n",
"-√2/4¦100⟩\n",
"√2/4¦101⟩\n",
"√2/4¦110⟩\n",
"√2/4¦111⟩\n"
]
}
],
"source": [
"print(sim.get_qs(True)) # 打印模拟器sim中运行量子线路circuit后的末态"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到此时的量子线路，以及$|100\\rangle$的相位翻转为-1，运行如下代码："
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4\n"
]
}
],
"source": [
"print(int('100', 2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到，发生相位翻转的$|100\\rangle$态即为我们希望相位翻转的$|4\\rangle$态。\n",
"\n",
"假设我们需要翻转除$|0\\rangle$态以外的每个态的相位，运行如下代码："
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"tags": []
},
"outputs": [
{
"data": {
"text/html": [
"q0: ──H────Z────●────●─────────●──\n",
" │ │ │ \n",
"q1: ──H────Z────Z────┼────●────●──\n",
" │ │ │ \n",
"q2: ──H────Z─────────Z────Z────Z──\n",
"\n"
],
"text/plain": [
"q0: ──H────Z────●────●─────────●──\n",
" │ │ │ \n",
"q1: ──H────Z────Z────┼────●────●──\n",
" │ │ │ \n",
"q2: ──H────Z─────────Z────Z────Z──"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"n_qubits = 3 # 设定量子比特数为3\n",
"sim1 = Simulator('projectq', n_qubits) # 使用projectq模拟器，命名为sim1\n",
"\n",
"operator1 = bitphaseflip_operator([i for i in range(1, pow(2, n_qubits))], n_qubits) # 调用我们定义好的bitphaseflip_operator()函数，翻转除|0>态以外的每个态的相位，命名为operator1\n",
"\n",
"circuit1 = Circuit() # 初始化量子线路，命名为circuit1\n",
"circuit1 += UN(H, n_qubits) # 每位量子比特上执行H门操作\n",
"circuit1 += operator1 # 在量子线路circuit1中添加翻转除|0>态以外的每个态的相位所需的量子门\n",
"\n",
"sim1.apply_circuit(circuit1) # 通过模拟器sim1运行搭建好的量子线路circuit1\n",
"\n",
"circuit1 # 打印此时的量子线路circuit1"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"√2/4¦000⟩\n",
"-√2/4¦001⟩\n",
"-√2/4¦010⟩\n",
"-√2/4¦011⟩\n",
"-√2/4¦100⟩\n",
"-√2/4¦101⟩\n",
"-√2/4¦110⟩\n",
"-√2/4¦111⟩\n"
]
}
],
"source": [
"print(sim1.get_qs(True)) # 打印模拟器sim1中运行量子线路circuit1后的末态"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到此时的量子线路，以及我们成功翻转除$|0\\rangle$态以外的每个态的相位。\n",
"\n",
"也就是说，我们定义的函数`bitphaseflip_operator()`可以实现Grover搜素算法中的Oracle算子$U_{\\omega}$和条件相移算子$P$。\n",
"\n",
"## 利用MindQuantum实现Grover搜素算法实例\n",
"\n",
"### 实例1：$n=3$，$|\\omega\\rangle=|2\\rangle$（单目标）\n",
"\n",
"首先，我们需要定义$G$算子，运行如下代码："
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"def G(phase_inversion_qubit, n_qubits): # 定义Grover搜索算法中的G算子\n",
" operator = bitphaseflip_operator(phase_inversion_qubit, n_qubits)\n",
" operator += UN(H, n_qubits)\n",
" operator += bitphaseflip_operator([i for i in range(1, pow(2, n_qubits))], n_qubits)\n",
" operator += UN(H, n_qubits)\n",
" return operator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"然后，我们根据Grover搜索算法的量子线路模型在MindQuantum中搭建对应的量子线路："
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"tags": []
},
"outputs": [
{
"data": {
"text/html": [
"q0: ──H─────────●─────────●────H────Z────●────●─────────●────H─────────●─────────●────H────Z────●────●─────────●────H──\n",
" │ │ │ │ │ │ │ │ │ │ \n",
"q1: ──H────Z────Z────●────●────H────Z────Z────┼────●────●────H────Z────Z────●────●────H────Z────Z────┼────●────●────H──\n",
" │ │ │ │ │ │ │ │ │ │ \n",
"q2: ──H──────────────Z────Z────H────Z─────────Z────Z────Z────H──────────────Z────Z────H────Z─────────Z────Z────Z────H──\n",
"\n"
],
"text/plain": [
"q0: ──H─────────●─────────●────H────Z────●────●─────────●────H─────────●─────────●────H────Z────●────●─────────●────H──\n",
" │ │ │ │ │ │ │ │ │ │ \n",
"q1: ──H────Z────Z────●────●────H────Z────Z────┼────●────●────H────Z────Z────●────●────H────Z────Z────┼────●────●────H──\n",
" │ │ │ │ │ │ │ │ │ │ \n",
"q2: ──H──────────────Z────Z────H────Z─────────Z────Z────Z────H──────────────Z────Z────H────Z─────────Z────Z────Z────H──"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"from numpy import pi, sqrt\n",
"\n",
"n_qubits = 3 # 设定量子比特数为3\n",
"phase_inversion_qubit = [2] # 设定需要翻转相位的目标态，在这里翻转|2>态的相位\n",
"\n",
"N = 2 ** (n_qubits) # 计算出数据库中元素的总个数\n",
"M = len(phase_inversion_qubit) # 计算出目标态的总个数\n",
"\n",
"r = int(pi / 4 * sqrt(N / M)) # 设定G算子迭代次数为r\n",
"\n",
"sim2 = Simulator('projectq', n_qubits) # 使用projectq模拟器，命名为sim2\n",
"\n",
"circuit2 = Circuit() # 初始化量子线路，命名为circuit2\n",
"circuit2 += UN(H, n_qubits) # 每位量子比特上执行H门操作\n",
"\n",
"for i in range(r): # 循环执行G算子r次\n",
" circuit2 += G(phase_inversion_qubit, n_qubits)\n",
"\n",
"sim2.apply_circuit(circuit2) # 通过模拟器sim2运行搭建好的量子线路circuit2\n",
"\n",
"circuit2 # 打印此时的量子线路circuit2"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-√2/16¦000⟩\n",
"-√2/16¦001⟩\n",
"0.9722718241315036¦010⟩\n",
"-√2/16¦011⟩\n",
"-√2/16¦100⟩\n",
"-√2/16¦101⟩\n",
"-√2/16¦110⟩\n",
"-√2/16¦111⟩\n"
]
}
],
"source": [
"print(sim2.get_qs(True)) # 打印模拟器sim2中运行量子线路circuit2后的末态"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到，$|010\\rangle$态的振幅为0.9722718241315036，相比于其它的量子态，这是极大的振幅，也就是说，若我们测量此时的状态，将会以极大的概率得到目标态$|010\\rangle$，运行如下代码进行测量："
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"tags": []
},
"outputs": [
{
"data": {
"text/html": [
"shots: 1000\n",
"Keys: q2 q1 q0│0.00 0.2 0.4 0.6 0.8 1.0\n",
"──────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴\n",
" 000│▒\n",
" │ \n",
" 001│▒\n",
" │ \n",
" 010│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓\n",
" │ \n",
" 011│▒\n",
" │ \n",
" 100│▒\n",
" │ \n",
" 101│▒\n",
" │ \n",
" 110│▒\n",
" │ \n",
" 111│▒\n",
" │ \n",
"{'000': 9, '001': 10, '010': 947, '011': 4, '100': 8, '101': 8, '110': 8, '111': 6}\n",
"\n"
],
"text/plain": [
"shots: 1000\n",
"Keys: q2 q1 q0│0.00 0.2 0.4 0.6 0.8 1.0\n",
"──────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴\n",
" 000│▒\n",
" │ \n",
" 001│▒\n",
" │ \n",
" 010│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓\n",
" │ \n",
" 011│▒\n",
" │ \n",
" 100│▒\n",
" │ \n",
" 101│▒\n",
" │ \n",
" 110│▒\n",
" │ \n",
" 111│▒\n",
" │ \n",
"{'000': 9, '001': 10, '010': 947, '011': 4, '100': 8, '101': 8, '110': 8, '111': 6}"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"from mindquantum import Measure\n",
"\n",
"sim2.reset() # 重置模拟器sim2维护好的量子态，使得初始化的量子态为|000>\n",
"\n",
"circuit2 += UN(Measure(), circuit2.n_qubits) # 对量子线路circuit2中的每一位量子比特添加测量门\n",
"\n",
"result = sim2.sampling(circuit2, shots=1000) # 通过模拟器sim2对量子线路circuit2进行1000次的采样\n",
"result # 打印采样结果"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到，1000次采样中有947次的采样结果为`010`，将其转化为10进制数，运行如下代码："
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2\n"
]
}
],
"source": [
"print(int('010', 2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到，我们成功地搜索出$|2\\rangle$态。\n",
"\n",
"### 实例2：$n=5$，$|\\omega\\rangle=|5\\rangle$和$|11\\rangle$（多目标）\n",
"\n",
"实例1中实现的是单目标搜索，现在我们尝试实现多目标搜索。首先，$G$算子已经定义好了，我们只需设定量子比特数和需要翻转相位的目标态，然后搭建对应的量子线路即可，运行如下代码："
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"tags": []
},
"outputs": [
{
"data": {
"text/html": [
"q0: ──H────●────●────●────●────●────●────●────●────H────Z────●────●─────────●────●─────────●─────────●─────────●────●─────────●─────────●─────────●─────────●─────────●─────────●─────────●────H────●────●────●────●────●────●────●────●────H────Z────●────●─────────●────●─────────●─────────●─────────●────●─────────●─────────●─────────●─────────●─────────●─────────●─────────●────H────●────●────●────●────●────●────●────●────H────Z────●────●─────────●────●─────────●─────────●─────────●────●─────────●─────────●─────────●─────────●─────────●─────────●─────────●────H──\n",
" │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ \n",
"q1: ──H────┼────●────●────┼────┼────●────●────┼────H────Z────Z────┼────●────●────┼────●────●─────────┼────●────●────┼────●────●─────────┼────●────●─────────┼────●────●─────────┼────●────●────H────┼────●────●────┼────┼────●────●────┼────H────Z────Z────┼────●────●────┼────●────●─────────┼────●────●────┼────●────●─────────┼────●────●─────────┼────●────●─────────┼────●────●────H────┼────●────●────┼────┼────●────●────┼────H────Z────Z────┼────●────●────┼────●────●─────────┼────●────●────┼────●────●─────────┼────●────●─────────┼────●────●─────────┼────●────●────H──\n",
" │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ \n",
"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──\n",
" │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ \n",
"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──\n",
" │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ \n",
"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──\n",
"\n"
],
"text/plain": [
"q0: ──H────●────●────●────●────●────●────●────●────H────Z────●────●─────────●────●─────────●─────────●─────────●────●─────────●─────────●─────────●─────────●─────────●─────────●─────────●────H────●────●────●────●────●────●────●────●────H────Z────●────●─────────●────●─────────●─────────●─────────●────●─────────●─────────●─────────●─────────●─────────●─────────●─────────●────H────●────●────●────●────●────●────●────●────H────Z────●────●─────────●────●─────────●─────────●─────────●────●─────────●─────────●─────────●─────────●─────────●─────────●─────────●────H──\n",
" │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ \n",
"q1: ──H────┼────●────●────┼────┼────●────●────┼────H────Z────Z────┼────●────●────┼────●────●─────────┼────●────●────┼────●────●─────────┼────●────●─────────┼────●────●─────────┼────●────●────H────┼────●────●────┼────┼────●────●────┼────H────Z────Z────┼────●────●────┼────●────●─────────┼────●────●────┼────●────●─────────┼────●────●─────────┼────●────●─────────┼────●────●────H────┼────●────●────┼────┼────●────●────┼────H────Z────Z────┼────●────●────┼────●────●─────────┼────●────●────┼────●────●─────────┼────●────●─────────┼────●────●─────────┼────●────●────H──\n",
" │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ \n",
"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──\n",
" │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ \n",
"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──\n",
" │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ \n",
"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──"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"n_qubits = 5 # 设定量子比特数为5\n",
"phase_inversion_qubit = [5, 11] # 设定需要翻转相位的目标态，在这里翻转|5>态和|11>态的相位\n",
"\n",
"N = 2 ** (n_qubits) # 计算出数据库中元素的总个数\n",
"M = len(phase_inversion_qubit) # 计算出目标态的总个数\n",
"\n",
"r = int(pi / 4 * sqrt(N / M)) # 设定G算子迭代次数为r\n",
"\n",
"sim3 = Simulator('projectq', n_qubits) # 使用projectq模拟器，命名为sim3\n",
"\n",
"circuit3 = Circuit() # 初始化量子线路，命名为circuit3\n",
"circuit3 += UN(H, n_qubits) # 每位量子比特上执行H门操作\n",
"\n",
"for i in range(r): # 循环执行G算子r次\n",
" circuit3 += G(phase_inversion_qubit, n_qubits)\n",
"\n",
"sim3.apply_circuit(circuit3) # 通过模拟器sim3运行搭建好的量子线路circuit3\n",
"\n",
"circuit3 # 打印此时的量子线路circuit3"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-0.03590776623212942¦00000⟩\n",
"-0.03590776623212939¦00001⟩\n",
"-0.03590776623212932¦00010⟩\n",
"-0.03590776623212946¦00011⟩\n",
"-0.03590776623212935¦00100⟩\n",
"0.6932961018664991¦00101⟩\n",
"-0.035907766232129434¦00110⟩\n",
"-0.03590776623212945¦00111⟩\n",
"-0.035907766232129434¦01000⟩\n",
"-0.03590776623212945¦01001⟩\n",
"-0.03590776623212935¦01010⟩\n",
"0.6932961018664991¦01011⟩\n",
"-0.03590776623212932¦01100⟩\n",
"-0.03590776623212946¦01101⟩\n",
"-0.03590776623212939¦01110⟩\n",
"-0.03590776623212939¦01111⟩\n",
"-0.0359077662321294¦10000⟩\n",
"-0.03590776623212941¦10001⟩\n",
"-0.035907766232129414¦10010⟩\n",
"-0.035907766232129434¦10011⟩\n",
"-0.03590776623212944¦10100⟩\n",
"-0.035907766232129434¦10101⟩\n",
"-0.03590776623212944¦10110⟩\n",
"-0.035907766232129434¦10111⟩\n",
"-0.03590776623212943¦11000⟩\n",
"-0.035907766232129434¦11001⟩\n",
"-0.03590776623212943¦11010⟩\n",
"-0.035907766232129434¦11011⟩\n",
"-0.0359077662321294¦11100⟩\n",
"-0.035907766232129434¦11101⟩\n",
"-0.035907766232129414¦11110⟩\n",
"-0.03590776623212941¦11111⟩\n"
]
}
],
"source": [
"print(sim3.get_qs(True)) # 打印模拟器sim3中运行量子线路circuit3后的末态"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到，$|00101\\rangle$和$|01011\\rangle$态的振幅均为0.6932961018664989，相比于其它的量子态，这是极大的振幅，也就是说，若我们测量此时的状态，将会以极大的概率得到目标态$|00101\\rangle$和$|01011\\rangle$态，运行如下代码进行测量："
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"tags": []
},
"outputs": [
{
"data": {
"text/html": [
"shots: 1000\n",
"Keys: q4 q3 q2 q1 q0│0.00 0.126 0.251 0.377 0.503 0.629\n",
"────────────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴\n",
" 00000│▒\n",
" │ \n",
" 00001│▒\n",
" │ \n",
" 00100│▒\n",
" │ \n",
" 00101│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n",
" │ \n",
" 00110│▒\n",
" │ \n",
" 00111│▒\n",
" │ \n",
" 01000│▒\n",
" │ \n",
" 01001│▒\n",
" │ \n",
" 01010│▒\n",
" │ \n",
" 01011│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓\n",
" │ \n",
" 01100│▒\n",
" │ \n",
" 01101│▒\n",
" │ \n",
" 01111│▒\n",
" │ \n",
" 10000│▒\n",
" │ \n",
" 10001│▒\n",
" │ \n",
" 10011│▒\n",
" │ \n",
" 10100│▒\n",
" │ \n",
" 10101│▒\n",
" │ \n",
" 10111│▒\n",
" │ \n",
" 11000│▒\n",
" │ \n",
" 11011│▒\n",
" │ \n",
" 11100│▒\n",
" │ \n",
" 11101│▒\n",
" │ \n",
" 11111│▒\n",
" │ \n",
"{'00000': 2, '00001': 2, '00100': 1, '00101': 463, '00110': 2, '00111': 3, '01000': 1, \n",
"'01001': 1, '01010': 1, '01011': 503, '01100': 1, '01101': 1, '01111': 1, '10000': 1, \n",
"'10001': 1, '10011': 2, '10100': 2, '10101': 2, '10111': 1, '11000': 3, '11011': 1, '11100': \n",
"2, '11101': 2, '11111': 1}\n",
"\n"
],
"text/plain": [
"shots: 1000\n",
"Keys: q4 q3 q2 q1 q0│0.00 0.126 0.251 0.377 0.503 0.629\n",
"────────────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴\n",
" 00000│▒\n",
" │ \n",
" 00001│▒\n",
" │ \n",
" 00100│▒\n",
" │ \n",
" 00101│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n",
" │ \n",
" 00110│▒\n",
" │ \n",
" 00111│▒\n",
" │ \n",
" 01000│▒\n",
" │ \n",
" 01001│▒\n",
" │ \n",
" 01010│▒\n",
" │ \n",
" 01011│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓\n",
" │ \n",
" 01100│▒\n",
" │ \n",
" 01101│▒\n",
" │ \n",
" 01111│▒\n",
" │ \n",
" 10000│▒\n",
" │ \n",
" 10001│▒\n",
" │ \n",
" 10011│▒\n",
" │ \n",
" 10100│▒\n",
" │ \n",
" 10101│▒\n",
" │ \n",
" 10111│▒\n",
" │ \n",
" 11000│▒\n",
" │ \n",
" 11011│▒\n",
" │ \n",
" 11100│▒\n",
" │ \n",
" 11101│▒\n",
" │ \n",
" 11111│▒\n",
" │ \n",
"{'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}"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pylint: disable=W0104\n",
"sim3.reset() # 重置模拟器sim3维护好的量子态，使得初始化的量子态为|00000>\n",
"\n",
"circuit3 += UN(Measure(), circuit3.n_qubits) # 对量子线路circuit3中的每一位量子比特添加测量门\n",
"\n",
"result1 = sim3.sampling(circuit3, shots=1000) # 通过模拟器sim3对量子线路circuit3进行1000次的采样\n",
"result1 # 打印采样结果"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到，1000次采样中有463次的采样结果为`00101`和503次的采样结果为`01011`，将其转化为10进制数，运行如下代码："
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5\n",
"11\n"
]
}
],
"source": [
"print(int('00101', 2))\n",
"print(int('01011', 2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从运行的结果看到，我们成功地搜索出$|5\\rangle$和$|11\\rangle$态。\n",
"\n",
"至此，我们介绍了Grover搜索算法的基本原理，以及通过两个具体的小例子来展示如何利用MindQuantum实现该算法！赶紧动手体验一下量子编程的乐趣吧！\n",
"\n",
"若想查询更多关于MindQuantum的API，请点击：[https://mindspore.cn/mindquantum/](https://mindspore.cn/mindquantum/)。\n",
"\n",
"### **参考文献：**\n",
"\n",
"\\[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.\n",
"\n",
"\\[2\\] G. Brassard, P. Hoyer, M. Mosca, et al. Quantum amplitude amplification and estimation\\[J\\]. Contemporary Mathematics, 2002, 305: 53-74."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "MindSpore",
"language": "python",
"name": "mindspore"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}