tutorials/mbqc/Pattern_CN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# MBQC 模型加速量子电路模拟\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ],
   "metadata": {
    "tags": []
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 概述\n",
    "\n",
    "量子计算利用量子世界中特有的运行规律，为我们提供了一条全新的并且非常有前景的信息处理方式。在当下，量子计算机仍处于研发中的初级阶段，其制造、运行和维护的成本极其昂贵。幸运的是，使用经典计算机模拟量子算法的方式足以满足大部分的科研和教学等需求。2012 年 John Preskill 提出 “量子计算优越性”（又称 “量子霸权”）这一概念，揭起了量子算法与经典算法性能大比拼的序幕 [1,2]。在各界科研团队竞相宣告“量子优越性”实现的同时，也有越来越多的人关注如何使用经典计算机和特殊的优化算法完成对量子计算机的模拟，进而挑战这些量子计算设备的“霸权地位”。不论是科学研究还是教学应用，如何提高经典计算机对量子计算机的模拟能力是一个备受关注的问题。\n",
    "\n",
    "我们在使用经典计算机模拟量子算法时，通常使用列向量来描述和存储量子态。单比特的量子态需要长度为 $2 \\times 1$ 大小的列向量来存储，$n$ 比特的量子态则需要长度为 $2^n \\times 1$ 大小的列向量来存储。由于列向量的长度会随着比特数的增加呈指数增长，当比特数较大时，经典计算机很难去存储和模拟计算。当下现有的量子电路模拟方式最多能支持模拟几十个量子比特的算法。解决这个瓶颈问题的思路之一是通过改变数据结构来改变量子态的存储方式，目前主流的可以用于替换量子态列向量的数据结构有决策图，张量网络（包括矩阵乘积态）等，每一种存储结构对应一种量子电路的模拟方式。然而，这些模拟方式始终都停留在**量子电路模型 (quantum circuit model)** 的讨论框架中。\n",
    "\n",
    "解决上述内存和计算资源消耗问题的另一个思路便是跳出量子电路模型的框架，尝试使用另一种等价模型来完成计算。**基于测量的量子计算模型 (measurement based quantum computation, MBQC)** [3-6]自提出后，以其独特的运算过程备受关注。如[MBQC 入门介绍](MBQC_CN.ipynb)中所讲，对于无依赖关系的测量，物理实现上可以同时进行，经典模拟上则可以通过优化执行顺序来降低实际参与运算的比特数量，从而减少内存消耗和计算量。\n",
    "\n",
    "本教程将会介绍如何利用 MBQC 模型，并依据其测量执行顺序的多样性对其进行优化，最终提高对应量子电路的模拟效率。同时，我们也将会介绍基于该模拟思路所开发的 MBQC 电路模块和翻译模块的使用方法。"
   ],
   "metadata": {
    "tags": []
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 量子电路模拟\n",
    "\n",
    "本教程提出的量子电路模拟的思路主要分为以下三个步骤，每个步骤有其需要调用的模块。每个模块对应的核心类及对应实现的功能，如表 1 所示：\n",
    "\n",
    "|步骤|调用的模块|实例化类|实现的功能|\n",
    "|:---:|:---:|:---:|:---:|\n",
    "|构造量子电路|``qobject`` 模块| `Circuit` 类|输入量子电路信息（包含量子门和测量信息）|\n",
    "|翻译和优化|``mcalculus`` 模块| `MCalculus` 类|将量子电路翻译成 MBQC 模型并进行优化处理|\n",
    "|模拟执行|``simulator`` 模块| `MBQC`类|模拟执行翻译后得到的模型并获得其运算结果|\n",
    "\n",
    "<div style=\"text-align:center\">表 1：本教程提出的量子电路模拟思路 </div>\n",
    "\n",
    "以下我们对这三个步骤分别做出详细的说明和对应的代码演示。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 构造量子电路\n",
    "\n",
    "在 MBQC 工具包的``qobject``中，我们设置了 ``Circuit`` 类，用于记录和存储用户输入的量子门和测量信息。为了让模型更加直观，便于大家接受和使用，我们在实例化该类之后，通过调用类方法来搭建属于自己的量子电路。在搭建量子门时，调用类方法的格式类似于量桨中我们熟悉的 [UAnsatz](https://qml.baidu.com/api/paddle_quantum.circuit.uansatz.html) 电路，大家可以参考[量桨上的教程及示例](https://qml.baidu.com/quick-start/quantum-neural-network.html)类比学习。如图 1 所示，我们使用一个简单的例子，来向大家展示 ``Circuit`` 类的使用方法。\n",
    "\n",
    "![Circuit example](./figures/mbqc-fig-pat-cir-intro.png)\n",
    "<div style=\"text-align:center\">图 1: 一个简单的量子电路图示例 </div>\n",
    "\n",
    "其中，$Ry$ 代表一个绕 y 轴的单比特旋转门，双比特量子门为 $CNOT$ 门，初始态为 $|0\\rangle$ 态。用 ``Circuit`` 类搭建该量子电路的代码实现如下："
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "# 引入需要的计算模块\n",
    "from numpy import pi, random\n",
    "from paddle import to_tensor\n",
    "\n",
    "# 引入需要的 Circuit 模块\n",
    "from paddle_quantum.mbqc.qobject import Circuit\n",
    "\n",
    "# 设置角度参数 theta \n",
    "theta = random.rand(4) * 2 * pi \n",
    "    \n",
    "# 将 Numpy array 转换成 Paddle 中的 Tensor\n",
    "theta = to_tensor(theta, dtype='float64')\n",
    "\n",
    "# 初始化量子电路\n",
    "qubit_number = 2\n",
    "cir = Circuit(qubit_number)\n",
    "\n",
    "# 添加 Ry 旋转门\n",
    "cir.ry(theta[0], 0)\n",
    "cir.ry(theta[1], 1)\n",
    "\n",
    "# 添加 CNOT 门\n",
    "cir.cnot([0, 1])\n",
    "\n",
    "# 添加 Ry 旋转门\n",
    "cir.ry(theta[2], 0)\n",
    "cir.ry(theta[3], 1)"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "然后，我们输入量子电路中的测量信息。\n",
    "\n",
    "**注意**：用``Circuit`` 输入测量的方式与 ``UAnsatz`` 电路不同！ ``Circuit`` 类需要在执行运算之前就需要调用 ``.measure`` 方法输入测量比特信息，而 ``UAnsatz`` 是在运行完量子电路之后调用 ``.measure`` 方法，对输出的量子态进行测量。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "# 输入测量比特的信息\n",
    "# 默认对电路中的所有比特进行测量\n",
    "cir.measure()"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "接下来，我们需要将该电路传递给 MBQC 翻译模块进行翻译和优化。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 翻译和优化\n",
    "\n",
    "翻译过程的主要逻辑参考文献 [7,8]，感兴趣的朋友可以自行学习文献中的细节，在此我们仅简要阐述翻译的思路及其代码实现。\n",
    "\n",
    "我们在 [MBQC 入门介绍](MBQC_CN.ipynb)中提及了 MBQC 模型的 \"EMC\" 语言，这里我们简单回顾一下。我们把由电路模型翻译得到的 MBQC 模型称为该电路模型对应的**模式 (pattern)** ，把由电路中的单个量子门或对输出态的单个测量翻译得到的 MBQC 模型称为该量子门或测量对应的**子模式 (subpattern)** [7]。量子电路的翻译过程实际上就是对所有量子门和所有电路测量进行逐一翻译、标准化、化简和优化的过程，具体来讲分为以下三步：\n",
    "\n",
    "- 逐一翻译：将电路中的每一个量子门和测量逐一翻译为对应的子模式\n",
    "- 标准化：将所有翻译后得到的子模式整合为一个标准化的模式，构成电路模型对应的模式\n",
    "- 化简和优化：对模式中的测量命令进行化简和优化\n"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "代码实现上，我们提供了 ``MCalculus`` 类来完成由电路模型到 MBQC 模型的具体翻译和优化任务。通过调用 ``set_circuit`` 方法可以将我们构造好的量子电路 ``cir`` 传递到 ``MCalculus`` 类中。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "# 引入需要的翻译和优化模块\n",
    "from paddle_quantum.mbqc.mcalculus import MCalculus\n",
    "\n",
    "# 实例化 MCalculus 类\n",
    "mc = MCalculus()\n",
    "\n",
    "# 将电路信息传递到 MCalculus 中\n",
    "mc.set_circuit(cir)"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### 逐一翻译\n",
    "我们先将每个量子门翻译为对应的 MBQC 子模式。根据 [MBQC 入门介绍](MBQC_CN.ipynb)，MBQC 的标准“三步走”流程和 \"EMC\" 语言等价。对于 MBQC 模型下实现 $R_y$ 门，我们可以将“三步走”流程的每个步骤与 “EMC” 命令对应起来，如表 2 所示：\n",
    "\n",
    "|“三步走”流程的步骤| 对应的 \"EMC\" 命令|\n",
    "|:---|:---|\n",
    "|**量子图态准备** <br/> 在节点 $1$ 处输入初始量子态，<br/> 在节点 $2,3,4,5$ 处初始化量子态为 $\\lvert+\\rangle$, <br/> 对相邻比特作用控制 Z 门。| **纠缠命令** <br/> $E_{12}E_{23}E_{34}E_{45}$|\n",
    "|**单比特测量** <br/> 对节点 $1$ 执行 $XY$ 平面测量 $M_1$，测量角度为 $\\frac{\\pi}{2}$，测量结果为 $s_1$；<br/>对节点 $2$ 执行 $XY$ 平面测量 $M_2$，测量角度为 $(-1)^{s_1 + 1}\\alpha$，测量结果为 $s_2$；<br/>对节点 $3$ 执行 $XY$ 平面测量 $M_3$，测量角度为 $-\\frac{\\pi}{2} + (s_1+s_2)\\pi$，测量结果为 $s_3$；<br/>对节点 $4$ 执行 $XY$ 平面测量 $M_4$，测量角度为 $s_2\\pi$，测量结果为 $s_4$。|**测量命令** <br/> $M_1M_2M_3M_4$|\n",
    "|**副产品纠正** <br/> 分别对节点 $5$ 执行 $X$ 副产品纠正，纠正算符 $X^{s_4}$ 和 $Z$ 副产品纠正命令，纠正算符 $Z^{s_3}$。| **副产品纠正命令** <br/> $X_5Z_5$|\n",
    "\n",
    "<div style=\"text-align:center\">表 2：MBQC 实现 Ry 的“三步走”流程与 “EMC” 命令的对应关系</div>\n",
    "\n",
    "我们将上述所有命令按照先后顺序从左到右排列起来，拼接成一个命令列表 \\[$E_{12}E_{23}E_{34}E_{45}M_1M_2M_3M_4X_5Z_5$\\]，其中各命令里包含了详细的参数信息，本教程为了表述简洁未明确写出。我们只需要从左至右执行对应的命令就完成了 MBQC 模型的运算过程。\n",
    "\n",
    "\n",
    "类似地，$CNOT$ 门对应子模式的命令列表为 \\[$E_{12}E_{23}E_{24}M_1 M_2 X_4 Z_3 Z_4$\\]。电路模型中，对输出量子态的单个比特进行测量的过程，也就是 MBQC 模型中对应输出节点进行 $Z$ 测量的过程。因此，电路模型中的单个测量步骤对应的子模式，就是对输出比特执行 $Z$ 测量的命令，用命令列表 \\[$M_1$\\] 来表示。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "我们设置了内部方法 ``__to_subpattern`` 来实现量子门和测量的翻译（该类方法中记录了所有逻辑门和测量的子模式信息；对于熟悉 MBQC 模型的朋友来说，如果希望自定义设计每个子模式，也可以直接加入其中）。当所有的量子门和测量的子模式翻译完成后，所有信息会存储在一个叫**原始模式（wild pattern）** 的变量中，便于后续的整合和处理。\n",
    "\n",
    "![Wild pattern](./figures/mbqc-fig-wild_pat.jpg)\n",
    "<div style=\"text-align:center\">图 2: 对量子门和测量进行逐一翻译生成原始模式 </div>"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### 标准化\n",
    "我们有了原始模式之后，下一步就是通过**标准化（standardization）** 操作获取整个电路对应的**标准模式（standard pattern）**。所谓标准化就是把原始模式中的所有命令按纠缠命令、测量命令和副产品纠正命令的先后顺序重新排列。\n",
    "\n",
    "**注意**：标准化中的顺序交换的过程是不平凡的，每相邻两个命令的顺序交换需要满足特定的规则 [7]。\n",
    "\n",
    "![Standard pattern](./figures/mbqc-fig-pat_std.jpg)\n",
    "<div style=\"text-align:center\">图 3: 原始模式标准化为标准模式 </div>"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "代码实现上，我们提供了 ``standardize`` 类方法用于实现对命令列表的标准化处理和对子模式的整合。调用方式如下："
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "# 标准化\n",
    "mc.standardize()"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### 化简和优化\n",
    "在获得电路模型对应的标准模式之后，我们便可以直接将该模式返回并接入 MBQC 模拟模块中运行了。但是，考虑到翻译得到的模式并不唯一，我们可以通过一些化简和优化技巧找到更优的模式（类似于寻找更简化的等价电路图），再使用 MBQC 模拟模块运行，以此减少内存消耗和计算时间，提高运算效率。一方面，测量命令对其他节点测量结果的依赖性越强，实际参与运算的比特数就越多，因此我们可以通过尽可能简化测量命令对其他测量结果的依赖关系，减少实际运算所需的比特数；另一方面，无依赖关系的测量命令在模拟上可以交换顺序而不影响测量结果，因此我们也可以通过优化测量命令的顺序来减少模拟过程的计算量。\n",
    "\n",
    "基于上述两点考虑，我们将使用**信号转移**操作来简化测量命令对其他测量结果的依赖关系，另用**基于行序优先原则的优化算法**来优化测量命令的顺序。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "**信号转移**\n",
    "\n",
    "信号转移是针对测量命令的依赖关系进行化简的过程。简单来说，对于测量命令中的某类依赖关系，我们可以将其从测量命令中拆分出来，从而对命令进行简化 [7]。代码实现上，我们提供了 ``shift_signals`` 类方法来实现信号转移操作。调用方式如下："
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "# 信号转移\n",
    "mc.shift_signals()"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "**基于行序优先原则的优化算法**\n",
    "\n",
    "基于行序优先原则的优化算法是我们自研的一类算法，该算法的初衷是希望按照行序优先的原则逐行对节点进行测量。按照这种测量方式，当该行节点都被测量之后，我们可以完全删除该行的信息，从而减小后续参与运算的比特数。在原先的电路模型中，该算法对应于按行执行量子门及测量。实验观察到，行序优先原则的优化算法可以有效优化浅层量子电路对应测量模式中的测量命令的顺序（其优势见下文）。\n",
    "\n",
    "代码实现上，我们提供了 ``optimize_by_row`` 类方法来实现基于行序优先原则的优化算法。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "# 测量顺序优化\n",
    "mc.optimize_by_row()"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "对测量命令进行化简和优化之后，便结束了我们全部的翻译过程。我们可以调用 ``get_pattern`` 类方法返回翻译得到的 MBQC 测量模式。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "# 返回处理后的 MBQC 模式\n",
    "pattern = mc.get_pattern()"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 模拟执行\n",
    "\n",
    "在获得翻译、化简和优化的模式之后，我们就可以使用 MBQC 模拟模块来执行该模式了。实例化 `MBQC` 类后，我们可以通过调用类方法 `set_pattern` 将模式信息传入模拟模块中，并通过调用类方法 `run_pattern` 执行运算过程，最后获得相应的运算结果。代码示例如下："
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "# 引入模拟模块和常用函数\n",
    "from paddle_quantum.mbqc.simulator import MBQC\n",
    "from paddle_quantum.mbqc.qobject import State\n",
    "from paddle_quantum.mbqc.utils import zero_state, kron, div_str_to_float\n",
    "\n",
    "# 实例化 MBQC 模型\n",
    "mbqc = MBQC()\n",
    "\n",
    "# 输入模式信息\n",
    "mbqc.set_pattern(pattern)\n",
    "\n",
    "# 输入初始量子态信息，此处选取为 |0> 态，与电路模型的输入保持一致\n",
    "input_vector = kron([zero_state() for _ in range(qubit_number)])\n",
    "input_system = [0,1]\n",
    "input_state = State(input_vector, input_system)\n",
    "\n",
    "mbqc.set_input_state(input_state)\n",
    "\n",
    "# 按照测量模式进行运算\n",
    "mbqc.run_pattern()\n",
    "\n",
    "# 获得运算后的量子输出\n",
    "quantum_output = mbqc.get_quantum_output()\n",
    "print(\"运算后的量子态为：\", quantum_output)\n",
    "\n",
    "# 获得运算后的经典输出\n",
    "classical_output = mbqc.get_classical_output()\n",
    "print(\"运算后的经典输出结果为：\", classical_output)"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "至此，我们便实现了电路模拟的全部过程。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 函数 “simulate_by_mbqc”\n",
    "\n",
    "为了方便使用，除了 `MBQC` 类之外，我们在 MBQC 模拟模块中单独提供了一个函数 ``simulate_by_mbqc``。我们通过调用 ``Circuit`` 类构造量子电路，之后直接调用 ``simulate_by_mbqc`` 来模拟运行。该函数可以将量子电路自动翻译为 MBQC 模型并执行运行，最后输出等价于量子电路模型的经典采样结果或量子态向量。下面我们对图 1 中的电路图，给出完整的使用示例。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "# 引入需要的通用计算模块\n",
    "from numpy import random, pi\n",
    "from paddle import to_tensor\n",
    "\n",
    "# 引入需要的 utils 模块\n",
    "from paddle_quantum.mbqc.utils import random_state_vector\n",
    "# 引入需要的 Circuit 模块\n",
    "from paddle_quantum.mbqc.qobject import Circuit\n",
    "# 引入模拟模块\n",
    "from paddle_quantum.mbqc.simulator import simulate_by_mbqc\n",
    "\n",
    "# 设置角度参数 theta \n",
    "theta = random.rand(4) * 2 * pi \n",
    "    \n",
    "# 我们需要将 Numpy array 转换成 Paddle 中的 Tensor\n",
    "theta = to_tensor(theta)\n",
    "\n",
    "# 初始化量子电路\n",
    "qubit_number = 2\n",
    "cir = Circuit(qubit_number)\n",
    "\n",
    "# 添加单比特旋转门\n",
    "cir.ry(theta[0], 0)\n",
    "cir.ry(theta[1], 1)\n",
    "\n",
    "# 添加两比特门\n",
    "cir.cnot([0, 1])\n",
    "\n",
    "# 添加单比特旋转门\n",
    "cir.ry(theta[2], 0)\n",
    "cir.ry(theta[3], 1)\n",
    "\n",
    "# 输入量子测量的信息\n",
    "# 默认对电路中的所有比特进行测量\n",
    "cir.measure()\n",
    "\n",
    "# 构造初始量子态\n",
    "input_vector = random_state_vector(qubit_number)\n",
    "input_system = list(range(qubit_number))\n",
    "input_state = State(input_vector, input_system)\n",
    "\n",
    "# 调用该函数运行量子电路，输入电路、初始量子态\n",
    "classical_output, quantum_output = simulate_by_mbqc(cir, input_state)\n",
    "\n",
    "# 打印运行结果\n",
    "print(\"经典输出为：\", classical_output)\n",
    "print(\"量子输出为：\", quantum_output)"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 示例\n",
    "\n",
    "由于近期小型量子计算机缺乏纠错能力，所以在量子算法设计中，可并行性和电路深度成为很重要的考虑因素。我们希望设计的量子算法具有高度的并行性和较浅的电路深度，以使得量子计算机能尽快地完成算法的执行，从而降低退相干性对计算结果保真度的影响。基于浅层量子电路而设计的量子算法对近期量子计算的发展和落地至关重要。以下我们通过两个示例，展示本教程中电路模拟思路在浅层量子电路模拟上的提升效果。\n",
    "\n",
    "### 谷歌随机量子电路\n",
    "\n",
    "2017年，谷歌设计了一系列[随机量子电路 (GRCS)](https://github.com/sboixo/GRCS)。鉴于该类量子电路的模拟难度，其往往被作为模拟器性能的基准测试案例 [9]。\n",
    "\n",
    "为了展示本教程中模拟思路对量子电路模拟上的实际效果，我们选取了一部分 GRCS 中的浅层电路（特别地，我们选取了一部分**电路深度为 10** 的含 CZ 门的电路），分别使用本教程中的模拟算法和业界最领先的 Qiskit 模拟器中的两种算法（ `statevector` 和 `matrix_product_state`）进行比较。我们选取的具体示例为：\n",
    "\n",
    "|索引|文件名|比特数|\\||索引|文件名|比特数|\\||索引|文件名|比特数|\\||索引|文件名|比特数|\\||索引|文件名|比特数|\n",
    "| :---: | :---: | :---: | :---:| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |:---: |:---: |:---: |\n",
    "|1|inst_5x5_10_0.txt|25|**\\|** | 11|inst_5x6_10_0.txt|30|**\\|**|21|inst_6x6_10_0.txt|36|**\\|**|31|inst_6x7_10_0.txt|42|**\\|**|41|inst_7x7_10_0.txt|49|\n",
    "|2|inst_5x5_10_1.txt|25|**\\|**| 12|inst_5x6_10_1.txt|30|**\\|**|22|inst_6x6_10_1.txt|36|**\\|**|32|inst_6x7_10_1.txt|42|**\\|**|42|inst_7x7_10_1.txt|49|\n",
    "|3|inst_5x5_10_2.txt|25|**\\|**| 13|inst_5x6_10_2.txt|30|**\\|**|23|inst_6x6_10_2.txt|36|**\\|**|33|inst_6x7_10_2.txt|42|**\\|**|43|inst_7x7_10_2.txt|49|\n",
    "|4|inst_5x5_10_3.txt|25|**\\|**| 14|inst_5x6_10_3.txt|30|**\\|**|24|inst_6x6_10_3.txt|36|**\\|**|34|inst_6x7_10_3.txt|42|**\\|**|44|inst_7x7_10_3.txt|49|\n",
    "|5|inst_5x5_10_4.txt|25|**\\|**| 15|inst_5x6_10_4.txt|30|**\\|**|25|inst_6x6_10_4.txt|36|**\\|**|35|inst_6x7_10_4.txt|42|**\\|**|45|inst_7x7_10_4.txt|49|\n",
    "|6|inst_5x5_10_5.txt|25|**\\|**| 16|inst_5x6_10_5.txt|30|**\\|**|26|inst_6x6_10_5.txt|36|**\\|**|36|inst_6x7_10_5.txt|42|**\\|**|46|inst_7x7_10_5.txt|49|\n",
    "|7|inst_5x5_10_6.txt|25|**\\|**| 17|inst_5x6_10_6.txt|30|**\\|**|27|inst_6x6_10_6.txt|36|**\\|**|37|inst_6x7_10_6.txt|42|**\\|**|47|inst_7x7_10_6.txt|49|\n",
    "|8|inst_5x5_10_7.txt|25|**\\|**| 18|inst_5x6_10_7.txt|30|**\\|**|28|inst_6x6_10_7.txt|36|**\\|**|38|inst_6x7_10_7.txt|42|**\\|**|48|inst_7x7_10_7.txt|49|\n",
    "|9|inst_5x5_10_8.txt|25|**\\|**| 19|inst_5x6_10_8.txt|30|**\\|**|29|inst_6x6_10_8.txt|36|**\\|**|39|inst_6x7_10_8.txt|42|**\\|**|49|inst_7x7_10_8.txt|49|\n",
    "|10|inst_5x5_10_9.txt|25|**\\|**| 20|inst_5x6_10_9.txt|30|**\\|**|30|inst_6x6_10_9.txt|36|**\\|**|40|inst_6x7_10_9.txt|42|**\\|**|50|inst_7x7_10_9.txt|49|"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "我们选取 `statevector` 和 `matrix_product_state` 两种算法中时间较短的结果作为 Qiskit 模拟器的运行时间。所有示例均使用具有 16 G 内存和 Intel Core i7 10TH GEN 处理器的普通笔记本运行，结果如图 4 所示。\n",
    "\n",
    "![GRCS plot](./figures/mbqc-fig-GRCS_plot.jpg)\n",
    "<div style=\"text-align:center\">图 4: 不同示例下 Qiskit 与 MBQC 模拟算法运行时间比较 </div>\n",
    "\n",
    "从图中可知，本教程的思路在模拟谷歌随机量子电路时具有运算效率上的显著优势。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 总结\n",
    "\n",
    "通过跳出量子电路模型的框架，本教程给出了一种使用 等价的 MBQC 模型来进行电路模拟的新思路。特别地，对于多比特浅层量子电路的模拟，该思路具有运算效率上的显著优势。我们期待该模拟思路将进一步在量子机器学习和量子神经网络的应用中带来突破。\n",
    "\n",
    "尽管当前我们 MBQC 模拟模块的底层采用量子态向量的数据结构，但是本教程的模拟思路并不依赖于具体计算时的数据存储方式，换句话说，该模拟思路可以与不同的数据结构配合实现。\n",
    "\n",
    "关于量子电路的模拟和 MBQC 模型中的算法开发均有待进一步探索，也欢迎广大量子计算开发者及爱好者加入我们，共同挖掘 MBQC 模型的无限可能！"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "## 参考文献\n",
    "\n",
    "[1] Preskill, John. \"Quantum computing and the entanglement frontier.\" [arXiv preprint arXiv:1203.5813 (2012).](https://arxiv.org/abs/1203.5813)\n",
    "\n",
    "[2] Preskill, John. \"Quantum computing in the NISQ era and beyond.\" [Quantum 2 (2018): 79.](https://quantum-journal.org/papers/q-2018-08-06-79/)\n",
    "\n",
    "[3] Robert Raussendorf, et al. \"A one-way quantum computer.\" [Physical Review Letters 86.22 (2001): 5188.](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.86.5188)\n",
    "\n",
    "[4] Raussendorf, Robert, and Hans J. Briegel. \"Computational model underlying the one-way quantum computer.\" [Quantum Information & Computation 2.6 (2002): 443-486.](https://dl.acm.org/doi/abs/10.5555/2011492.2011495)\n",
    "\n",
    "[5] Robert Raussendorf, et al. \"Measurement-based quantum computation on cluster states.\" [Physical Review A 68.2 (2003): 022312.](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.68.022312)\n",
    "\n",
    "[6] Briegel, Hans J., et al. \"Measurement-based quantum computation.\" [Nature Physics 5.1 (2009): 19-26.](https://www.nature.com/articles/nphys1157)\n",
    "\n",
    "[7] Danos, Vincent, et al. \"The measurement calculus.\" [Journal of the ACM (JACM) 54.2 (2007): 8-es.](https://dl.acm.org/doi/abs/10.1145/1219092.1219096)\n",
    "\n",
    "[8] Broadbent, Anne, and Elham Kashefi. \"Parallelizing quantum circuits.\" [Theoretical computer science 410.26 (2009): 2489-2510.](https://arxiv.org/abs/0704.1736)\n",
    "\n",
    "[9] Boixo, Sergio, et al. \"Characterizing quantum supremacy in near-term devices.\" [Nature Physics 14.6 (2018): 595-600.](https://www.nature.com/articles/s41567-018-0124-x)"
   ],
   "metadata": {}
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "73e152e9b81fe728e387c249fa9090f02d423820fe8ab6018c11ce80df71d553"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.11"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "toc-autonumbering": false,
  "toc-showcode": false,
  "toc-showmarkdowntxt": false,
  "toc-showtags": false,
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}