04_Solving a problem with quantum computers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "aec1e5f5",
   "metadata": {},
   "source": [
    "# Solving a problem with quantum computers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5838c415",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, execute, BasicAer\n",
    "from qiskit.visualization import plot_histogram, array_to_latex\n",
    "from qiskit.quantum_info import Statevector\n",
    "backend = BasicAer.get_backend('qasm_simulator')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3af92482",
   "metadata": {},
   "source": [
    "Generating random numbers from a variety of specific probability distributions is interesting, and so is implementing digital computer operations on a quantum computer so that multiple operations are performed simultaneously. However neither of these is enough to justify the hype around quantum computers. Let's now take a look at an example of something where quantum computers can significantly outperform digital computers. It's known as [Grover's algorithm](https://en.wikipedia.org/wiki/Grover%27s_algorithm), and allows a quantum computer to take a function that might be performed on digital computers, and wrap it in some quantum goodness that quickly solves for it. \"Solving for it\" in this context means creating a probability distribution that is skewed in a controlled way so that the right answer comes up most often when measuring the qubits at the end.\n",
    "\n",
    "Also, we will solve for a function of the type where it has one (or just a couple) of solutions, and where the approach to solve for it on a digital computer would be to \"brute force\" the answer by trying every possible solution to check if it works. On a quantum computer, there are some tricks to try the function fewer times, or even just once, and yet still figure out the solution. This demonstrates quantum advantage for using a quantum computer to solve problems of this type.\n",
    "\n",
    "Functions of the type we're interested in, that have one specific solution, exist all over the place. So, this is a potentially highly useful application for quantum computers. For example, a function that checks a possible set of numbers to a particular [Sudoku puzzle](https://en.wikipedia.org/wiki/Sudoku) to confirm if it is a correct solution, a function that checks a password to see if it matches an encrypted password entry for a user, or a function that confirms the colour of a particular pixel in an image is correct for a given 3D scene with a particular set of objects and lighting. Many different problems can be rewritten in terms of a function that checks if an answer is correct.\n",
    "\n",
    "However, before seeing how to do this on a quantum computer, we need to introduce a couple of new operations. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa2812d1",
   "metadata": {},
   "source": [
    "### Z operation\n",
    "The Z operation works on all pairs of rows in the state vector associated with different values of a particular qubit, and flips the sign on the second row of each pair. We can call it the \"flip\" operation. Let's have a quick look at an example.\n",
    "\n",
    "In a two qubit scenario, if we start with an H(0) operator and an H(1) operator, as we did in the first notebook, we have the same value on each row of the state vector. If we then do a Z(0) followed by a Z(1), you can see the signs flip but the numbers otherwise stay the same.\n",
    "\n",
    "| Qubits| Initial state vector | H(0) | H(1) | Z(0) | Z(1) |\n",
    "| :- | :- | :- | :- | :- | :- |\n",
    "| $\\rvert00\\rangle$ | $1.0$ | $\\frac{1}{\\sqrt{2}}$ | $\\frac{1}{2}$ | $\\frac{1}{2}$  | $\\frac{1}{2}$  |\n",
    "| $\\rvert01\\rangle$ | $0.0$ | $\\frac{1}{\\sqrt{2}}$ | $\\frac{1}{2}$ | -$\\frac{1}{2}$ | -$\\frac{1}{2}$ |\n",
    "| $\\rvert10\\rangle$ | $0.0$ | $0.0$                | $\\frac{1}{2}$ | $\\frac{1}{2}$  | -$\\frac{1}{2}$ |\n",
    "| $\\rvert11\\rangle$ | $0.0$ | $0.0$                | $\\frac{1}{2}$ | -$\\frac{1}{2}$ | $\\frac{1}{2}$  |\n",
    "\n",
    "We saw negative probabilities in the notebook where we introduced the RY operation, and here they are again. They are the key to how Grover's algorithm works.\n",
    "\n",
    "Note that we could have created a Z operation out of the operations that we already have, using a neat trick. The Z operation produces the same result as using the H, X, and H operations in sequence. If you remember, H takes a pair of rows with values $a$ and $b$, and turns them into $\\frac{a+b}{\\sqrt{2}}$ and $\\frac{a-b}{\\sqrt{2}}$. X then swaps these, so performing H again results in $\\frac{2a}{\\sqrt{2}\\times\\sqrt{2}}$ and $\\frac{-2b}{\\sqrt{2}\\times\\sqrt{2}}$ which is $a$ and $-b$. However, Z is a common enough thing to want to do that it is useful to have it as a standalone operation rather than do H, X and H each time.\n",
    "\n",
    "### CCZ operation\n",
    "Similarly to CCX, the CCZ is \"doubly constrained\". In this case, it is a \"doubly constrained flip\" operation. Constrained to just those rows where the two specified qubits are $|1\\rangle$, it flips the sign of the second row of all pairs where the third qubit is the only one changing. Since the second row of these pairs is also the row where the third qubit is $|1\\rangle$, another way to think about this operation is flipping the sign of all rows where the three specified qubits are $|1\\rangle$.\n",
    "\n",
    "Here's an example of CCZ in practice:\n",
    "\n",
    "| Qubits| Initial state vector | H(0) | H(1) | H(2) | CCZ(0, 1, 2) |\n",
    "| :- | :- | :- | :- | :- | :- |\n",
    "| $\\rvert000\\rangle$ ($\\rvert0\\rangle$) | $1.0$ | $\\frac{1}{\\sqrt{2}}$ | $\\frac{1}{2}$ | $\\frac{1}{\\sqrt{8}}$ | $\\frac{1}{\\sqrt{8}}$ |\n",
    "| $\\rvert001\\rangle$ ($\\rvert1\\rangle$) | $0.0$ | $\\frac{1}{\\sqrt{2}}$ | $\\frac{1}{2}$ | $\\frac{1}{\\sqrt{8}}$ | $\\frac{1}{\\sqrt{8}}$ |\n",
    "| $\\rvert010\\rangle$ ($\\rvert2\\rangle$) | $0.0$ | $0.0$ | $\\frac{1}{2}$ | $\\frac{1}{\\sqrt{8}}$ | $\\frac{1}{\\sqrt{8}}$ |\n",
    "| $\\rvert011\\rangle$ ($\\rvert3\\rangle$) | $0.0$ | $0.0$ | $\\frac{1}{2}$ | $\\frac{1}{\\sqrt{8}}$ | $\\frac{1}{\\sqrt{8}}$ |\n",
    "| $\\rvert100\\rangle$ ($\\rvert4\\rangle$) | $0.0$ | $0.0$ | $0.0$ | $\\frac{1}{\\sqrt{8}}$ | $\\frac{1}{\\sqrt{8}}$ |\n",
    "| $\\rvert101\\rangle$ ($\\rvert5\\rangle$) | $0.0$ | $0.0$ | $0.0$ | $\\frac{1}{\\sqrt{8}}$ | $\\frac{1}{\\sqrt{8}}$ |\n",
    "| $\\rvert110\\rangle$ ($\\rvert6\\rangle$) | $0.0$ | $0.0$ | $0.0$ | $\\frac{1}{\\sqrt{8}}$ | $\\frac{1}{\\sqrt{8}}$ |\n",
    "| $\\rvert111\\rangle$ ($\\rvert7\\rangle$) | $0.0$ | $0.0$ | $0.0$ | $\\frac{1}{\\sqrt{8}}$ | $-\\frac{1}{\\sqrt{8}}$ |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a781476",
   "metadata": {},
   "source": [
    "### Implementing a verifier\n",
    "The other thing that Grover's algorithm needs is a function that verifies whether a value is a valid solution to some problem. All it needs to do is take a potential solution, and tell us \"yes\" or \"no\".\n",
    "\n",
    "We can do this by considering some of the qubits to represent a proposed solution, and one other qubit to represent \"yes\" if it is $|1\\rangle$ or \"no\" if it is $|0\\rangle$. In the example implemented here, qubits 0 and 1 will represent potential solutions, and qubit 2 will represent the result of validating it.\n",
    "\n",
    "On a digital computer, we would think about this as bits. We would implement some logical operations that take two bits representing potential solutions and return another bit with the validation result. As we saw in the last notebook, we can implement the deterministic operations of a digital computer on a quantum computer by using X, CX, CCX, etc. operations.\n",
    "\n",
    "Let's say we want our verifier function to take state vectors where one of $|000\\rangle$, $|001\\rangle$, $|010\\rangle$, or $|011\\rangle$ rows has the value $1.0$ (100%), and only if it's the \"right\" one, will the state vector be changed so that the corresponding row where qubit 2 is $|1\\rangle$ becomes $1.0$. For example, if $|011\\rangle$ is the right solution, this would be implemented simply with the function CCX(0, 1, 2).\n",
    "\n",
    "Firstly, let's use X operations to encode the value 3 into the state vector, by putting the value $1.0$ in the $|011\\rangle$ ($|3\\rangle$) row."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5f64c9be",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\n",
       "\n",
       "\\begin{bmatrix}\n",
       "0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 1  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " \\end{bmatrix}\n",
       "$$"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q = QuantumRegister(3)    # We want 3 qubits\n",
    "algo1 = QuantumCircuit(q) # Readies us to construct an algorithm to run on the quantum computer\n",
    "\n",
    "# Start in the |3> row\n",
    "algo1.x(0)\n",
    "algo1.x(1)\n",
    "\n",
    "v1 = Statevector(algo1)\n",
    "array_to_latex(np.vstack(v1.data))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e898e0d9",
   "metadata": {},
   "source": [
    "Now if we perform CCX(0, 1, 2), the values in $|011\\rangle$ ($|3\\rangle$) and $|111\\rangle$ ($|7\\rangle$) will be swapped, moving the $1.0$ value to the final row, where qubit 2 has a value of $|1\\rangle$. Since we know that CCX is constrained to work only on these rows, we know that only where the $|011\\rangle$ potential solution is given the $1.0$ value will the state vector be changed to have $1.0$ on a row where qubit 2 is $|1\\rangle$. The other three potential solutions will result in no change."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "77a5c91a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\n",
       "\n",
       "\\begin{bmatrix}\n",
       "0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 1  \\\\\n",
       " \\end{bmatrix}\n",
       "$$"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "algo1.ccx(0, 1, 2) # Apply CX operation, constrained to rows where qubit 0 and 1 are |1>, swapping qubit 2's rows\n",
    "v2 = Statevector(algo1)\n",
    "array_to_latex(np.vstack(v2.data))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "078619f9",
   "metadata": {},
   "source": [
    "To create different verifier functions, we can use X operations and specify either qubit 0 or qubit 1. For example, to create a function that will answer \"yes\" for the potential solution $|01\\rangle$ and \"no\" the other three potential solutions, we simply do X(1) before doing CCX(0, 1, 2). We will also do X(1) again after the CCX to \"undo\" the first X, and ensure the state vector has $1.0$ in the $|101\\rangle$ ($|5\\rangle$) row:\n",
    "\n",
    "| Qubits| Initial state vector | X(1) | CCX(0, 1, 2) | X(1) |\n",
    "| :- | :- | :- | :- | :- |\n",
    "| $\\rvert000\\rangle$ ($\\rvert0\\rangle$) | $0.0$ | $0.0$ | $0.0$ | $0.0$ |\n",
    "| $\\rvert001\\rangle$ ($\\rvert1\\rangle$) | $1.0$ | $0.0$ | $0.0$ | $0.0$ |\n",
    "| $\\rvert010\\rangle$ ($\\rvert2\\rangle$) | $0.0$ | $0.0$ | $0.0$ | $0.0$ |\n",
    "| $\\rvert011\\rangle$ ($\\rvert3\\rangle$) | $0.0$ | $1.0$ | $0.0$ | $0.0$ |\n",
    "| $\\rvert100\\rangle$ ($\\rvert4\\rangle$) | $0.0$ | $0.0$ | $0.0$ | $0.0$ |\n",
    "| $\\rvert101\\rangle$ ($\\rvert5\\rangle$) | $0.0$ | $0.0$ | $0.0$ | $1.0$ |\n",
    "| $\\rvert110\\rangle$ ($\\rvert6\\rangle$) | $0.0$ | $0.0$ | $0.0$ | $0.0$ |\n",
    "| $\\rvert111\\rangle$ ($\\rvert7\\rangle$) | $0.0$ | $0.0$ | $1.0$ | $0.0$ |\n",
    "\n",
    "Implementing this in Qiskit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "87a3f4a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Verifies that a proposed solution is correct only when it is |10>\n",
    "def add_verify(algo):\n",
    "    algo.x(1)\n",
    "    algo.ccx(0, 1, 2)\n",
    "    algo.x(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8dfdecc9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\n",
       "\n",
       "\\begin{bmatrix}\n",
       "0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " 1  \\\\\n",
       " 0  \\\\\n",
       " 0  \\\\\n",
       " \\end{bmatrix}\n",
       "$$"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "algo2 = QuantumCircuit(q) # Readies us to construct an algorithm to run on the quantum computer\n",
    "\n",
    "# Ensure the state vector has 100% in the |001> row\n",
    "algo2.x(0) \n",
    "\n",
    "add_verify(algo2) # Add the verify function to the algorithm\n",
    "v3 = Statevector(algo2)\n",
    "array_to_latex(np.vstack(v3.data))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75b4602f",
   "metadata": {},
   "source": [
    "However, we need to modify the verifier function a little first. We are going to apply the H operation on the result qubit (qubit 2) before running the function, and then again afterwards.\n",
    "\n",
    "This is a little trick that turns an X operation into a Z operation. So, the CCX operation effectively becomes like a CCZ operation. And yes, the verifier function could have just been written with a CCZ instead of a CCX and we could skip the H operations, but digital computer operations don't use Z type operations, and this way the algorithm is more general."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "939a30eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Flips the sign of the row corresponding to the outcome that the verify function would indicate is correct\n",
    "def add_verify_with_h(algo):\n",
    "    algo.h(2)\n",
    "    add_verify(algo)\n",
    "    algo.h(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "056528fa",
   "metadata": {},
   "source": [
    "This version of the function will now flip the sign of the state vector row with the answer. Unfortunately, we can't stop here with the job done, because in practice we can't read the state vector out of the quantum computer. All we can do is take measurements of the qubits, and while we can have a negative value in a row of a state vector, we won't see a negative probability appear in measurements.\n",
    "\n",
    "Grover's algorithm is about amplifying the negative row so it will have a higher probability in the measurements."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ade181d",
   "metadata": {},
   "source": [
    "### Grover's algorithm\n",
    "Normally the verification function will be quite complicated, and difficult to figure out from just looking at it. Our verification function is simple, but that's fine for learning how Grover's algorithm works.\n",
    "\n",
    "The basic strategy for using Grover's algorithm is to:\n",
    "1. Prepare the state vector so it has the same value on every row, i.e. no row has a zero value.\n",
    "2. Apply the verification function, which will flip the sign of the row corresponding to the right answer.\n",
    "3. Amplify the negative rows compared to the non-negative rows.\n",
    "\n",
    "Then we measure the qubits, and the most likely result should be the right answer. For larger numbers of qubits, the steps 2 and 3 will typically be repeated to make the right answer clearer, but we shouldn't need to do that for our example.\n",
    "\n",
    "We've already defined the verification function, but here's the state preparation function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "82dce379",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Creates a uniform probability distribution across the state vector\n",
    "def add_prepare(algo):\n",
    "    algo.h(0)\n",
    "    algo.h(1)\n",
    "    algo.h(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19cb46b0",
   "metadata": {},
   "source": [
    "It is just the approach to creating a uniform probability distribution that we saw in the first notebook.\n",
    "\n",
    "We can see how the verification function just flips the sign of the answer row ($|101\\rangle$) when given a state vector with $\\frac{1}{\\sqrt{8}}$ values in all of its rows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d8d1dd4b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\n",
       "\n",
       "\\begin{bmatrix}\n",
       "\\frac{\\sqrt{2}}{4}  \\\\\n",
       " \\frac{\\sqrt{2}}{4}  \\\\\n",
       " \\frac{\\sqrt{2}}{4}  \\\\\n",
       " \\frac{\\sqrt{2}}{4}  \\\\\n",
       " \\frac{\\sqrt{2}}{4}  \\\\\n",
       " - \\frac{\\sqrt{2}}{4}  \\\\\n",
       " \\frac{\\sqrt{2}}{4}  \\\\\n",
       " \\frac{\\sqrt{2}}{4}  \\\\\n",
       " \\end{bmatrix}\n",
       "$$"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "algo3 = QuantumCircuit(q) # Readies us to construct an algorithm to run on the quantum computer\n",
    "add_prepare(algo3)        # Add the operations to prepare the state vector for solving the function\n",
    "add_verify_with_h(algo3)  # Add the sign-flipping version of the verify function to the algorithm\n",
    "v4 = Statevector(algo3)\n",
    "array_to_latex(np.vstack(v4.data))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a895314d",
   "metadata": {},
   "source": [
    "The amplification function requires a bit of explanation. \n",
    "\n",
    "The idea is to make everything a bit more negative, and because one row is already negative, that row becomes much more negative than the other rows. As the probability of the outcome of a measurement being a given row is equal to the square of the value of that row, it doesn't matter than the values are negative. The row that is more negative than the other rows will end up becoming a more likely outcome.\n",
    "\n",
    "The workhorse of the procedure is the H operation. As we discussed in the first notebook, it is like a \"half\" operation, where it works on all pairs of rows that differ only by a specific qubit, and turns the first of these into the sum of the pairs divided by the root of a half, and the second into the difference of the pairs divided by the root of a half.\n",
    "\n",
    "There are two observations worth noting here. Firstly, it puts the sums of the pairs into the first row, i.e. the row where the specific qubit is $|0\\rangle$. Secondly, it is its own inverse, i.e. that it you perform two identical H operations in sequence, the second operation undoes the first one.\n",
    "\n",
    "Using these two observations, the amplification function applies the H operation for each of the qubits in turn, resulting in all rows being summed into the first row of the state vector, i.e. corresponding to $|000\\rangle$, although this sum will be divided by the root of 8, which is the result of applying $\\frac{1}{\\sqrt{2}}$ in the calculations three times. However, this row will be a large, positive value.\n",
    "\n",
    "Then the amplification function flips the sign on the $|000\\rangle$ row, making it a large, negative value. Lastly, the H operation is applied for each qubit in turn, reversing the earlier H operations, but spreading the amount \"taken\" from the $|000\\rangle$ row across all of the other rows.\n",
    "\n",
    "Let's see it in action. Firstly, let's apply H for each qubit. We can do this by reusing the prepare function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "6575add2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\n",
       "\n",
       "\\begin{bmatrix}\n",
       "\\frac{3}{4}  \\\\\n",
       " \\frac{1}{4}  \\\\\n",
       " - \\frac{1}{4}  \\\\\n",
       " \\frac{1}{4}  \\\\\n",
       " \\frac{1}{4}  \\\\\n",
       " - \\frac{1}{4}  \\\\\n",
       " \\frac{1}{4}  \\\\\n",
       " - \\frac{1}{4}  \\\\\n",
       " \\end{bmatrix}\n",
       "$$"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add_prepare(algo3)\n",
    "v5 = Statevector(algo3)\n",
    "array_to_latex(np.vstack(v5.data))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "674accac",
   "metadata": {},
   "source": [
    "After the verify function was performed, all rows were $\\frac{1}{\\sqrt{8}}$, except for the solution row which was negative. The sum of all rows is $\\frac{6}{\\sqrt{8}}$ and this value divided by $\\sqrt{8}$ is $\\frac{3}{4}$, which is what we've ended up with in row $|000\\rangle$ after the first part of the amplification procedure.\n",
    "\n",
    "Next we flip the sign on that row so it becomes negative. We can do this by using the X operation for each qubit, to reverse the order of the state vector. On a digital computer, to reverse a vector like this, you'd need to perform an operation for each row in the first half of the vector, swapping it with its counterpart row in the second half of the vector. Quantum computers are much more efficient.\n",
    "\n",
    "X(0) swaps groups of rows separated by one row, X(1) swaps groups of rows separated by two rows, and X(2) swaps groups of rows separated by four rows. Once we've performed each of these, the state vector has been reversed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e8a9f59c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Reverses the rows of the state vector\n",
    "def add_reverse(algo):\n",
    "    algo.x(0)\n",
    "    algo.x(1)\n",
    "    algo.x(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7687ae0d",
   "metadata": {},
   "source": [
    "Using this reverse routine, we can following it by using CCZ to flip the sign on row $|111\\rangle$, then reverse the state vector again to put the state vector back in the original order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "17ddae82",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\n",
       "\n",
       "\\begin{bmatrix}\n",
       "- \\frac{3}{4}  \\\\\n",
       " \\frac{1}{4}  \\\\\n",
       " - \\frac{1}{4}  \\\\\n",
       " \\frac{1}{4}  \\\\\n",
       " \\frac{1}{4}  \\\\\n",
       " - \\frac{1}{4}  \\\\\n",
       " \\frac{1}{4}  \\\\\n",
       " - \\frac{1}{4}  \\\\\n",
       " \\end{bmatrix}\n",
       "$$"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add_reverse(algo3) # Add the operations to reverse the state vector\n",
    "algo3.ccz(0, 1, 2) # Apply the CCZ operation to flip the sign on row |111>\n",
    "add_reverse(algo3) # Add the operations to reverse the state vector again, putting it back in the right order\n",
    "v6 = Statevector(algo3)\n",
    "array_to_latex(np.vstack(v6.data))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65314fda",
   "metadata": {},
   "source": [
    "Note that in flipping the sign on row $|000\\rangle$, we have deducted an amount equal to $\\frac{6}{4}$ (or $\\frac{3}{2}$) from this row. This reduction will now be spread back across all the rows by using the H operation for each qubit again. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "b09e06fa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\n",
       "\n",
       "\\begin{bmatrix}\n",
       "-0.1767766953  \\\\\n",
       " -0.1767766953  \\\\\n",
       " -0.1767766953  \\\\\n",
       " -0.1767766953  \\\\\n",
       " -0.1767766953  \\\\\n",
       " -0.8838834765  \\\\\n",
       " -0.1767766953  \\\\\n",
       " -0.1767766953  \\\\\n",
       " \\end{bmatrix}\n",
       "$$"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add_prepare(algo3)\n",
    "v7 = Statevector(algo3)\n",
    "array_to_latex(np.vstack(v7.data))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d3f035e",
   "metadata": {},
   "source": [
    "The reduction by $\\frac{3}{2}$ has been divided by $\\sqrt{8}$ again, so the difference between these values and the ones after the verify function is just $\\frac{3}{\\sqrt{32}}$. All of the rows that were $\\frac{1}{\\sqrt{8}}$ are now $-\\frac{1}{\\sqrt{32}}$, and the single row that was $-\\frac{1}{\\sqrt{8}}$ is now $-\\frac{5}{\\sqrt{32}}$. The visualisation here in the notebook probably doesn't show it, and just shows $-0.17678$ (or similar) for all rows except one that shows $-0.88388$ (or similar).\n",
    "\n",
    "Now that we've worked through the operation of the amplify function, we can define it as a Python function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "54ad92d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Amplifies the row with a negative value to become more negative\n",
    "def add_amplify(algo):\n",
    "    add_prepare(algo)\n",
    "    add_reverse(algo)\n",
    "    algo.ccz(0, 1, 2)\n",
    "    add_reverse(algo)\n",
    "    add_prepare(algo)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df4945e3",
   "metadata": {},
   "source": [
    "Let's now see the whole thing in action, and what gets measured at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "b4cc9178",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAnkAAAG8CAYAAACixLM7AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAA9hAAAPYQGoP6dpAABAF0lEQVR4nO3de3xM1/7/8fdkchEhQRqXkESQJnVpRV1KNISeKFrl6A0tbQ96c9TltKiv0irFoSinLXKqt+Ogh7bqR4VKqFTrGq3TiiFKNKIUiaQuSWZ+f/hmvh2ZkMRlJjuv5+PRR1l7Zc9nmUXeWXvtPSabzWYTAAAADMXD1QUAAADg+iPkAQAAGBAhDwAAwIAIeQAAAAZEyAMAADAgQh4AAIABEfIAAAAMiJAHAABgQJ6uLqCis1qtyszMVPXq1WUymVxdDgAAMDibzaazZ88qODhYHh4lr9cR8q5RZmamQkJCXF0GAACoZDIyMtSgQYMSjxPyrlH16tUlXfqD9vf3d3E1AADA6HJychQSEmLPICUh5F2joku0/v7+hDwAAHDTXG2bGDdeAAAAGBAhD0CZFRYWasKECQoPD5evr68aN26syZMny2azSZLy8/M1ZswYtWjRQn5+fgoODtbAgQOVmZnpcJ79+/frgQce0C233CJ/f3917NhRSUlJrhgSABgOIQ9AmU2fPl3vvPOO5s+fr59++knTp0/XjBkzNG/ePEnS77//rl27dmnChAnatWuXVq5cqbS0NPXq1cvhPPfdd58KCgq0ceNG7dy5U3fccYfuu+8+ZWVluWJYAGAoJlvRj94ol5ycHAUEBCg7O5s9eag07rvvPtWpU0f//Oc/7W19+/aVr6+vPv74Y6dfs337drVt21aHDx9WaGioTp48qaCgIG3evFl33323JOns2bPy9/fX+vXrdc8999yUsQBARVPa7MFKHoAy69Chg7766ivt379fkrRnzx5t2bJF3bt3L/FrsrOzZTKZVKNGDUlSYGCgIiMj9eGHHyovL08FBQVasGCBateurTvvvPNmDAMADI27awGU2dixY5WTk6OoqCiZzWYVFhZqypQpGjBggNP+58+f15gxY9SvXz/7T50mk0kbNmxQ7969Vb16dXl4eKh27dr68ssvVbNmzZs5HAAwJEIegDJbvny5/vWvf2nJkiVq1qyZUlNTNWLECAUHB2vQoEEOffPz8/Xwww/LZrPpnXfesbfbbDY9//zzql27tr7++mv5+voqISFB999/v7Zv36569erd7GEBgKGwJ+8asScPlVFISIjGjh2r559/3t72+uuv6+OPP9a+ffvsbUUBLz09XRs3blRgYKD92FdffaX4+HidPn3a4e9ORESE/vKXv2js2LE3ZzAAUMGUNnuwkgegzH7//fdin5doNptltVrtvy8KeBaLRUlJSQ4Br+gckoqdx8PDw+E8AIDyIeQBKLP7779fU6ZMUWhoqJo1a6bdu3frzTff1FNPPSXpUsB78MEHtWvXLq1evVqFhYX2x6LUqlVL3t7eat++vWrWrKlBgwbplVdeka+vrxYtWqRDhw6pZ8+erhweABgCl2uvEZdrURmdPXtWEyZM0Keffqpff/1VwcHB6tevn1555RV5e3vr559/Vnh4uNOvTUpKUufOnSVJO3bs0Pjx47Vjxw7l5+erWbNmeuWVV654ly4AVHalzR6EvGtEyAMAADcTz8kDAACoxAh5AAAABkTIAwAAMCBCHgAAgAER8gAAAAyIkAcAAGBAhDwAAAADIuQBAAAYECEPAADAgAh5AAAABkTIAwAAMCBCHgAAgAER8gAAAAyIkAcAAGBAhDwAAAADIuQBAAAYECEPAADAgAh5AAAABkTIAwAAMCBCHgAAgAF5uroAADfGkDmursA9LRrh6goA4OZgJQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAAbllyLPZbFq5cqXi4uJUr149Va1aVZGRkXr66aeVnp5erH9OTo5GjRqlsLAw+fj4qGHDhnrxxReVm5vr9PxWq1Xz5s1TixYt5Ovrq6CgIPXr18/puQEAACoitwx5f/vb39S3b1+lpaWpd+/e+utf/6rw8HAtWrRILVu21N69e+198/Ly1KlTJ82ePVtRUVEaOXKkIiMjNXPmTHXp0kXnz58vdv6nn35aw4cPl81m0/Dhw3Xvvfdq5cqVatOmjSwWy80cKgAAwA3hdo9QycrK0pw5cxQWFqY9e/YoICDAfmz27NkaNWqU3nzzTb333nuSpBkzZig1NVVjxozRtGnT7H3Hjh2r6dOna/bs2Ro3bpy9PSkpSQkJCYqNjdX69evl7e0tSerfv7969OihYcOGad26dTdptAAAADeG263k/fzzz7JarYqJiXEIeJJ03333SZJOnDgh6dJl3YSEBFWrVk0TJkxw6DthwgRVq1ZNCQkJDu2LFi2SJE2ePNke8CSpe/fu6ty5sxITE3XkyJHrPi4AAICbye1CXkREhLy9vZWSkqKcnByHY6tXr5Ykde3aVZJksViUmZmpmJgY+fn5OfT18/NTTEyM0tPTlZGRYW9PTk62H7tct27dJEmbNm26rmMCAAC42dzucm1gYKCmTZum0aNHKyoqSg888ID8/f21Z88ebdy4Uc8995yGDRsmSfb9cxEREU7PFRERoXXr1slisSgkJER5eXk6duyYmjdvLrPZ7LT/H8/rzIULF3ThwgX774uCaH5+vvLz8yVJHh4eMpvNKiwslNVqtfctai8oKJDNZrO3m81meXh4lNhedN4inp6X3raCgoJStXt5eclqtaqwsNDeZjKZ5OnpWWJ7SbUzpoozJqn4HIfc7n0y4txjTIyJMd34MZWG24U8SRo5cqTq16+vwYMH691337W3d+zYUf3797f/wWZnZ0tSscu6Rfz9/R36lbW/M2+88YZeffXVYu2JiYmqWrWqJCk0NFTR0dH6/vvvHS79RkZGKioqStu2bbNfcpakli1bKiwsTJs3b9bZs2ft7e3bt1ft2rWVmJjo8IbGxcXJ19dXa9ascaihR48eOnfunJKSkuxtnp6e6tmzp06ePKmtW7fa26tXr64uXbooIyNDqamp9vagoCB16NBBFotFaWlp9nbGVPHGJEULxbnb+2TEuceYGBNjurFj2rlzp0rDZPtjjHUTr732ml5//XW99tpreuyxx1SjRg2lpqZq5MiRSk1N1YoVK9SrVy8tWbJEAwYM0Pjx4/X6668XO8/48eM1depUrVy5Un369FFmZqbq16+vmJgYbdmypVj/9evXKz4+XsOHD9fcuXOd1uZsJS8kJEQnT560h8TK+lMFY3KvMT0zj5U8Z95+3r3eJyPOPcbEmBjTjR3TqVOnFBgYqOzsbHv2cMbtVvI2bNigiRMnauTIkRo7dqy9vWPHjvriiy/UqFEjjR49Wr169bKvyJW08lZ0KbWoX1n7O+Pj4yMfH59i7V5eXvLy8nJoM5vNTi8LF02M0rZfft7ytHt4eMjDo/gWzJLaS6qdMVWcMcE5d3ufjDj3GBNjYkyuGVOx1ytVr5to7dq1ki4tj16ubt26ioqK0oEDB5Sbm3vVPXSX79nz8/NTvXr1dOjQIYckXVJ/AACAisrtQt7FixclyeH6+R+dOHFCHh4e8vLyUkREhIKDg5WSkqK8vDyHfnl5eUpJSVF4eLhCQkLs7Z06dbIfu1zR8/FiY2Ov13AAAABcwu1CXtGjTd58881il1XfffddHT16VO3bt5ePj49MJpMGDx6s3NxcTZ482aHv5MmTlZubqyFDhji0Dx06VNKl5+gVBUrp0gpicnKy4uPjFRYWdiOGBgAAcNO43Y0XhYWF6tKlizZv3qzatWurV69eqlGjhnbt2qWNGzfK19dXycnJatu2raRLK3YxMTHas2eP4uPj1apVK+3atUuJiYlq06aNNm3aJF9fX4fXGDJkiBISEtSsWTP17NlTx44d07Jly1StWjVt3bpVt956a6nrzcnJUUBAwFU3PwI325A5rq7APS0a4eoKAODalDZ7uF3Iky7dwTp79mwtX75caWlpunjxourUqaO4uDi9/PLLuu222xz6Z2dna9KkSVqxYoWysrJUr149PfTQQ5o4caKqV69e7PxWq1Xz58/XwoULdeDAAVWrVk333HOPpkyZosaNG5epVkIe3BUhzzlCHoCKrkKHvIqEkAd3RchzjpAHoKIrbfZwuz15AAAAuHaEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwILcOeZ9++qn+9Kc/KTAwUFWqVFF4eLj69eunjIwMh345OTkaNWqUwsLC5OPjo4YNG+rFF19Ubm6u0/NarVbNmzdPLVq0kK+vr4KCgtSvXz+lp6ffjGEBAADccJ6uLsAZm82mZ555RgsXLlTjxo316KOPqnr16srMzNSmTZt0+PBhhYSESJLy8vLUqVMnpaamKj4+Xv369dPu3bs1c+ZMbdq0SZs3b1aVKlUczv/0008rISFBzZo10/Dhw5WZmanly5crMTFR3377rSIiIlwxbAAAgOvGLUPeW2+9pYULF+q5557TW2+9JbPZ7HC8oKDA/usZM2YoNTVVY8aM0bRp0+ztY8eO1fTp0zV79myNGzfO3p6UlKSEhATFxsZq/fr18vb2liT1799fPXr00LBhw7Ru3bobPEIAAIAby2Sz2WyuLuKPzp07p/r166tmzZpKS0uTp2fJOdRms6lBgwbKyclRVlaW/Pz87Mfy8vJUt25d1a5dWwcPHrS39+/fX//+97+1adMmxcbGOpwvLi5OycnJOnz4sEJDQ0tVb05OjgICApSdnS1/f/8yjha4cYbMcXUF7mnRCFdXAADXprTZw+325CUmJur06dPq3bu3CgsLtXLlSk2bNk3vvvuuDhw44NDXYrEoMzNTMTExDgFPkvz8/BQTE6P09HSHPXzJycn2Y5fr1q2bJGnTpk03YGQAAAA3j9tdrt25c6ckyWw26/bbb9f+/fvtxzw8PDRy5EjNnDlT0qWQJ6nEPXQRERFat26dLBaLQkJClJeXp2PHjql58+bFLgH/8TxF53XmwoULunDhgv33OTk5kqT8/Hzl5+fb6zSbzSosLJTVanWo32w2q6CgQH9cQDWbzfLw8Cixvei8RYpWN/942fpK7V5eXrJarSosLLS3mUwmeXp6ltheUu2MqeKMSSo+xyG3e5+MOPcYE2NiTDd+TKXhdiHv119/lSS9+eabatWqlbZt26bbbrtNu3fv1tChQzVr1iw1btxYzz77rLKzsyVJAQEBTs9VtIRZ1K+s/Z1544039OqrrxZrT0xMVNWqVSVJoaGhio6O1vfff68jR47Y+0RGRioqKkrbtm3TiRMn7O0tW7ZUWFiYNm/erLNnz9rb27dvr9q1aysxMdHhDY2Li5Ovr6/WrFnjUEOPHj107tw5JSUl2ds8PT3Vs2dPnTx5Ulu3brW3V69eXV26dFFGRoZSU1Pt7UFBQerQoYMsFovS0tLs7Yyp4o1JihaKc7f3yYhzjzExJsZ0Y8dUtCB2NW63J2/o0KFatGiRfH19deDAAQUHB9uP7d27V3fccYfCw8N14MABLVmyRAMGDND48eP1+uuvFzvX+PHjNXXqVK1cuVJ9+vRRZmam6tevr5iYGG3ZsqVY//Xr1ys+Pl7Dhw/X3LlzndbnbCUvJCREJ0+etIfEyvpTBWNyrzE9M4+VPGfeft693icjzj3GxJgY040d06lTpxQYGHjVPXlut5JXtMrWunVrh4AnSc2bN1ejRo104MABnTlzxt63pJW3okupRf3K2t8ZHx8f+fj4FGv38vKSl5eXQ5vZbHZ6Wbikm0lKar/8vOVp9/DwkIdH8S2YJbWXVDtjqjhjgnPu9j4Zce4xJsbEmFwzpmKvV6peN1FkZKQkqUaNGk6PF7WfO3fuqnvoLt+z5+fnp3r16unQoUMOSbqk/gAAABWV24W8uLg4SdJPP/1U7Fh+fr4OHDggPz8/BQUFKSIiQsHBwUpJSVFeXp5D37y8PKWkpCg8PNz+4GRJ6tSpk/3Y5Yqej3f5o1UAAAAqGrcLeY0bN1Z8fLwOHDighIQEh2PTpk3TmTNn1KdPH3l6espkMmnw4MHKzc3V5MmTHfpOnjxZubm5GjJkiEP70KFDJUkTJkzQxYsX7e1r165VcnKy4uPjFRYWdoNGBwAAcHO43Y0XknTw4EF16NBBv/76q3r27KmoqCjt3r1bGzduVFhYmL799lvVrVtX0qUVu5iYGO3Zs0fx8fFq1aqVdu3apcTERLVp00abNm2Sr6+vw/mHDBli/1iznj176tixY1q2bJmqVaumrVu36tZbby11rTwMGe6KhyE7x8OQAVR0FfZhyNKl1bwdO3boiSee0M6dO/XWW2/JYrHo+eef17Zt2+wBT7q0z27Tpk0aMWKEfvrpJ82aNUv79u3T6NGj9dVXXxULeJK0YMEC+92zc+fO1Zo1a9SnTx9t27atTAEPAADAXbnlSl5Fwkoe3BUrec6xkgegoqvQK3kAAAC4NoQ8AAAAAyLkAQAAGBAhDwAAwIAIeQAAAAZEyAMAADAgQh4AAIABEfIAAAAMiJAHAABgQIQ8AAAAAyLkAQAAGBAhDwAAwIAIeQAAAAZEyAMAADAgQh4AAIABEfIAAAAMiJAHAABgQIQ8AAAAAyLkAQAAGBAhDwAAwIAIeQAAAAZEyAMAADAgQh4AAIABEfIAAAAMiJAHAABgQIQ8AAAAAyp3yNu8ebOOHDlyxT4ZGRnavHlzeV8CAAAA5VTukBcXF6f333//in0+/PBDxcXFlfclAAAAUE7lDnk2m+2qfaxWq0wmU3lfAgAAAOV0Q/fkWSwWBQQE3MiXAAAAgBOeZen81FNPOfz+s88+088//1ysX2FhoX0/Xvfu3a+pQAAAAJRdmULeH/fgmUwmpaamKjU11Wlfk8mkNm3aaPbs2ddSHwAAAMqhTCHv0KFDki7tx2vUqJFGjBihF154oVg/s9msmjVrys/P7/pUCQAAgDIpU8gLCwuz/3rx4sWKjo52aAMAAIB7KFPI+6NBgwZdzzoAAABwHZU75BXZtm2btm/frjNnzqiwsLDYcZPJpAkTJlzrywAAAKAMyh3yTp06pd69eyslJeWKz8wj5AEAANx85Q55o0aN0pYtW9S5c2cNGjRIDRo0kKfnNS8MAgAA4DoodypbvXq12rZtq6+++opPtQAAAHAz5f7Ei3Pnzik2NpaABwAA4IbKHfJatmzp9NMuAAAA4HrlDnkTJ07UqlWr9O23317PegAAAHAdlHtPXlZWlnr27KlOnTppwIABatWqlfz9/Z32HThwYLkLBAAAQNmZbFd6/skVeHh4yGQyOTw+5fL9eTabTSaTyenz84wiJydHAQEBys7OLjHkAq4wZI6rK3BPi0a4ugIAuDalzR7lXslbvHhxeb8UAAAANxgfawYAAGBA5b7xAgAAAO6r3Ct5R44cKXXf0NDQ8r4MAAAAyqHcIa9hw4alehCyyWRSQUFBeV8GAAAA5VDukDdw4ECnIS87O1t79uzRoUOH1KlTJzVs2PBa6gMAAEA5lDvkvf/++yUes9lsmjVrlmbMmKF//vOf5X0JAAAAlNMNufHCZDLpb3/7m5o1a6YXX3zxRrwEAAAAruCG3l3bunVrbdy48Ua+BAAAAJy4oSHv4MGD3HQBAADgAuXek1cSq9WqX375Re+//74+//xzde3a9Xq/BAAAAK6i3CGv6LNrS2Kz2VSzZk3NmjWrvC8BAACAcip3yIuNjXUa8jw8PFSzZk21adNGTz75pGrXrn1NBQIAAKDsyh3ykpOTr2MZAAAAuJ747FoAAAADui43XqSkpCg1NVU5OTny9/dXy5YtFRMTcz1ODQAAgHK4ppD3zTff6Mknn9SBAwckXbrZomifXkREhBYvXqz27dtfe5UAAAAok3KHvP/+97+Kj4/X77//rj/96U+Ki4tTvXr1lJWVpaSkJCUmJqpbt2769ttv1bRp0+tZMwAAAK6i3CHvtdde08WLF7VmzRrde++9DsfGjBmjL7/8Ur169dJrr72mpUuXXnOhAAAAKL1y33iRnJysBx98sFjAK3LvvffqwQcfVFJSUrmLAwAAQPmUO+RlZ2crPDz8in3Cw8OVnZ1d3pcAAABAOZU75AUHB+vbb7+9Yp/vvvtOwcHB5X0JAAAAlFO5Q16vXr2UnJysCRMm6Pz58w7Hzp8/r4kTJyopKUkPPPDANRcJAACAsjHZbDZbeb7wt99+U7t27XTo0CEFBgaqbdu2qlOnjo4fP67t27frxIkTatSokbZt26ZatWpd77rdRk5OjgICApSdnS1/f39XlwPYDZnj6grc06IRrq4AAK5NabNHue+uDQwM1LfffquXXnpJS5cu1Zo1a+zHqlSpoieffFLTp083dMADAABwV9f0sWa33HKL3nvvPWVnZ2vPnj36+uuvtWfPHmVnZ+uf//ynbrnllutS5PTp02UymWQymZzuA8zJydGoUaMUFhYmHx8fNWzYUC+++KJyc3Odns9qtWrevHlq0aKFfH19FRQUpH79+ik9Pf261AsAAOBqZQ55U6ZM0csvv6z8/Hx7m5eXl1q0aKGYmBi1aNFCNptN48eP17Rp0665wL1792rixIny8/NzejwvL0+dOnXS7NmzFRUVpZEjRyoyMlIzZ85Uly5diu0XlKSnn35aw4cPl81m0/Dhw3Xvvfdq5cqVatOmjSwWyzXXDAAA4GplCnkbNmzQK6+8osDAQHl5eZXYz9vbW4GBgRo/fvw1PScvPz9fgwYNUsuWLdWnTx+nfWbMmKHU1FSNGTNG69at07Rp07Ru3TqNGTNG27dv1+zZsx36JyUlKSEhQbGxsdq1a5emT5+ujz76SJ999plOnTqlYcOGlbteAAAAd1GmkPfhhx+qZs2apQpCzz//vGrVqqXFixeXu7gpU6bov//9r9577z2ZzeZix202mxISElStWjVNmDDB4diECRNUrVo1JSQkOLQvWrRIkjR58mR5e3vb27t3767OnTsrMTFRR44cKXfNAAAA7qBMIe+bb77RPffcIx8fn6v29fHx0T333KOUlJRyFbZr1y5NmTJFEydOLPGzby0WizIzMxUTE1Pscq6fn59iYmKUnp6ujIwMe3tycrL92OW6desmSdq0aVO5agYAAHAXZbq7NjMzU40aNSp1//DwcH3++edlLurChQsaOHCgWrZsqZdeeqnEfkX75yIiIpwej4iI0Lp162SxWBQSEqK8vDwdO3ZMzZs3d7oyWHSeK+3Lu3Dhgi5cuGD/fU5OjqRLl5aL9il6eHjIbDarsLBQVqvV3reovaCgQH98co3ZbJaHh0eJ7X/c/yhJnp6X3raCgoJStXt5eclqtaqwsNDeZjKZ5OnpWWJ7SbUzpoozJqn4HIfc7n0y4txjTIyJMd34MZVGmUKes8FfSX5+vjw8yn4D7yuvvCKLxaKdO3c6DWNFij4yLSAgwOnxomfHFPUra39n3njjDb366qvF2hMTE1W1alVJUmhoqKKjo/X99987XPqNjIxUVFSUtm3bphMnTtjbW7ZsqbCwMG3evFlnz561t7dv3161a9dWYmKiwxsaFxcnX19fh8fWSFKPHj107tw5h32Qnp6e6tmzp06ePKmtW7fa26tXr64uXbooIyNDqamp9vagoCB16NBBFotFaWlp9nbGVPHGJEULxbnb+2TEuceYGBNjurFj2rlzp0qjTA9DvvXWW9W4cWOtXbu2VP27d++u9PR0h8KvZuvWrerYsaMmTZrksM/uiSee0AcffKCtW7fqrrvukiQtWbJEAwYM0Pjx4/X6668XO9f48eM1depUrVy5Un369FFmZqbq16+vmJgYbdmypVj/9evXKz4+XsOHD9fcuXOd1udsJS8kJEQnT560h8TK+lMFY3KvMT0zj5U8Z95+3r3eJyPOPcbEmBjTjR3TqVOnFBgYeH0fhnz33Xfr448/1s8//6yGDRtese/PP/+sjRs3auDAgaU+f0FBgQYNGqTbb79dY8eOvWr/ohW5klbeii6lFvUra39nfHx8nO5J9PLyKnbHsdlsdroSWTQxStte0p3MZWn38PBwuqpaUntJtTOmijMmOOdu75MR5x5jYkyMyTVjKvZ6per1v55//nnl5+frwQcf1MmTJ0vs99tvv+mhhx5SQUGBnn322VKfPzc3VxaLRampqfL29rY/ANlkMumDDz6QdGk51WQy6bPPPrvqHrrL9+z5+fmpXr16OnTokEOSLqk/AABARVWmlbxWrVppxIgRmjNnjpo2bapnnnlGcXFxatCggSTpl19+0VdffaWFCxfqxIkTGjVqlFq1alXq8/v4+Ogvf/mL02ObN2+WxWJRr169FBQUpIYNGyoiIkLBwcFKSUlRXl6ewx22eXl5SklJUXh4uEJCQuztnTp10tKlS5WSkqLY2FiH11i3bp0kFWsHAACoaMr82bWzZs1SlSpV9Pe//11TpkzRlClTHI7bbDaZzWaNGzfO6T65K/H19S32XLsiTzzxhCwWi8aNG2ffkydJgwcP1muvvabJkyc7fMLG5MmTlZubq5dfftnhPEOHDtXSpUs1YcIErV+/3v6svLVr1yo5OVnx8fEKCwsrU90AAADupswhz2QyaerUqfrLX/6ixYsX65tvvlFWVpYkqW7duoqJidETTzyhxo0bX/dinXnppZf0+eefa/r06dq9e7datWqlXbt2KTExUW3atNGIESMc+sfFxWnw4MFKSEhQq1at1LNnTx07dkzLli1TrVq1NG/evJtSNwAAwI1U5pBXpHHjxmVeqbsR/Pz8tGnTJk2aNEkrVqxQUlKS6tWrp9GjR2vixIny9fUt9jULFixQixYttHDhQs2dO1fVqlVTnz59NGXKlJsWTgEAAG6kMj1CBcXl5OQoICDgqrcxAzfbkDmursA9LRrh6goA4NqUNnuU/UnFAAAAcHuEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwILcLeb/88ovmzJmj+Ph4hYaGytvbW3Xr1lXfvn313XffOf2anJwcjRo1SmFhYfLx8VHDhg314osvKjc312l/q9WqefPmqUWLFvL19VVQUJD69eun9PT0Gzk0AACAm8btQt68efM0cuRIpaenKz4+XqNHj1bHjh31+eefq0OHDlq2bJlD/7y8PHXq1EmzZ89WVFSURo4cqcjISM2cOVNdunTR+fPni73G008/reHDh8tms2n48OG69957tXLlSrVp00YWi+VmDRUAAOCG8XR1AZdr27atkpOT1alTJ4f2r7/+Wl27dtWzzz6r3r17y8fHR5I0Y8YMpaamasyYMZo2bZq9/9ixYzV9+nTNnj1b48aNs7cnJSUpISFBsbGxWr9+vby9vSVJ/fv3V48ePTRs2DCtW7fuJowUAADgxjHZbDabq4sorW7duikxMVHbt29X69atZbPZ1KBBA+Xk5CgrK0t+fn72vnl5eapbt65q166tgwcP2tv79++vf//739q0aZNiY2Mdzh8XF6fk5GQdPnxYoaGhpaopJydHAQEBys7Olr+///UZKHAdDJnj6grc06IRrq4AAK5NabOH212uvRIvLy9JkqfnpQVIi8WizMxMxcTEOAQ8SfLz81NMTIzS09OVkZFhb09OTrYfu1y3bt0kSZs2bbpRQwAAALgp3O5ybUmOHDmiDRs2qF69emrRooUk2ffPRUREOP2aiIgIrVu3ThaLRSEhIcrLy9OxY8fUvHlzmc1mp/3/eF5nLly4oAsXLth/n5OTI0nKz89Xfn6+JMnDw0Nms1mFhYWyWq32vkXtBQUF+uMCqtlsloeHR4ntRectUhRyCwoKStXu5eUlq9WqwsJCe5vJZJKnp2eJ7SXVzpgqzpik4nMccrv3yYhzjzExJsZ048dUGhUi5OXn5+vxxx/XhQsXNH36dHtAy87OliQFBAQ4/bqiJcyifmXt78wbb7yhV199tVh7YmKiqlatKkkKDQ1VdHS0vv/+ex05csTeJzIyUlFRUdq2bZtOnDhhb2/ZsqXCwsK0efNmnT171t7evn171a5dW4mJiQ5vaFxcnHx9fbVmzRqHGnr06KFz584pKSnJ3ubp6amePXvq5MmT2rp1q729evXq6tKlizIyMpSammpvDwoKUocOHWSxWJSWlmZvZ0wVb0xStFCcu71PRpx7jIkxMaYbO6adO3eqNNx+T57VatXjjz+uJUuWaMiQIVq4cKH92JIlSzRgwACNHz9er7/+erGvHT9+vKZOnaqVK1eqT58+yszMVP369RUTE6MtW7YU679+/XrFx8dr+PDhmjt3rtN6nK3khYSE6OTJk/aQWFl/qmBM7jWmZ+axkufM28+71/tkxLnHmBgTY7qxYzp16pQCAwOvuifPrVfyrFarnnrqKS1ZskSPPfaY3n33XYfjRStyJa28FV1KLepX1v7O+Pj42O/s/SMvLy/7nsEiZrPZ6WXhoolR2vbLz1uedg8PD3l4FN+CWVJ7SbUzpoozJjjnbu+TEeceY2JMjMk1Yyr2eqXq5QJWq1VPPvmkPvjgA/Xr10/vv/9+sT+Yq+2hu3zPnp+fn+rVq6dDhw45JOmS+gMAAFRUbhnyigLehx9+qEceeUQfffRRiTdKBAcHKyUlRXl5eQ7H8vLylJKSovDwcIWEhNjbO3XqZD92uaLn413+aBUAAICKxu1CXtEl2g8//FAPPfSQPv744xIvPZlMJg0ePFi5ubmaPHmyw7HJkycrNzdXQ4YMcWgfOnSoJGnChAm6ePGivX3t2rVKTk5WfHy8wsLCrvOoAAAAbi63u/Fi0qRJevXVV1WtWjW98MILTq879+7dWy1btpR0acUuJiZGe/bsUXx8vFq1aqVdu3YpMTFRbdq00aZNm+Tr6+vw9UOGDFFCQoKaNWumnj176tixY1q2bJmqVaumrVu36tZbby11vTwMGe6KhyE7x8OQAVR0pc0ebnfjxc8//yxJys3N1ZQpU5z2adiwoT3k+fn5adOmTZo0aZJWrFihpKQk1atXT6NHj9bEiROLBTxJWrBggVq0aKGFCxdq7ty5qlatmvr06aMpU6aocePGN2poAAAAN43breRVNKzkwV2xkuccK3kAKjpDfqwZAAAASoeQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8A4BK//PKLHnvsMQUGBsrX11ctWrTQjh077MdtNpteeeUV1atXT76+vrrnnntksVhcWDFQsRDyUMykSZNkMpkc/ouKirIfz8rK0uOPP666devKz89PrVq10ooVK1xYMYCK5vTp04qJiZGXl5fWrl2rH3/8UbNmzVLNmjXtfWbMmKG33npL7777rr777jv5+fmpW7duOn/+vAsrByoOT1cXAPfUrFkzbdiwwf57T8//myoDBw7UmTNntGrVKt1yyy1asmSJHn74Ye3YsUPR0dGuKBdABTN9+nSFhIRo8eLF9rbw8HD7r202m+bMmaP/+Z//0QMPPCBJ+vDDD1WnTh199tlnevTRR296zUBFw0oenPL09FTdunXt/91yyy32Y998843++te/qm3btmrUqJH+53/+RzVq1NDOnTtdWDGAimTVqlVq3bq1HnroIdWuXVvR0dFatGiR/fihQ4eUlZWle+65x94WEBCgdu3aaevWra4oGS52tatMRWw2m7p37y6TyaTPPvvs5hfqRgh5cMpisSg4OFiNGjXSgAEDdOTIEfuxDh06aNmyZTp16pSsVquWLl2q8+fPq3Pnzq4rGECFkp6ernfeeUcRERFat26dnn32WQ0fPlwffPCBpEvbQiSpTp06Dl9Xp04d+zFUPs2aNdOxY8fs/23ZsqVYnzlz5shkMrmgOvfD5VoU065dO73//vuKjIzUsWPH9Oqrr+ruu+/W3r17Vb16dS1fvlyPPPKIAgMD5enpqapVq+rTTz9VkyZNXF06gArCarWqdevWmjp1qiQpOjpae/fu1bvvvqtBgwa5uDq4q6KrTCVJTU3VrFmztGPHDtWrV+8mVuaeWMlDMd27d9dDDz2k22+/Xd26ddOaNWt05swZLV++XJI0YcIEnTlzRhs2bNCOHTs0atQoPfzww/rhhx9cXDmAiqJevXpq2rSpQ9ttt91mv2pQ9I38+PHjDn2OHz9+xW/yMLYrXWX6/fff1b9/f/3jH/9gjvwvQh6uqkaNGrr11lt14MABHTx4UPPnz9d7772nrl276o477tDEiRPVunVr/eMf/3B1qQAqiJiYGKWlpTm07d+/X2FhYZIu3YRRt25dffXVV/bjOTk5+u6779S+ffubWivcQ9FVpi+//FLvvPOODh06pLvvvltnz56VJI0cOVIdOnSw36gDLteiFHJzc3Xw4EE9/vjj+v333yVJHh6OPx+YzWZZrVZXlAegAir6hjx16lQ9/PDD2rZtmxYuXKiFCxdKkkwmk0aMGKHXX39dERERCg8P14QJExQcHKzevXu7tni4RPfu3e2/vv3229WuXTuFhYVp+fLlCgoK0saNG7V7924XVuh+CHko5m9/+5vuv/9+hYWFKTMzUxMnTpTZbFa/fv1Uo0YNNWnSRE8//bRmzpypwMBAffbZZ1q/fr1Wr17t6tIBVBBt2rTRp59+qnHjxum1115TeHi45syZowEDBtj7vPTSS8rLy9PQoUN15swZdezYUV9++aWqVKniwsrhLv54lemHH37QwYMHVaNGDYc+ffv21d13363k5GSX1OhqJpvNZnN1ERVZTk6OAgIClJ2dLX9/f1eXc108+uij2rx5s3777TcFBQWpY8eOmjJliho3bizp0p6IsWPHasuWLcrNzVWTJk30t7/9TY8//riLK8cfDZnj6grc06IRrq4AwPWQm5ur0NBQTZo0SQ8//LBOnjzpcLxFixaaO3eu7r//fodnMBpBabMHK3koZunSpVc8HhERwSdcAABuqitdZQoKCnJ6s0VoaKjhAl5ZEPIAAIDbO3r0qPr16+dwlenbb79VUFCQq0tzW4Q8AADg9q52lely7EYj5AEA/hf7OJ1jHycqKkJeBcE/vs7xjy8AAM7xMGQAAAADYiUPAACUC1eZnHOXq0ys5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECEPAAAAAMi5AEAABgQIQ8AAMCACHkAAAAGRMgDAAAwIEIeAACAARHyAAAADIiQBwAAYECVNuRt375dPXr0UI0aNeTn56e77rpLy5cvd3VZAAAA14WnqwtwhaSkJHXr1k1VqlTRo48+qurVq2vFihV65JFHlJGRodGjR7u6RAAAgGtS6VbyCgoKNGTIEHl4eGjz5s1auHChZs2apT179ujWW2/Vyy+/rMOHD7u6TAAAgGtS6ULexo0bdfDgQfXv318tW7a0twcEBOjll1/WxYsX9cEHH7iuQAAAgOug0oW85ORkSVJ8fHyxY926dZMkbdq06WaWBAAAcN1VupBnsVgkSREREcWO1a1bV9WqVbP3AQAAqKgq3Y0X2dnZki5dnnXG39/f3seZCxcu6MKFC8XOd+rUKeXn50uSPDw8ZDabVVhYKKvVau9b1F5QUCCbzWZvN5vN8vDwKLE9Pz9fF897lWO0xvfbb/n2X5tMJnl6espqtaqwsLBYe0nvx/V8n/7I0/PSX6+CgoJStXt5eZVYe3nGdPG8+Up/dJXWH+eM5Pr3yZ3m3sXzle7n/lI5fdq93id3mnsXz1/pT67yOnPmxr5Pp06dkiSH98QZk+1qPQwmPj5e69evl8ViUZMmTYodr1+/vnJzc0sMepMmTdKrr756o8sEAAC4ooyMDDVo0KDE45VuJa9oBa+kEJeTk6OaNWuW+PXjxo3TqFGj7L+3Wq06deqUAgMDZTKZrm+xbignJ0chISHKyMiQv7+/q8tBBcCcQVkxZ1BWlW3O2Gw2nT17VsHBwVfsV+lCXtFePIvFojvvvNPhWFZWlnJzc9W2bdsSv97Hx0c+Pj4ObTVq1Ljudbo7f3//SvEXCdcPcwZlxZxBWVWmOVPStrM/qnQbMDp16iRJSkxMLHZs3bp1Dn0AAAAqqkoX8rp27apGjRppyZIlSk1NtbdnZ2dr6tSp8vb21sCBA11XIAAAwHVQ6S7Xenp6KiEhQd26dVNsbKzDx5odPnxYM2fOVMOGDV1dptvy8fHRxIkTi12yBkrCnEFZMWdQVswZ5yrd3bVFtm3bpokTJ+qbb75Rfn6+WrRooVGjRumRRx5xdWkAAADXrNKGPAAAACOrdHvyAAAAKgNCHgAAgAER8gAAAAyIkAcAAGBAhDwAAAADIuThqopuwLbZbOJmbAAAKgZCHq7KZDLZ/1/0awC43op+iCwsLHRxJYAx8Jw8XNGvv/6qH374QRaLRWfPnlW7du0UGRmpwMBAeXpe+sAUq9UqDw9+XsAlzAcAcA+EPJRo7dq1mjJlir755huH9sDAQHXt2lWPPPKI7rvvPnl5ebmoQrg7Ah9K68svv9TevXu1Z88eBQUFqW3btmrSpIlCQ0MVGBgos9ksm83G1QTYFRYWymw2u7oMt0bIg1MZGRnq3Lmz8vLy9MQTTyguLk7p6enavXu39uzZo++//14XLlzQbbfdpvHjx6tv377y8fHhH+FK7Pjx45oxY4bi4+PVrl071ahRw36saD8ngQ+XO3PmjN544w39/e9/l9lsdrhUW6tWLcXExKhPnz7q3bu3w5xC5XX5D4+l/felMn5/8nR1AXBPCxYs0OnTp5WQkKA///nPDseOHj2qb775RqtWrdKSJUv02GOP6ejRo3rppZcq3V8g/J+3335bs2fP1qeffqqmTZuqc+fO6tSpk26//Xb5+PjY54bVapXNZpPZbFZycrLOnz+ve++918XVw1UWLVqk+fPnq3fv3ho+fLiCg4O1e/dupaWlafv27dq6dau++OILzZs3TxMmTFDv3r1dXTJcbMGCBUpOTtbAgQPVqVMnVatWzeHfF0lOA19l/P7ESh6cuuuuu+Tr66tPPvlEt9xyiwoKCmQymYotjSclJWn06NH68ccf9fbbb+upp55yUcVwtejoaP34449q1aqVdu3apfz8fIWFhSkmJkZxcXGKiYlRVFSUvf/vv/+ufv36afXq1crLy1OVKlVcWD1cpWHDhmrevLk++OADBQYGOhzLzMzU7t27tWrVKr333nsqLCzUwoULNXjwYBdVC3cQHh6uw4cPy8fHR3fccYfi4+PVo0cPtWvXziHIFRQUyNPTU7///rsWLlyoO+64Q3FxcS6s/OYj5KGY3Nxc9enTR0ePHtXOnTtVtWpVh+Xxy5fGd+/era5du+ruu+/W559/XimXxCu7jIwMxcbGKjAwUFu3btXOnTu1Zs0arVq1St9//708PDzUrFkzxcbGKjY2Vt26dVNaWpp69eqlNm3aaNWqVa4eAlxg3759atOmjYYPH64pU6ZIcr4Sc/HiRW3YsEF//etfdebMGa1evVrt27d3Sc1wrf/+979q0aKF7rzzTtWsWVMbNmyQJPn5+SkmJkY9evRQfHy8ww+UW7ZsUWxsrDp06KAtW7a4qnSXYIMMiqlWrZruvPNOpaWlaenSpZKKL30X/d5qtSo6OlqxsbHat2+fDh8+TMCrhI4dO6acnBw1b95cXl5eatOmjSZNmqTExEStWbNGQ4YMUXZ2tv7xj3/oiSee0P33369x48bp+PHjGjp0qKvLh4vYbDbVqFFDBw8elHRp5UVSsR8ovb291aNHD7355ps6ffq0vv76a5fVDNf64YcfJEn9+/dXYmKi9u3bp2nTpqlJkyZKTEzUiBEj1KVLF/Xv318fffSRTp8+rW3btkmSxo0b58rSXYKVPDj1yy+/qHv37tq7d6+GDRumJ554Qk2bNnW4pFa0FJ6Tk6PBgwfru+++0+HDh11YNVzlwIEDGjNmjPr27av+/fsXO56fn6/MzEx9/fXX+uKLL7RhwwadPn1aNWrU0KlTp1xQMdzFXXfdpR9//FHLli1T9+7dHY4VXRUoupJw6tQptW7dWnfeeac++eQTF1UMV1q4cKGeeeYZ/b//9/+KzZft27fr3//+t/7zn//o6NGjkqSIiAjl5OTo3LlzOnPmjAsqdi1W8uBU/fr19dprr6lhw4aaP3++nn76ac2cOVPJyck6fPiwzp8/b39O3hdffKHk5ORif+FQeTRp0kTvvfeeunXr5vS4l5eXwsLC1L9/fy1btkxTp06VJPXr1+9mlgk3UrS+8NZbb8nf3189e/bUyJEjtW3bNp0/f17S/22Uz8/PlySlpaXpwoULCg4Odk3RcCmbzabbb79dI0aM0K233urQLklt2rTRm2++qf379+uLL77QwIEDdfz4cR0/flyPP/64q8p2KVby4ODy/XSnTp3SG2+8oeXLlysjI0NBQUFq3ry5goODVbVqVZ07d07Lly9XeHi4PvvsM0VGRrqweriCsz2YhYWFMplMJT7S4KWXXtLMmTO1Y8cOtWrV6maUCTdVWFiojz/+WOPGjVNWVpaaNm2q+Ph4dejQQU2bNlVUVJQ8PDz0yy+/6MUXX9Qnn3yi7777jnlTieXm5srb21ve3t7Fjl3+79GwYcP09ttva9euXWrZsuVNrNI9EPJQTNFfkqNHjyo4OFgeHh7au3evVq9ereTkZP3000/KyMiQJNWsWVMtW7bUW2+9pWbNmrm4crhK0ZzJyspS7dq1HcJdYWGhPDw87P/wHj16VD179lRmZqZOnDjhqpLhZk6cOKH58+dr+fLl2r9/v6pWrar69eurWrVqqlWrlvbt26cTJ07oySef1Ntvv+3qcuHGiv49OnjwoB555BFlZ2fLYrG4uiyXIOTBrqCgQCkpKXrvvfe0f/9+mUwmVa1aVW3atNHDDz+s6Oho2Ww2ZWRk6Ny5c0pPT1dUVJRCQkLk6enJXbWV0OVzxsPDQ76+vrrjjjvUt29fdejQodjXnDx5Uh999JGCg4P1yCOPuKBquBObzSar1Sqz2axz587JYrFo+/btSklJ0Xfffad9+/YpKChIISEhGjx4sB577DH5+fm5umxUAKtXr1avXr304osvavr06a4uxyUIebCbOXOmJk+erLNnz6pJkyYym81KS0uzH2/atKmee+45Pfjgg6pdu7YLK4W7uNqciYqK0pAhQ9SvXz/VrVvX3n7x4kV5enryCRhwymq16vz58/L29lZ2draysrK4UgC70i4oHD9+XF9++aXuv/9+1apV6yZU5n4IeZAkHTp0SC1atFCrVq30wQcfyNvbW3Xq1FFWVpa++OILffLJJ0pOTpYkxcXFafr06WrdurVri4ZLlWXOdOnSRTNmzGAfFXTu3DkdOXJEoaGh8vX1dThmtVplMpns38Av/2bOZyFXTleaM1dT2T/flpAHSdIrr7yiBQsWaMmSJeratauk4v/A/vDDD5o5c6aWL1+usLAw/etf/9Kdd97pqpLhYtcyZ7i0X3lNmzZNK1as0J///GfdddddioyMVJ06dRy+ERd9WyqaIydOnFDNmjXtd/SjcinNnLkcc+YSQh4kSX379lVqaqqSkpIUGhpqfwbeH/fLFJk7d65GjhypQYMGafHixS6sGq7EnEF5NGjQQJmZmTKbzQoICFCHDh0UHx+vdu3aqVGjRsU+2iwvL0+TJk3Sb7/9poSEBFbyKqFrmTOLFi2q1Ct5lTviwi46OlqffvqpcnNzJcn+088fP6+2aPXlhRde0Ndff62NGzcqPT1djRo1clndcB3mDMpq//79ys7OVvv27dW/f3+tX79eW7du1erVqxUaGqrOnTvrnnvuUXR0tOrXr68aNWpo7969WrRokTp37kzAq4Sudc5U5oAnEfLwv4o+tHnAgAGaNWuWOnbs6PQZREX7GyIjI7V27Vr7N3hUPswZlNX+/ft1/vx5xcfH6/nnn9d9992ntLQ0bd26VRs3btSKFSv0r3/9S02bNlWXLl1077336quvvlJOTo6GDBni6vLhAsyZa2QDbDZbQUGBbfTo0TaTyWS77bbbbPPnz7dlZWU57Xvq1CnbwIEDbUFBQTe5SrgT5gzK6pNPPrGZTCbbsmXLHNovXrxos1gstv/85z+2F154wXbHHXfYvL29bX5+fraqVavaatas6aKK4WrMmWvDnjw4WLBggf7+978rPT1dwcHB6tOnj7p3766QkBCZzWbVqFFD8+bN05w5c/Tcc89p1qxZri4ZLsacQWnZbDbt27dPVapUUXh4uNMbcPLy8rR//36lpaVp8eLFWr9+vYYNG6a33nrLRVXDlZgz14aQBwc2m00HDhzQokWLtHTpUvuHPNeuXVteXl46duyYrFar+vXrp+nTp6tBgwYurhiuxpzB9eDsm/fw4cM1f/587dy5U9HR0S6qDO6KOXN1hDyUKC8vT9u2bdOqVauUmZmpX3/9Vf7+/nr44YfVt29fValSxdUlws0wZ3Ctip6F9/PPP+uBBx7Q6dOndeTIEVeXBTfGnCkZN16gRH5+foqLi1NcXJzy8/Pl5eXl6pLg5pgzuFZFd9D+8ssvys/P13PPPefiiuDumDMlYyUPAOB2bDabjh49qlq1avFZtSgV5kxxhDwAAAAD4smSAAAABkTIAwAAMCBCHgAAgAER8gAAAAyIkAcAAGBAhDwAAAADIuQBAAAYECEPAADAgAh5AAAABvT/AcUe2yQqRnKNAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 700x500 with 1 Axes>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = ClassicalRegister(2)     # The solution at the end has only 2 bits\n",
    "algo4 = QuantumCircuit(q, c) # Readies us to construct an algorithm to run on the quantum computer\n",
    "\n",
    "add_prepare(algo4)           # Step 1 of Grover's: prepare the state vector\n",
    "add_verify_with_h(algo4)     # Step 2 of Grover's: apply the verify function and flip the solution row negative\n",
    "add_amplify(algo4)           # Step 3 of Grover's: amplify negative rows\n",
    "\n",
    "algo4.measure(q[0:2], c)     # Measure the two qubits 0 and 1, and get some bits\n",
    "result = execute(algo4, backend, shots=1000).result()    # Run this all 1,000 times\n",
    "plot_histogram(result.get_counts(algo4))                 # Show a histogram of the results"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bda504c5",
   "metadata": {},
   "source": [
    "You can go back and set up the verify function differently, and you'll see that the algorithm will still reveal the correct solution in the measurements.\n",
    "\n",
    "In this way, the quantum computer hasn't needed to brute force the answer by trying the verification function over and over again until it finds the answer. The fact that the verification function can be used to make a row in the state vector negative was enough to allow this negative value to be amplified, and set up a probability distribution that makes the answer pop out more often in the measurements.\n",
    "\n",
    "As I mentioned at the start, it may be that the \n",
    "```\n",
    "add_verify_with_h(algo4)\n",
    "add_amplify(algo4)\n",
    "```\n",
    "steps need to be repeated as the number of qubits increases. However, it won't need to be done as frequently as once per qubit, so it will continue to be more efficient than the brute force approach that a digital computer has to use."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e1733a1",
   "metadata": {},
   "source": [
    "### In conclusion\n",
    "We added another two operations to our set, and have seen how to use them on a quantum computer to figure out the solution to a problem giving the digital computing function that verifies solutions to that problem. Here is the complete set of operations over these four notebooks:\n",
    "\n",
    "| Operation | Short-hand description | Specified by | Detailed description |\n",
    "| :- | :- | :- | :- |\n",
    "| H | \"half\" | 1 qubit | For all pairs of rows that differ only by the value of a specific qubit, replace the first row value into a new value that is the *sum* of the original values divided by $\\sqrt{2}$, and the second row value into the *difference* between the original values divided by $\\sqrt{2}$. |\n",
    "| CX | \"constrained swap\" | 2 qubits | For all pairs of rows where the first qubit specified is in the $\\rvert1\\rangle$ state, and where otherwise the rows differ only by the value of the second qubit specified, swap the rows in the pair. |\n",
    "| RY | \"relative swap\" | 1 angle and 1 qubit | For all pairs of rows that differ only by the value of a specific qubit, swap a fraction $f$ of the value from the first row to the second, and bring the opposite fraction (i.e. $1-f$) from the second row but with the sign flipped, where $f$ is specified as the angle $2 \\times arcsin(\\sqrt{f})$. If $f$ is $1.0$, the angle will be $\\pi$. |\n",
    "| X | \"swap\" | 1 qubit | For all pairs of rows that differ only by the value of a specific qubit, swap the values in the pair. |\n",
    "| CCX | \"doubly constrained swap\" | 3 qubits | For all pairs of rows where both the first and second qubit specified are in the $\\rvert1\\rangle$ state, and where otherwise the rows differ only by the value of the third qubit specified, swap the rows in the pair. |\n",
    "| Z | \"flip\" | 1 qubit | For all pairs of rows that differ only by the value of a specific qubit, flip the sign on the second row of each pair. |\n",
    "| CCZ | \"doubly constrained flip\" | 3 qubits | For all pairs of rows where both the first and second qubit specified are in the $\\rvert1\\rangle$ state, and where otherwise the rows differ only by the value of the third qubit specified, flip the sign on the second row of each pair. |\n",
    "\n",
    "That's all for now. Hope you've enjoyed working along with me in seeing how quantum computers can perform computation by changing the probabilities of the different possible outcomes of their qubits, and how often this approach allows quantum computers to solve a problem more efficiently than a digital computer."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}