tutorials/mbqc/MBQC_EN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "# MBQC Quick Start Guide\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Introduction\n",
    "\n",
    "Quantum computation utilizes the peculiar laws in the quantum world and provides us with a novel and promising way of information processing. The essence of quantum computation is to evolve the initially prepared quantum state into another expected one, and then make measurements on it to obtain the required classical results. However, the approaches of quantum state evolution are varied in different computation models. The widely used **quantum circuit model** [1,2] completes the evolution by performing quantum gate operations, which can be regarded as a quantum analog of the classical computing model. In contrast, **measurement-based quantum computation (MBQC)** provides a completely different approach for quantum computing.\n",
    "\n",
    "As its name suggests, the entire evolution in MBQC is completed via quantum measurements. There are mainly two variants of measurement-based quantum computation in the literature: **teleportation-based quantum computing (TQC)** model[3-5] and **one-way quantum computer (1WQC)** model [6-9]. The former requires joint measurements on multiple qubits, while the latter only requires single-qubit measurements. After these two variants were proposed, they were proved to be highly correlated and admit a one-to-one correspondence [10]. So without further declaration, **all of the following discussions about MBQC will refer to the 1WQC model.**\n",
    "\n",
    "MBQC is a unique model in quantum computation and has no classical analog. The model controls the computation by measuring part of the qubits of an entangled state, with those remaining unmeasured undergoing the evolution correspondingly. By controlling measurements, we can complete any desired evolution. The computation in MBQC is mainly divided into three steps. The first step is to prepare a resource state, which is a highly entangled many-body quantum state. This state can be prepared offline and can be independent of specific computational tasks. The second step is to sequentially perform single-qubit measurements on each qubit of the prepared resource state, where subsequent measurements can depend on previous measurement outcomes, that is, measurements can be adaptive. The third step is to perform byproduct corrections on the final state. Finally, we do classical data processing on measurement outcomes to obtain the required computation results. \n",
    "\n",
    "A typical example of MBQC algorithms is shown in Figure 1. The grid represents a commonly used quantum resource state (called cluster state, see below for details). Each vertex on the grid represents a qubit, while the entire grid represents a highly entangled quantum state. We measure each qubit one by one in a specific measurement basis (In the vertices, X, Y, Z, XY, etc. represent the corresponding measurement basis), and then perform byproduct corrections (to eliminate the effect of Pauli X and Pauli Z operators), to complete the computation.\n",
    "\n",
    "![MBQC example](./figures/mbqc-fig-general_pattern.jpg)\n",
    "<div style=\"text-align:center\">Figure 1: A typical example of MBQC algorithm where computation is proceeded by measuring each qubit on the vertex. </div>\n",
    "\n",
    "The \"three-step\" process of MBQC has brought us quantities of benefits. For example, if the quantum state prepared in the first step is too noisy, we can simply discard this state **before computation begins** (that is, before any measurement is implemented), and prepare it again to ensure the accuracy of the computational results. Since the resource state can be prepared offline and independent of specific computing tasks, it can also be applied to secure delegated quantum computation [11,12] to protect clients' privacy. In addition, single-qubit measurement is easier to be implemented in practice than quantum gates. Non-adaptive quantum measurements can even be carried out simultaneously, thereby, reducing the computation depth and requiring less coherence time of the quantum system. The difficulty of realizing MBQC mainly lies in resource state preparation in the first step. Such a quantum state is highly entangled and the number of qubits required is much larger than that of the usual circuit model. For recent progress on the resource state preparation, please refer to [13,14]. Table 1 briefly summarizes both advantages and limitations of MBQC and quantum circuit models.\n",
    "\n",
    "|    | Quantum circuit model     | MBQC model    |\n",
    "|:---: | :---: | :---: |\n",
    "| Pros|  has classical analog <br/> easy to understand <br/> and develop applications | resource state can be prepared offline <br/> easy to implement single-qubit measurement <br/> measurements can be implemented simultaneously <br/> leading to lower implementation depth |\n",
    "|Cons| implementation order fixed <br/> depth restricted by coherence time| no classical analog thus super-intuitive <br/> resource state requires a large number of qubits <br/> thus hard to prepare in practice| \n",
    "\n",
    "<div style=\"text-align:center\">Table 1: Advantages and limitations of MBQC and quantum circuit models </div>\n",
    "\n",
    "Since MBQC does not have a classical analog, it may be difficult for beginners to understand it intuitively. However, it is this super-intuitive approach that brings a wide range of opportunities to explore the unknowns. So, let's dive into the world of MBQC and explore the mysteries together!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Prerequisites\n",
    "\n",
    "Before introducing MBQC and our module in more detail, let's briefly review the two building blocks of MBQC.\n",
    "\n",
    "### 1. Graph and graph state\n",
    "    \n",
    "Given a graph $G=(V, E)$ with vertices set $V$ and edges set $E$, we can prepare an entangled quantum state by initializing a plus state $|+\\rangle = (|0\\rangle + |1\\rangle) / \\sqrt{2}$ to each vertex of $G$ and performing a control Z operation $CZ = |0\\rangle\\langle 0| \\otimes I + |1\\rangle\\langle1|\\otimes Z$ between each connected qubit pair. The resulting quantum state is called the **graph state** of $G$, denoted by $|G\\rangle$, such that:\n",
    "    \n",
    "$$\n",
    "|G\\rangle = \\prod_{(a,b) \\in E} CZ_{ab} \\left(\\bigotimes_{v \\in V}|+\\rangle_v\\right). \\tag{1}\n",
    "$$\n",
    "\n",
    "The concept of graph state is nothing particular. Actually, the well-known Bell state and GHZ state are both graph states up to local unitary transformations. Besides, if the underlying graph we consider is a 2D grid then the corresponding graph state is called **cluster state**, depicted in Figure 2.\n",
    "\n",
    "![Graph states](./figures/mbqc-fig-graph_states.jpg)\n",
    "<div style=\"text-align:center\">Figure 2：(i) the graph of a $Bell$ state; (ii) the graph of a 4-qubit $GHZ$ state; (iii) the graph of a cluster state </div>\n",
    "\n",
    "### 2. Projective measurement\n",
    "\n",
    "Quantum measurement is one of the main concepts in quantum information processing. In the circuit model, measurements are performed usually at the end of the circuit to extract classical results from the quantum state. However, in MBQC, quantum measurements are also used to drive the computation. In the MBQC model, we use single-qubit measurements by default and mainly use 0/1 projection measurement. According to Born's rule [17], given a projective measurement basis $\\{|\\psi_0\\rangle, |\\psi_1\\rangle\\}$ and a quantum state $|\\phi\\rangle$, the probability that the outcome $s \\in \\{0,1\\}$ occurs is given by $p(s) = |\\langle \\psi_s|\\phi\\rangle|^2$, and the corresponding post-measurement state is $| \\psi_s\\rangle\\langle\\psi_s|\\phi\\rangle / \\sqrt{p(s)}$. In other words, the state of the measured qubit collapses into $|\\psi_s\\rangle$, while the state of other qubits evolves to $\\langle\\psi_s|\\phi\\rangle / \\sqrt{p(s)}$.\n",
    "\n",
    "Single-qubit measurements are commonly used, especially the binary projective measurements on the $XY$, $YZ$ and $XZ$ planes, defined respectively by the following orthonormal bases,\n",
    "\n",
    "- XY-plane measurement: $M^{XY}(\\theta) = \\{R_z(\\theta) |+\\rangle, R_z(\\theta) |-\\rangle \\}$, reducing to $X$ measurement if $\\theta = 0$ and $Y$ measurement if $\\theta = \\frac{\\pi}{2}$;\n",
    "\n",
    "- YZ-plane measurement: $M^{YZ}(\\theta) = \\{R_x(\\theta)|0\\rangle, R_x(\\theta)|1\\rangle\\}$, reducing to $Z$ measurement if $\\theta = 0$;\n",
    "\n",
    "- XZ-plane measurement: $M^{XZ}(\\theta) = \\{R_y(\\theta)|0\\rangle, R_y(\\theta)|1\\rangle\\}$, reducing to $Z$ measurement if $\\theta = 0$.\n",
    "\n",
    "In the above definitions, we use $|+\\rangle = (|0\\rangle + |1\\rangle)/ \\sqrt{2},|-\\rangle = (|0\\rangle - |1\\rangle)/ \\sqrt{2}$, and $R_x, R_y, R_z$ are rotation gates around $x,y,z$ axes respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## MBQC Module Framework\n",
    "\n",
    "\n",
    "### 1. Model and code implementation\n",
    "\n",
    "#### \"Three-step\" process\n",
    "\n",
    "As is mentioned above, MBQC is different from the quantum circuit model. The computation in MBQC is driven by measuring each qubit on a graph state. To be specific, the MBQC model consists of the following three steps.\n",
    "\n",
    "- **Graph state preparation**: that is, to prepare a many-body entangled state. Given vertices and edges in a graph, we can prepare a graph state by initializing a plus state on each vertex and performing a control Z operation between each connected qubit pair. Since a graph state and its underlying graph have a one-to-one correspondence, it suffices to work with the graph only. In addition, we can selectively replace some of the plus states in the graph with a customized input state if necessary.\n",
    "\n",
    "- **Single-qubit measurement**: that is, to perform single-qubit measurements on the prepared graph state with specific measurement bases. The measurement angles can be adaptively adjusted according to previous outcomes. Non-adaptive measurements commute with each other in simulation and can even be performed simultaneously in experiments. \n",
    "\n",
    "- **Byproduct correction**: Due to the random nature of quantum measurement, the evolution of the unmeasured quantum state cannot be uniquely determined. In other words, the unmeasured quantum state may undergo some extra evolutions, called **byproducts**. So the last step is to correct these to obtain the expected result. If the final output is not a quantum state but the measurement outcomes, it suffices to eliminate the effect of byproducts via classical data processing only.\n",
    "\n",
    "In conclusion, the \"three-step\" process of MBQC includes graph state preparation, single-qubit measurement, and byproduct correction. The first two steps are indispensable while the implementation of the third step depends on the form of expected results.\n",
    "\n",
    "#### Measurement pattern and \"EMC\" language\n",
    "\n",
    "Besides the \"three-step\" process, an MBQC model can also be described by the **EMC** language from the measurement calculus [18]. As is mentioned above, MBQC admits a one-to-one correspondence to the circuit model. We can usually call the MBQC equivalent of a quantum circuit as a measurement **pattern** while the equivalent of a specific gate/measurement is called **subpattern** [18]. In the \"EMC\" language, we usually call an entanglement operation \"an entanglement command\", denoted by \"E\"; call a measurement operation \"a measurement command\", denoted by \"M\"; call a byproduct correction operation \"a byproduct correction command\", denoted by \"C\". Therefore, in parallel with the\"three-step\" process, MBQC is also characterized by an \"EMC\" command list. The process of computation is to execute commands in the command list in order. However, to familiarize ourselves with MBQC quickly, we will adopt the conventional \"three-step\" process to describe MBQC in this tutorial. In a later tutorial [Speeding up quantum circuit simulation by MBQC](/tutorials/measurement-based-quantum-computation/speeding-up-quantum-circuit-simulation-by-mbqc.html), we will use the \"EMC\" language instead as it is more friendly for specific calculations. It should be noted that the \"three-step\" process and the \"EMC\" language are essentially the same things with different denotations.\n",
    "\n",
    "#### Code implementation\n",
    "\n",
    "In terms of code implementation, we provide a simulation module ``simulator`` that mainly consists of a class `MBQC` with attributes and methods necessary for MBQC simulation. We can instantiate an MBQC class, create and perform our MBQC-based algorithms with it.\n",
    "\n",
    "```python\n",
    "# code implementation\n",
    "from paddle_quantum.mbqc.simulator import MBQC\n",
    "\n",
    "class MBQC:\n",
    "    def __init__():\n",
    "        ...\n",
    "```\n",
    "\n",
    "After instantiation, we can call class methods step by step to complete the MBQC computation process. Here, we briefly introduce some frequently used methods and their functionalities in Table 2. Please refer to the API documentation for details.\n",
    "\n",
    "|MBQC class method|Functionality|\n",
    "|:---:|:---:|\n",
    "|set_graph|input a graph for MBQC|\n",
    "|set_pattern|input a measurement pattern for MBQC|\n",
    "|set_input_state|input initial quantum state|\n",
    "|draw_process|draw the dymanical process of MBQC computation|\n",
    "|track_progress|track the running progress of MBQC computation|\n",
    "|measure|perform single-qubit measurement|\n",
    "|sum_outcomes|sum outcomes of the measured qubits|\n",
    "|correct_byproduct|correct byproduct operators|\n",
    "|run_pattern|run the input measurement pattern|\n",
    "|get_classical_output|return classical results|\n",
    "|get_quantum_output|return quantum results|\n",
    "\n",
    "<div style=\"text-align:center\">Table 2: Frequently used methods of the class MBQC and their functionalities </div>\n",
    "<br/>\n",
    "\n",
    "In the ``simulator`` module, we provide two simulation modes, \"graph\" and \"pattern\", corresponding to the two equivalent descriptions of the MBQC computation process respectively. If we set a graph, the whole computation needs to follow the \"three-step\" process. It is worth mentioning that we design a **vertex dynamic classification algorithm** to simulate the MBQC computation process efficiently. Roughly speaking, we integrate the first two steps of the process, change the execution order of entanglement and measurement operations automatically to reduce the number of effective qubits involved in the computation and thereby improve the efficiency. The outline to use the simulation module is as follows:\n",
    "\n",
    "```python\n",
    "\"\"\"\n",
    "MBQC simulation module usage (set a graph and proceed with the \"three-step\" process)\n",
    "\"\"\"\n",
    "from paddle_quantum.mbqc.simulator import MBQC\n",
    "\n",
    "# Instantiate MBQC and create an MBQC model\n",
    "mbqc = MBQC()\n",
    "\n",
    "# First step of the \"three-step\" process, set a graph\n",
    "mbqc.set_graph(graph)\n",
    "\n",
    "# Set an initial input state (optional)\n",
    "mbqc.set_input_state(input_state)\n",
    "\n",
    "# Second step of the \"three-step\" process, perform single-qubit measurements\n",
    "mbqc.measure(which_qubit, basis)\n",
    "mbqc.measure(which_qubit, basis)\n",
    "......\n",
    "\n",
    "# Third step of the \"three-step\" process, correct byproducts\n",
    "mbqc.correct_byproduct(gate, which_qubit, power)\n",
    "\n",
    "# Obtain the classical and quantum outputs\n",
    "classical_output = mbqc.get_classical_output()\n",
    "quantum_output = mbqc.get_quantum_output()\n",
    "```\n",
    "\n",
    "If we set a pattern to the ``MBQC`` class, we need to call the `run_pattern` method to complete the simulation.\n",
    "\n",
    "```python\n",
    "\"\"\"\n",
    "MBQC simulation module usage (set a pattern and simulate by \"EMC\" commands)\n",
    "\"\"\"\n",
    "from paddle_quantum.mbqc.simulator import MBQC\n",
    "\n",
    "# Instantiate MBQC and create an MBQC model\n",
    "mbqc = MBQC()\n",
    "\n",
    "# Set a measurement pattern\n",
    "mbqc.set_pattern(pattern)\n",
    "\n",
    "# Set an initial input state (optional) \n",
    "mbqc.set_input_state(input_state)\n",
    "\n",
    "# Run the measurement pattern\n",
    "mbqc.run_pattern()\n",
    "\n",
    "# Obtain the classical and quantum outputs\n",
    "classical_output = mbqc.get_classical_output()\n",
    "quantum_output = mbqc.get_quantum_output()\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After going through the above introduction, I am sure you already have a basic understanding of MBQC and our simulation module. Now, let's do some combat exercises with the following two examples!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Example: general single-qubit unitary gate in MBQC\n",
    "\n",
    "For a general single-qubit unitary gate $U$, it can be decomposed to $ U = R_x(\\gamma)R_z(\\beta)R_x(\\alpha)$ up to a global phase [17]. In MBQC, this unitary gate can be realized in the following way [15]. As shown in Figure 3: prepare five qubits, with input on the leftmost qubit while output on the rightmost qubit; input a state $|\\psi\\rangle$ and initialize other qubits with $|+\\rangle$; apply a $CZ$ operation to each connected qubit pair; perform $X$-measurement on the first qubit and adaptive measurements in the $XY$-plane on the middle three qubits, with the four measured qubits' outcomes recorded as $s_1$, $s_2$, $s_3$, $s_4$; correct byproducts to the state on qubit $5$ after all measurements. Then, the output state on qubit 5 will be $U|\\psi\\rangle$.\n",
    "\n",
    "\n",
    "![Single qubit pattern](./figures/mbqc-fig-single_qubit_pattern_EN.jpg)\n",
    "<div style=\"text-align:center\">Figure 3: Realizing a general single-qubit unitary gate in MBQC </div>\n",
    "\n",
    "**Note**: after measuring the first four qubits, state on qubit $5$ has the form of $X^{s_2 + s_4}Z^{s_1 + s_3} U|\\psi\\rangle$, where $X^{s_2 + s_4}$ and $Z^{s_1 + s_3}$ are the so-called byproducts. We need to correct them according to the measurement outcomes to get the desired state of $U|\\psi\\rangle$.\n",
    "\n",
    "Here is the code implementation:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  Import relevant modules\n",
    "\n",
    "We first import two common modules `numpy` and `paddle`. Then we need to import the MBQC simulation module ``simulator`` which mainly contains the class ``MBQC``. We can instantiate this class and create an MBQC model. We also need to import the ``qobject`` module which contains quantum objects that are frequently used in quantum information processing (e.g. ``State``, ``Circuit``, ``Pattern``). Finally, we import the ``utils`` module that provides commonly used functions (e.g. ``plus_state``, ``basis`` etc.). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import common calculation modules\n",
    "from numpy import pi\n",
    "from paddle import to_tensor, matmul\n",
    "# Import relevant modules for MBQC simulation\n",
    "from paddle_quantum.mbqc.simulator import MBQC\n",
    "from paddle_quantum.mbqc.qobject import State\n",
    "from paddle_quantum.mbqc.utils import rotation_gate, basis, random_state_vector, compare_by_vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Set graph and state\n",
    "\n",
    "Then, we can set the graph on our own. For this instance in Figure 3, we need five vertices (recorded as `['1', '2', '3', '4', '5']`) and four edges (recorded as  (`[('1', '2'), ('2', '3'), ('3', '4'), ('4', '5')]`)). We need to set an input the state on vertex `'1'` and initialize measurement angles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Construct the underlying graph\n",
    "V = ['1', '2', '3', '4', '5']\n",
    "E = [('1', '2'), ('2', '3'), ('3', '4'), ('4', '5')]\n",
    "G = [V, E]\n",
    "# Generate a random state vector\n",
    "input_psi = random_state_vector(1)\n",
    "# Construct a quantum state on vertex '1'\n",
    "input_state = State(input_psi, ['1'])\n",
    "# Initialize measurement angles of type Tensor\n",
    "alpha = to_tensor([pi / 6], dtype='float64')\n",
    "beta  = to_tensor([pi / 4], dtype='float64')\n",
    "gamma = to_tensor([pi / 3], dtype='float64')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  Instantiate an MBQC model\n",
    "\n",
    "Then we can construct our own MBQC model by instantiating the class `MBQC` and setting the graph and input state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instantiate MBQC\n",
    "mbqc = MBQC()\n",
    "# Set the graph\n",
    "mbqc.set_graph(G)\n",
    "# Set the input state\n",
    "mbqc.set_input_state(input_state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we perform measurements on the first four vertices."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  Measure the first vertex\n",
    "\n",
    "As shown in Figure 3, we perform $X$-measurement on the first vertex, that is, the measurement in $XY$-plane with an angle of $\\theta_1 = 0$。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate the angle for the first measurement\n",
    "theta1 = to_tensor([0], dtype='float64')\n",
    "# Measure the first vertex\n",
    "mbqc.measure('1', basis('XY', theta1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Measurement on the first vertex is straightforward because it is not adaptive. However, things will be tougher to the second, third, and fourth vertices, as the measurement angles are set adaptively according to the previous measurement outcomes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  Measure the second vertex\n",
    "\n",
    "As shown in Figure 3, the measurement on the second vertex has a form of $M^{XY}(\\theta_2)$, where\n",
    "\n",
    "$$\n",
    "\\theta_2 = (-1)^{s_1 + 1} \\alpha, \\tag{2}\n",
    "$$\n",
    "\n",
    "This is a measurement in the $XY$-plane with an adaptive angle $(-1)^{s_1 + 1} \\alpha$, where $s_1$ is the outcome of the first vertex. \n",
    "\n",
    "There is a method `sum_outcomes` in the class `MBQC` to calculate the summation of outcomes for vertices in the first argument. If we want to add an extra value \"$x$\" on top of the summation, we can set the second argument to be $x$.Otherwise, the default value of the second argument is $0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate the angle for the second measurement\n",
    "theta2 = to_tensor((-1) ** mbqc.sum_outcomes(['1'], 1), dtype='float64') * alpha\n",
    "# Measure the second vertex\n",
    "mbqc.measure('2', basis('XY', theta2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  Measure the third vertex\n",
    "\n",
    "As shown in Figure 3, the measurement on the third vertex has a form of $M^{XY}(\\theta_3)$, where\n",
    "\n",
    "$$\n",
    "\\theta_3 = (-1)^{s_2 + 1} \\beta, \\tag{3}\n",
    "$$\n",
    "\n",
    "This is a measurement in the $XY$-plane with an adaptive angle $(-1)^{s_2 + 1} \\beta$, where $s_2$ is the outcome of the second vertex."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate the angle for the third measurement\n",
    "theta3 = to_tensor((-1) ** mbqc.sum_outcomes(['2'], 1), dtype='float64') * beta\n",
    "# Measure the third vertex\n",
    "mbqc.measure('3', basis('XY', theta3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Measure the fourth vertex\n",
    "\n",
    "As shown in Figure 3, the measurement on the fourth vertex has a form of $M^{XY}(\\theta_4)$, where\n",
    "\n",
    "$$\n",
    "\\theta_4 = (-1)^{s_1 + s_3 + 1} \\gamma, \\tag{4}\n",
    "$$\n",
    "\n",
    "This is a measurement in the $XY$-plane with an adaptive angle $(-1)^{s_1 + s_3 + 1} \\gamma$, where $s_1$ and $s_3$ are respectively the outcomes of the first and the third vertices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate the angle for the fourth measurement\n",
    "theta4 = to_tensor((-1) ** mbqc.sum_outcomes(['1', '3'], 1), dtype='float64') * gamma\n",
    "# Measure the fourth vertex\n",
    "mbqc.measure('4', basis('XY', theta4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  Correct byproducts on the fifth vertex\n",
    "\n",
    "After measurements on the first four vertices, the state on the fifth vertex is not exactly $U|\\psi\\rangle$, but a state with byproducts $X^{s_2 + s_4}Z^{s_1 + s_3} U|\\psi\\rangle$. To obtain the desired $U|\\psi\\rangle$, we must correct byproducts on the fifth vertex."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Correct byproducts on the fifth vertex\n",
    "mbqc.correct_byproduct('X','5', mbqc.sum_outcomes(['2','4']))\n",
    "mbqc.correct_byproduct('Z','5', mbqc.sum_outcomes(['1','3']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Obtain the final output state and compare it with the expected one\n",
    "\n",
    "We can call `get_classical_output` and `get_quantum_output` to obtain the classical and quantum outputs after simulation. We also provide in the module ``utils`` two functions `compare_by_vector` and `compare_by_density` to check if two given quantum states are identical. The former function compares two states by their state vectors, while the second function compares their density matrices. If two states are identical, both functions will return the norm difference of these two states, and print a statement: \"They are exactly the same states.\" (Note: we regard two states as the same if their norm difference is within the range of 1e-14 and 1e-16.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Obtain the classcial result\n",
    "classical_output = mbqc.get_classical_output()\n",
    "# Obtain the quantum result\n",
    "quantum_output = mbqc.get_quantum_output()\n",
    "\n",
    "# Compute the expected state vector\n",
    "vector_std = matmul(rotation_gate('x', gamma),\n",
    "                matmul(rotation_gate('z', beta),\n",
    "                    matmul(rotation_gate('x', alpha), input_psi)))\n",
    "# Construct the expected state on vertex '5'\n",
    "state_std = State(vector_std, ['5'])\n",
    "\n",
    "# Compare with the expected state\n",
    "compare_by_vector(quantum_output, state_std)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Example: CNOT gate in MBQC\n",
    "\n",
    "CNOT gate is one of the most frequently used gates in the circuit model. In MBQC, the realization of a CNOT gate is shown in Figure 4 [7]: prepare $15$ qubits, with $1$, $9$ being the input qubits and $7$, $15$ being the output qubits; input a state $|\\psi\\rangle$ and initialize other vertices to $|+\\rangle$; apply a CZ operator to each connected qubit pairs; perform $X$-measurements on the vertices $1, 9, 10, 11, 13, 14$ and $Y$-measurement on the vertices $2, 3, 4, 5, 6, 8, 12$ (Note: All of these measurements are non-adaptive measurements, so the order of their executions can be permuted); correct byproducts on $7$ and $15$ to obtain the output state $\\text{CNOT}|\\psi\\rangle$.\n",
    "\n",
    "![CNOT pattern](./figures/mbqc-fig-cnot_pattern.jpg)\n",
    "<div style=\"text-align:center\">Figure 4: Realization of CNOT gate in MBQC </div>\n",
    "\n",
    "**Note**: Similar to the first example, byproduct corrections are necessary to get the desired $\\text{CNOT}|\\psi\\rangle$.\n",
    "\n",
    "Here is a complete code implementation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import common calculation modules\n",
    "from paddle import to_tensor, matmul\n",
    "\n",
    "# Import relevant modules for MBQC simulation\n",
    "from paddle_quantum.mbqc.simulator import MBQC\n",
    "from paddle_quantum.mbqc.qobject import State\n",
    "from paddle_quantum.mbqc.utils import pauli_gate, cnot_gate, basis, random_state_vector, compare_by_vector\n",
    "\n",
    "# Define Pauli X and Pauli Z gates and X, Y measurement bases\n",
    "X = pauli_gate('X')\n",
    "Z = pauli_gate('Z')\n",
    "X_basis = basis('X')\n",
    "Y_basis = basis('Y')\n",
    "\n",
    "# Define the underlying graph for computation\n",
    "V = [str(i) for i in range(1, 16)]\n",
    "E = [('1', '2'), ('2', '3'), ('3', '4'), ('4', '5'), \n",
    "     ('5', '6'), ('6', '7'), ('4', '8'), ('8', '12'),\n",
    "     ('9', '10'), ('10', '11'), ('11', '12'), \n",
    "     ('12', '13'), ('13', '14'), ('14', '15')]\n",
    "G = [V, E]\n",
    "\n",
    "# Generate a random state vector\n",
    "input_psi = random_state_vector(2)\n",
    "# Construct a quantum state on vertices '1' and '9'\n",
    "input_state = State(input_psi, ['1','9'])\n",
    "\n",
    "# Instantiate a MBQC class\n",
    "mbqc = MBQC()\n",
    "# Set the graph state\n",
    "mbqc.set_graph(G)\n",
    "# Set the input state\n",
    "mbqc.set_input_state(input_state)\n",
    "\n",
    "# Measure each qubit step by step\n",
    "mbqc.measure('1', X_basis)\n",
    "mbqc.measure('2', Y_basis)\n",
    "mbqc.measure('3', Y_basis)\n",
    "mbqc.measure('4', Y_basis)\n",
    "mbqc.measure('5', Y_basis)\n",
    "mbqc.measure('6', Y_basis)\n",
    "mbqc.measure('8', Y_basis)\n",
    "mbqc.measure('9', X_basis)\n",
    "mbqc.measure('10', X_basis)\n",
    "mbqc.measure('11', X_basis)\n",
    "mbqc.measure('12', Y_basis)\n",
    "mbqc.measure('13', X_basis)\n",
    "mbqc.measure('14', X_basis)\n",
    "\n",
    "# Compute the power of byproduct operators\n",
    "cx = mbqc.sum_outcomes(['2', '3', '5', '6'])\n",
    "tx = mbqc.sum_outcomes(['2', '3', '8', '10', '12', '14'])\n",
    "cz = mbqc.sum_outcomes(['1', '3', '4', '5', '8', '9', '11'], 1)\n",
    "tz = mbqc.sum_outcomes(['9', '11', '13'])\n",
    "\n",
    "# Correct the byproduct operators\n",
    "mbqc.correct_byproduct('X', '7', cx)\n",
    "mbqc.correct_byproduct('X', '15', tx)\n",
    "mbqc.correct_byproduct('Z', '7', cz)\n",
    "mbqc.correct_byproduct('Z', '15', tz)\n",
    "\n",
    "# Obtain the classcial result\n",
    "classical_output = mbqc.get_classical_output()\n",
    "# Obtain the quantum result\n",
    "quantum_output = mbqc.get_quantum_output()\n",
    "\n",
    "# Construct the expected result\n",
    "vector_std = matmul(to_tensor(cnot_gate()), input_psi)\n",
    "state_std = State(vector_std, ['7', '15'])\n",
    "\n",
    "# Compare with the expected result\n",
    "compare_by_vector(quantum_output, state_std)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Welcome Aboard!\n",
    "\n",
    "After this tutorial, we highly recommend learning the following ones for further exploration:\n",
    "\n",
    "- [Measurement-based Quantum Approximate Optimization Algorithm](QAOA_EN.ipynb)\n",
    "- [Polynomial Unconstrained Boolean Optimization Problem in MBQC](PUBO_EN.ipynb)\n",
    "- [Speeding Up Quantum Circuit Simulation by MBQC](Pattern_EN.ipynb)\n",
    "\n",
    "Our MBQC module provides all the essential building blocks for the implementation of a general MBQC algorithm. It can do much beyond than what we have listed above. We sincerely encourage you to explore more potential applications with MBQC and our module! If you are interested in a more detailed study of MBQC itself, please refer to [15,16]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## References\n",
    "\n",
    "[1] Deutsch, David Elieser. \"Quantum computational networks.\" [Proceedings of the Royal Society of London. A. 425.1868 (1989): 73-90.](https://royalsocietypublishing.org/doi/abs/10.1098/rspa.1989.0099)\n",
    "\n",
    "[2] Barenco, Adriano, et al. \"Elementary gates for quantum computation.\" [Physical review A 52.5 (1995): 3457.](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.3457)\n",
    "\n",
    "[3] Gottesman, Daniel, and Isaac L. Chuang. \"Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations.\" [Nature 402.6760 (1999): 390-393.](https://www.nature.com/articles/46503?__hstc=13887208.d9c6f9c40e1956d463f0af8da73a29a7.1475020800048.1475020800050.1475020800051.2&__hssc=13887208.1.1475020800051&__hsfp=1773666937)\n",
    "\n",
    "[4] Nielsen, Michael A. \"Quantum computation by measurement and quantum memory.\" [Physics Letters A 308.2-3 (2003): 96-100.](https://www.sciencedirect.com/science/article/abs/pii/S0375960102018030)\n",
    "\n",
    "[5] Leung, Debbie W. \"Quantum computation by measurements.\" [International Journal of Quantum Information 2.01 (2004): 33-43.](https://www.worldscientific.com/doi/abs/10.1142/S0219749904000055)\n",
    "\n",
    "[6] 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",
    "[7] 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",
    "[8] 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",
    "[9] Briegel, Hans J., et al. \"Measurement-based quantum computation.\" [Nature Physics 5.1 (2009): 19-26.](https://www.nature.com/articles/nphys1157)\n",
    "\n",
    "[10] Aliferis, Panos, and Debbie W. Leung. \"Computation by measurements: a unifying picture.\" [Physical Review A 70.6 (2004): 062314.](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.70.062314)\n",
    "\n",
    "[11] Broadbent, Anne, et al. \"Universal blind quantum computation.\" [2009 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2009.](https://arxiv.org/abs/0807.4154)\n",
    "\n",
    "[12] Morimae, Tomoyuki. \"Verification for measurement-only blind quantum computing.\" [Physical Review A 89.6 (2014): 060302.](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.89.060302)\n",
    "\n",
    "[13] Larsen, Mikkel V., et al. \"Deterministic generation of a two-dimensional cluster state.\" [Science 366.6463 (2019): 369-372.](https://science.sciencemag.org/content/366/6463/369)\n",
    "\n",
    "[14] Asavanant, Warit, et al. \"Generation of time-domain-multiplexed two-dimensional cluster state.\" [Science 366.6463 (2019): 373-376.](https://science.sciencemag.org/content/366/6463/373)\n",
    "\n",
    "[15] Richard Jozsa, et al. \"An introduction to measurement based quantum computation.\" [arXiv:quant-ph/0508124](https://arxiv.org/abs/quant-ph/0508124v2)\n",
    "\n",
    "[16] Nielsen, Michael A. \"Cluster-state quantum computation.\" [Reports on Mathematical Physics 57.1 (2006): 147-161.](https://www.sciencedirect.com/science/article/abs/pii/S0034487706800145)\n",
    "\n",
    "[17] Nielsen, Michael A., and Isaac Chuang. \"Quantum computation and quantum information.\"[Cambridge university press (2010).](https://www.cambridge.org/core/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE)\n",
    "\n",
    "[18] 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)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "07efdcd4b820c98a756949507a4d29d7862823915ec7477944641bea022f4f62"
  },
  "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.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "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
}