tutorial/114_grover_en.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "014_algo_grover.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    }
  },
  "cells": [
    {
      "metadata": {
        "colab_type": "text",
        "id": "NjHnSAbHrInP"
      },
      "cell_type": "markdown",
      "source": [
        "# Grover's algorithm\n",
        "Grover's algorithm is a search algorithm to find out the data efficiently from random data.\n",
        "\n",
        "The basic step of grover's algorithm is \n",
        "\n",
        "1. Making superposition  \n",
        "2. Marking of the data you want to find  \n",
        "3. Amplitude amplification  \n",
        "\n",
        "Repeating the step2 and 3 properly, we can get the correct result."
      ]
    },
    {
      "metadata": {
        "id": "CJhIv6UdASWQ",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Marking\n",
        "Here we see 2qubits grover's algorithm. Combination of 2 binary numbers are 00, 01, 10 and 11. Now we see the basic marking circuit to mark the state vector.\n",
        "\n",
        "To do marking we prepare a diagonal matrix which is one element is -1 and others are 1. By using H gate, CZ gate and S gate we can realize it.\n"
      ]
    },
    {
      "metadata": {
        "id": "oXg3hf3yAkMS",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Let's see on blueqat."
      ]
    },
    {
      "metadata": {
        "id": "j_E32CZHht9a",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "!pip install blueqat"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "7Q4HfcrWmQ2n",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Now we see the circuit one by one. We can check the unitary matrix of the circuit by running .run_with_sympy_unitary(). And we usually start from the diagonal matrix of CZ gate first and changing it."
      ]
    },
    {
      "metadata": {
        "id": "mV6JWcmHCMY2",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        },
        "outputId": "0587b425-fe85-40f0-d952-f9630cc48055"
      },
      "cell_type": "code",
      "source": [
        "from blueqat import Circuit\n",
        "\n",
        "\n",
        "'''\n",
        "#marking on 11\n",
        "\n",
        "-------*-----\n",
        "-------Z-----\n",
        "'''\n",
        "\n",
        "Circuit(2).cz[0,1].run_with_sympy_unitary()"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Matrix([\n",
              "[1, 0, 0,  0],\n",
              "[0, 1, 0,  0],\n",
              "[0, 0, 1,  0],\n",
              "[0, 0, 0, -1]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 18
        }
      ]
    },
    {
      "metadata": {
        "id": "u5zYyzFPiwj8",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        },
        "outputId": "c16ebec3-7568-45c6-e49f-ca6de857ff0d"
      },
      "cell_type": "code",
      "source": [
        "'''\n",
        "#marking on 01\n",
        " \n",
        "----S--*--S---\n",
        "-------Z-------\n",
        "'''\n",
        "\n",
        "Circuit(2).s[0].cz[0,1].s[0].run_with_sympy_unitary()"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Matrix([\n",
              "[1,  0, 0, 0],\n",
              "[0, -1, 0, 0],\n",
              "[0,  0, 1, 0],\n",
              "[0,  0, 0, 1]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 17
        }
      ]
    },
    {
      "metadata": {
        "id": "iyRwxTkBoRKZ",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        },
        "outputId": "4ad9d23f-c23f-40dd-9d10-f069e5f77c50"
      },
      "cell_type": "code",
      "source": [
        "'''\n",
        "#marking on 10\n",
        " \n",
        "--------*------\n",
        "----S--Z--S---\n",
        "'''\n",
        "\n",
        "Circuit(2).s[1].cz[0,1].s[1].run_with_sympy_unitary()"
      ],
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Matrix([\n",
              "[1, 0,  0, 0],\n",
              "[0, 1,  0, 0],\n",
              "[0, 0, -1, 0],\n",
              "[0, 0,  0, 1]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 19
        }
      ]
    },
    {
      "metadata": {
        "id": "wrh29In4me-W",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        },
        "outputId": "44bbed8d-83bd-4375-9cf1-81996ba4c1ab"
      },
      "cell_type": "code",
      "source": [
        "\n",
        "'''\n",
        "#00\n",
        " \n",
        "----S--*--S--\n",
        "----S--Z--S--\n",
        "'''\n",
        "\n",
        "Circuit(2).s[:].cz[0,1].s[:].run_with_sympy_unitary()"
      ],
      "execution_count": 41,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Matrix([\n",
              "[1,  0,  0,  0],\n",
              "[0, -1,  0,  0],\n",
              "[0,  0, -1,  0],\n",
              "[0,  0,  0, -1]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 41
        }
      ]
    },
    {
      "metadata": {
        "id": "60TxX_5bvL2E",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "The result is inversed on the sign. We can think about global phase that flips all the minus sign to plus and plus sign to minus."
      ]
    },
    {
      "metadata": {
        "id": "U1uxGVsCCi85",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Amplitude amplification\n",
        "Ampitude amplification is a circuit which is -1 on diagonal and +1 on offdiagonal. Doing this we can get the marked state vector.\n",
        "\n",
        "The amplitude amplification circuit on 2qubits is like this,"
      ]
    },
    {
      "metadata": {
        "id": "uEO1xB4OCkcK",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        },
        "outputId": "b29840b6-9400-4830-e93c-0f0f9b84199f"
      },
      "cell_type": "code",
      "source": [
        "'''\n",
        "--H-X-*-X-H--\n",
        "--H-X-Z-X-H--\n",
        "'''\n",
        "\n",
        "Circuit(2).h[:].x[:].cz[0,1].x[:].h[:].run_with_sympy_unitary()"
      ],
      "execution_count": 44,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Matrix([\n",
              "[ 1/2, -1/2, -1/2, -1/2],\n",
              "[-1/2,  1/2, -1/2, -1/2],\n",
              "[-1/2, -1/2,  1/2, -1/2],\n",
              "[-1/2, -1/2, -1/2,  1/2]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 44
        }
      ]
    },
    {
      "metadata": {
        "id": "yd5MaoRKCuWS",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Circuit\n",
        "Now we have the total circuit. First we prepare the state vector as |+> applying H gate on every qubit."
      ]
    },
    {
      "metadata": {
        "id": "3eRpgppa_1FI",
        "colab_type": "code",
        "outputId": "5960f694-2a20-4803-803c-9d9dbf180827",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "cell_type": "code",
      "source": [
        "from blueqat import Circuit\n",
        "\n",
        "#Amplitude amplification\n",
        "a = Circuit(2).h[:].x[:].cz[0,1].x[:].h[:].m[:]\n",
        "\n",
        "'''\n",
        "#00 Circuit\n",
        "\n",
        "--H--S--*--S----H-X-*-X-H--\n",
        "--H--S--Z--S----H-X-Z-X-H--\n",
        "'''\n",
        "\n",
        "(Circuit(2).h[:].s[:].cz[0,1].s[:] + a).run(shots=100)"
      ],
      "execution_count": 46,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Counter({'00': 100})"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 46
        }
      ]
    },
    {
      "metadata": {
        "id": "WcvE1NcLC4H7",
        "colab_type": "code",
        "outputId": "7014d538-0fab-4464-ba86-e127b72811b5",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "cell_type": "code",
      "source": [
        "'''\n",
        "#01 Circuit\n",
        "--H-----*-------H-X-*-X-H--\n",
        "--H--S--Z--S---H-X-Z-X-H--\n",
        "'''\n",
        "\n",
        "(Circuit(2).h[:].s[1].cz[0,1].s[1] + a).run(shots=100)"
      ],
      "execution_count": 47,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Counter({'01': 100})"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 47
        }
      ]
    },
    {
      "metadata": {
        "id": "N4BvigvuDHfu",
        "colab_type": "code",
        "outputId": "96cd45a7-65da-45df-ecbb-85ee97f6e68f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "cell_type": "code",
      "source": [
        "'''\n",
        "#10 Circuit\n",
        "--H--S--*--S----H-X-*-X-H--\n",
        "--H-----Z--------H-X-Z-X-H--\n",
        "'''\n",
        "(Circuit(2).h[:].s[0].cz[0,1].s[0] + a).run(shots=100)"
      ],
      "execution_count": 48,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Counter({'10': 100})"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 48
        }
      ]
    },
    {
      "metadata": {
        "id": "wQ94cpSODMyP",
        "colab_type": "code",
        "outputId": "894cbb13-f0f5-4601-fff7-c614e77340dd",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "cell_type": "code",
      "source": [
        "'''\n",
        "#11 Circuit\n",
        "--H-----*-------H-X-*-X-H--\n",
        "--H-----Z-------H-X-Z-X-H--\n",
        "'''\n",
        "(Circuit(2).h[:].cz[0,1] + a).run(shots=100)"
      ],
      "execution_count": 49,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Counter({'11': 100})"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 49
        }
      ]
    },
    {
      "metadata": {
        "id": "lP9JKP_xDgai",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "And we all succeded to get the result."
      ]
    }
  ]
}