{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 基于MindQuantum的Grover搜索算法和龙算法\n",
"\n",
"[](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/notebook/r1.8/mindquantum/zh_cn/mindspore_grover_search_algorithm.ipynb) \n",
"[](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/notebook/r1.8/mindquantum/zh_cn/mindspore_grover_search_algorithm.py) \n",
"[](https://gitee.com/mindspore/docs/blob/r1.8/docs/mindquantum/docs/source_zh_cn/grover_search_algorithm.ipynb)\n",
"[](https://authoring-modelarts-cnnorth4.huaweicloud.com/console/lab?share-url-b64=aHR0cHM6Ly9taW5kc3BvcmUtd2Vic2l0ZS5vYnMuY24tbm9ydGgtNC5teWh1YXdlaWNsb3VkLmNvbS9ub3RlYm9vay9yMS44L21pbmRxdWFudHVtL3poX2NuL21pbmRzcG9yZV9ncm92ZXJfc2VhcmNoX2FsZ29yaXRobS5pcHluYg%3D%3D&imageid=9549a798-7cce-42b2-a2ae-dcb864f122df)\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",
"*提示：由于HiQ量子云平台JupyterLab环境中svg图片暂时无法显示，请开发者自行打印量子线路。*\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": {
"image/svg+xml": "",
"text/plain": [
""
]
},
"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.svg() # 打印此时的量子线路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": {
"image/svg+xml": "",
"text/plain": [
""
]
},
"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.svg() # 打印此时的量子线路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": {
"image/svg+xml": "",
"text/plain": [
""
]
},
"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.svg() # 打印此时的量子线路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": {
"image/svg+xml": "",
"text/plain": [
""
]
},
"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.svg() # 打印此时的量子线路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": {
"image/svg+xml": "",
"text/plain": [
""
]
},
"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.svg() # 打印采样结果"
]
},
{
"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": {
"image/svg+xml": "",
"text/plain": [
""
]
},
"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.svg() # 打印此时的量子线路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": {
"image/svg+xml": "",
"text/plain": [
""
]
},
"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.svg() # 打印采样结果"
]
},
{
"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",
"## 龙算法\n",
"\n",
"除了在规模为4的数据库中找1个数据的场景，Grover算法不能够精确的搜索出所标记态。清华大学龙桂鲁教授在Grover算法基础之上提出量子精确搜索算法龙算法[3]，能够以准确率为1的概率在所有场景中搜索出目标态。其主要思想是将Grover算子改写为如下的算子，\n",
"\n",
"$$\n",
"L = -H^{\\otimes n} R_0 H^{\\otimes n} R_\\tau\n",
"$$\n",
"\n",
"其中：$R_0 = (I+(e^{i\\theta}-1)\\left|0\\right>\\left<0\\right|)$，$R_\\tau = (I+(e^{i\\theta}-1)\\left|\\tau\\right>\\left<\\tau\\right|)$。在满足相位匹配条件时，\n",
"\n",
"$$\n",
"\\theta = 2\\arcsin\\left(\\sin\\beta\\sin\\left(\\frac{\\pi}{4J_s+6}\\right)\\right)\n",
"$$\n",
"\n",
"我们只需作用$J_s+1$次龙算子，就可以以概率1找到目标态，这里$\\beta=\\arcsin{\\sqrt{M/N}}$，$M$为标记态个数，$N$为数据库大小，$J_s>=[((\\pi/2)-\\beta)/\\beta]$。下面我们用MindQuantum来实现。\n",
"\n",
"### 一般角度相位转动线路\n",
"\n",
"借助于辅助比特，我们搭建某个计算基矢一般角度相位转动线路。"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [],
"source": [
"from mindquantum.core import X, PhaseShift\n",
"from mindquantum.core import Circuit\n",
"def change_phase_with_anclia(which, n_qubits, phase):\n",
" c = Circuit()\n",
" which_bit = bin(which)[2:].zfill(n_qubits)[::-1]\n",
" polarity_circ = Circuit()\n",
" for idx, bit in enumerate(which_bit):\n",
" if bit == \"0\":\n",
" polarity_circ += X.on(idx)\n",
" c += polarity_circ\n",
" c += PhaseShift(phase).on(n_qubits, list(range(n_qubits)))\n",
" c += polarity_circ\n",
" return c"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 搭建龙算子"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [],
"source": [
"from mindquantum.core import BARRIER, Z\n",
"\n",
"def L(which, n_qubits, theta, phi):\n",
" U = UN(H, n_qubits)\n",
" R0 = change_phase_with_anclia(0, n_qubits, theta)\n",
" R_t = change_phase_with_anclia(which, n_qubits, phi)\n",
" g_ops = R_t + BARRIER + U + BARRIER + R0 + BARRIER + U + BARRIER\n",
" g_ops += Z.on(n_qubits)\n",
" return g_ops"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 完成量子精确搜索算法：龙算法\n",
"\n",
"这里我们以3比特数据库中搜索$\\left|2\\right>$态为例，完成龙算法。"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": "",
"text/plain": [
""
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import numpy as np\n",
"from mindquantum.core import UN, H\n",
"n_qubits = 3\n",
"will_find = 2\n",
"beta = np.arcsin(np.sqrt(1 / 2**n_qubits))\n",
"Js = int((np.pi / 2 - beta) / 2 / beta)\n",
"theta = 2 * np.arcsin(np.sin(np.pi / (4 * Js + 6)) / np.sin(beta))\n",
"phi = theta\n",
"\n",
"g = L(will_find, n_qubits, theta, phi) # 构建用于精确搜索的龙算子\n",
"\n",
"circ = UN(H, n_qubits) + X.on(n_qubits)\n",
"for i in range(Js + 1):\n",
" circ += g\n",
"circ.svg()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"接下来，我们计算线路的量子态。"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(0.04870813668458639-0.9988130542903j)¦1010⟩\n"
]
}
],
"source": [
"print(circ.get_qs(ket=True))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"发现，除去相位，我们可以精确的得到目标态。通过采样，我们也可以得到如下类似的结果。"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": "",
"text/plain": [
""
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from mindquantum.simulator import Simulator\n",
"from mindquantum.core import Measure\n",
"\n",
"sim = Simulator('projectq', circ.n_qubits)\n",
"res = sim.sampling(circ + UN(Measure(), circ.n_qubits), shots=100)\n",
"res.svg()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"若想查询更多关于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.\n",
"\n",
"\\[3\\] Long G L. Grover algorithm with zero theoretical failure rate. Physical Rev A, 2001, 64: 022307."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3.8.8 ('base')",
"language": "python",
"name": "python3"
},
"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.8"
},
"vscode": {
"interpreter": {
"hash": "d62cf896b9ca57de08105ce3983377439eacacf6f6599f9150bf400edf4fa4b8"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}