tutorial-ja/101_subtractor_ja.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NjHnSAbHrInP"
   },
   "source": [
    "# ひき算\n",
    "量子コンピュータには従来のコンピュータと同じ計算もできるという特徴があります。ひき算の回路を確認します。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 今回学ぶこと\n",
    "1. 量子ゲートを使って二進数のひき算を実装\n",
    "2. 量子の重ね合わせを使って1つの回路で複数のひき算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Blueqatのインストール\n",
    "pipからBlueqatをインストールします。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "collapsed": true,
    "id": "OF-AmKpXtgSJ"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: blueqat in /home/ec2-user/anaconda3/envs/python3/lib/python3.6/site-packages (0.3.13)\n",
      "Requirement already satisfied: numpy~=1.12 in /home/ec2-user/anaconda3/envs/python3/lib/python3.6/site-packages (from blueqat) (1.18.3)\n",
      "Requirement already satisfied: scipy>=1.1.0 in /home/ec2-user/anaconda3/envs/python3/lib/python3.6/site-packages (from blueqat) (1.1.0)\n",
      "\u001b[33mWARNING: You are using pip version 20.0.2; however, version 20.1 is available.\n",
      "You should consider upgrading via the '/home/ec2-user/anaconda3/envs/python3/bin/python -m pip install --upgrade pip' command.\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "!pip install blueqat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "PKhFYi-drld1"
   },
   "source": [
    "## 二進数のひき算\n",
    "たし算は符号を判定するccxゲートと、位の足し合わせを実行するcxゲートを使います。今回はa-b=cdという二進数のひき算の量子回路を行います。今回はaとbの値によって4種類のひき算を実装します。それぞれのひき算は、\n",
    "\n",
    "0-0 = 00 => 0000  \n",
    "0-1 = 11 => 0111  \n",
    "1-0 = 01 => 1001  \n",
    "1-1 = 00 => 1100  \n",
    "\n",
    "となります。4量子ビットのビット列で表現し、前半の2量子ビットが入力値aとbで、後半の2量子ビットが出力値cとdです。aとbを入力する回路と、実際に引き算を実現する回路を別に作り、何度か使い回します。1のようなデータの入力はXゲートを使って0を反転させて実装します。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ひき算の回路部分はこのようになります。*はコントロールビットです。\n",
    "\n",
    "```\n",
    "a ---X---*---X---*------- a\n",
    "b -------*-------|---*--- b\n",
    "0 -------X-------|---|--- c\n",
    "0 ---------------X---X--- d\n",
    "```\n",
    "\n",
    "aとbにXゲートを使ってデータを入れると、ccx回路で符号の判定、cx回路で位の引き算を行います。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "O674HiVxjc7P",
    "outputId": "63d75a71-0b78-4b7b-b759-56b2d018e284"
   },
   "outputs": [],
   "source": [
    "#ツールの読み込み\n",
    "from blueqat import Circuit\n",
    "\n",
    "#ひき算部分を実現します。\n",
    "substractor = Circuit().x[0].ccx[0,1,2].x[0].cx[0,3].cx[1,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "O674HiVxjc7P",
    "outputId": "63d75a71-0b78-4b7b-b759-56b2d018e284"
   },
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Counter({'0000': 100})"
     },
     "metadata": {},
     "execution_count": 2
    }
   ],
   "source": [
    "#0-0\n",
    "(Circuit() + substractor).m[:].run(shots=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "xlTAVvSt3iZv",
    "outputId": "c6e6810e-4569-4849-da61-ab41e72f83c0"
   },
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Counter({'0111': 100})"
     },
     "metadata": {},
     "execution_count": 3
    }
   ],
   "source": [
    "#0-1\n",
    "(Circuit().x[1] + substractor).m[:].run(shots=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "BtkqFj8n3kBS",
    "outputId": "5db803d7-a2dc-417b-95c2-eacf35e160c2"
   },
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Counter({'1001': 100})"
     },
     "metadata": {},
     "execution_count": 5
    }
   ],
   "source": [
    "#1-0\n",
    "(Circuit().x[0] + substractor).m[:].run(shots=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "JnmWCnOf3xGw",
    "outputId": "b89c5e8a-899b-47da-faed-dc5a3a5035e5"
   },
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Counter({'1100': 100})"
     },
     "metadata": {},
     "execution_count": 6
    }
   ],
   "source": [
    "#1-1\n",
    "(Circuit().x[0,1] + substractor).m[:].run(shots=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "OPe8FDu04AtN"
   },
   "source": [
    "このように、ひき算が実装できました。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "OPe8FDu04AtN"
   },
   "source": [
    "## 重ね合わせを利用したひき算\n",
    "ここで、Xゲートでデータを一つ一つ入れる代わりに、Hゲートを使ってひき算をしてみます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Counter({'0000': 25, '1100': 23, '1001': 25, '0111': 27})"
     },
     "metadata": {},
     "execution_count": 7
    }
   ],
   "source": [
    "#Xゲートの代わりにHゲートを入力に使う\n",
    "(Circuit().h[0,1] + substractor).m[:].run(shots=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "アダマールゲートを利用すると4つのひき算が大体1/4ずつ答えとして出てきました。このように汎用ひき算回路を作ると、重ね合わせ状態を利用した計算を実行できます。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## もつれを利用したひき算\n",
    "次にHゲートの代わりにa-b=0となるたし算を量子のもつれを使って行ってみます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Counter({'1100': 51, '0000': 49})"
     },
     "metadata": {},
     "execution_count": 8
    }
   ],
   "source": [
    "#00と11のもつれを作る\n",
    "(Circuit().h[0].cx[0,1] + substractor).m[:].run(shots=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "このように、入力値が00と11がもつれているので、この2つのひき算が約1/2ずつ出てきます。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "--------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 解説：回路の作成（符号）\n",
    "まずは上の符号から作成します。\n",
    "符号は、0, 1, 0, 0 の順になっています。\n",
    "\n",
    "表で表すと以下になります。\n",
    "\n",
    "|X|Y|符号|\n",
    "|:-:|:-:|:-:|\n",
    "|0|0|0|\n",
    "|0|1|1|\n",
    "|1|0|0|\n",
    "|1|1|0|\n",
    "\n",
    "次にXの桁を反転させると\n",
    "\n",
    "|X|Y|符号|\n",
    "|:-:|:-:|:-:|\n",
    "|1|0|0|\n",
    "|1|1|1|\n",
    "|0|0|0|\n",
    "|0|1|0|\n",
    "\n",
    "これを見ると CCXゲートと同じことがわかります。\n",
    "(CCXは入力の頭2つのビットが1ならば3番目のビットを反転させる)\n",
    "\n",
    "このことから入力が 11 の場合は以下の回路を考えることができます。\n",
    "\n",
    "<img src=\"./img/008/008_02_0.png\" width=\"23%\">\n",
    "\n",
    "上から2ビットを入力、残りの1ビットを出力だと考えると上の回路から 1 が出力されるのがわかります。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 解説：回路の作成（２桁目）\n",
    "次にもう一つのくらいを作成します。\n",
    "2桁目を見ると、0, 1, 1, 0 の順になっています。\n",
    "\n",
    "表で表すと以下になります。\n",
    "\n",
    "|X|Y|X+Yの1桁目|\n",
    "|:-:|:-:|:-:|\n",
    "|0|0|0|\n",
    "|0|1|1|\n",
    "|1|0|1|\n",
    "|1|1|0|\n",
    "\n",
    "これを見ると CXゲートと同じことがわかります。\n",
    "(左辺がCXの入力で右辺が出力の2番目のビット)\n",
    "\n",
    "このことから入力が 10 の場合は以下の回路を考えることができます。\n",
    "\n",
    "<img src=\"./img/008/008_02_1.png\" width=\"27%\">\n",
    "\n",
    "上から2ビットを入力、残りの1ビットを出力だと考えると上の回路から 1 が出力されるのがわかります。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 解説：回路の作成（全体）\n",
    "最後に上の二つの回路をまとめます。\n",
    "\n",
    "入力を 00 としてまとめた回路を以下に示します。\n",
    "\n",
    "<img src=\"./img/008/008_02_3.png\" width=\"40%\">\n",
    "\n",
    "上2ビットを入力、残りの2ビットが出力です。\n",
    "始めの CCX は符号の部分で残りの 2つの CX は引き算の部分です。   \n",
    "符号を検知するためにXゲートを施したのでCCXした後は再びXをして戻しています。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 解説：重ね合わせ回路の実装\n",
    "量子の重ね合わせを用いると4パターンを一気に操作することができます。\n",
    "\n",
    "式としては以下の物を考えます。\n",
    "\n",
    "<img src=\"./img/009/009_02_0.png\" width=\"35%\">\n",
    "\n",
    "見てわかる通り右辺に入力の4パターンが出てきました。\n",
    "この性質を用いて実装します。\n",
    "\n",
    "回路は以下のようになります。\n",
    "\n",
    "<img src=\"./img/009/009_02_2.png\" width=\"40%\">\n",
    "\n",
    "今まで Xゲートを施していた部分を Hゲートにして 4パターンを作っています。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (応用) 一般の引き算\n",
    "一般の10進数同士で引き算を実装します。  \n",
    "引き算回路は足し算回路を逆にすることで実装できます。\n",
    "\n",
    "足し算回路は以下のようになります。\n",
    "\n",
    "<img src=\"https://qiita-user-contents.imgix.net/https%3A%2F%2Fqiita-image-store.s3.ap-northeast-1.amazonaws.com%2F0%2F218694%2F489c8ea6-130c-d44b-4bae-4d86f64556c2.png?ixlib=rb-1.2.2&auto=format&gif-q=60&q=75&s=e67fbf71779fa7ebb443e93663c56dc4\">\n",
    "\n",
    "右から回路を考えます。\n",
    "$a, a+b$ を入力して $b$ を出力します。 $a = a_n ... a_0$, $(a+b) = b_n ... b_0$ と2進数で表示できます。  \n",
    "(ここで n は数が大きい方の位を基準とします。)\n",
    "\n",
    "$c_i$ は繰り下がりを表します。  \n",
    "この回路は carry と呼ばれる繰り上がりの部分と sum の合計の部分にわかれています。\n",
    "まずはこの2つの部分を考察します。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 繰り下がり\n",
    "carry, sum は以下のようになります。\n",
    "\n",
    "<img src=\"https://qiita-user-contents.imgix.net/https%3A%2F%2Fqiita-image-store.s3.ap-northeast-1.amazonaws.com%2F0%2F218694%2F00361854-e782-0da0-3386-f59f668a1ada.png?ixlib=rb-1.2.2&auto=format&gif-q=60&q=75&s=58d1d41b0893b16bfb24bfd546328ff2\" width=\"60%\">\n",
    "\n",
    "回路の始めの部分はこれらを組み合わせて繰り下がりを求めています。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### オバーフロービット\n",
    "$a < a+b$ の場合でしか引き算はできません。   \n",
    "判別を $b_{n+1}$ で行います。これをオーバーフロービットと言います。\n",
    "\n",
    "$a < a+b$ のとき $b_{n+1}$ = 0  \n",
    "$a > a+b$ のとき $b_{n+1}$ = 1 になります。\n",
    "\n",
    "$a > a+b$ のときは $2^{n+1} - b$ が出力されます。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 実装\n",
    "引き算回路を実装します。\n",
    "\n",
    "流れは以下のようになります。  \n",
    "1. carry の逆回路と sum 回路で各位の繰り下がりを求める。  \n",
    "2. オーバーフローを判別して $b_{n+1}$ に格納する。  \n",
    "3. carry 回路で差を出力する。    \n",
    "\n",
    "以上の流れから $b$ は $b_n ... b_0$ の部分に出力されることが分かります。\n",
    "$b_{n+1}$ はオーバーフロービットです。\n",
    "\n",
    "実装するために下準備をします。  \n",
    "これは足し算回路と同じなので説明は省略します。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from blueqat import Circuit\n",
    "\n",
    "def carry(i):\n",
    "    return Circuit().ccx[i+1,i+2,i+3].cx[i+1,i+2].ccx[i,i+2,i+3]\n",
    "\n",
    "def carry_reverse(i):\n",
    "    return Circuit().ccx[i,i+2,i+3].cx[i+1,i+2].ccx[i+1,i+2,i+3]\n",
    "\n",
    "def sum_reverse(a):\n",
    "    return Circuit().cx[a,a+2].cx[a+1,a+2]\n",
    "\n",
    "def tobinary(A):\n",
    "    return bin(A)[2:]\n",
    "\n",
    "def digits(a,b): \n",
    "     # 2進数に変換\n",
    "     aa = tobinary(a)  \n",
    "     bb = tobinary(b)  \n",
    "     alen = len(aa)  \n",
    "     blen = len(bb)  \n",
    "\n",
    "     # nを決めて大きい方にビット数を合わせる\n",
    "     maxlen = max(alen,blen) \n",
    "     if alen>blen: \n",
    "         bb = bb.zfill(alen) \n",
    "     elif blen>alen: \n",
    "         aa = aa.zfill(blen) \n",
    "\n",
    "     # マッピング\n",
    "     str = '' \n",
    "     for i in range(maxlen): \n",
    "         str += '0' + aa[maxlen-i-1] + bb[maxlen-i-1] \n",
    "     str += '0' \n",
    "     return str\n",
    "\n",
    "def toX(a): \n",
    "     cir = Circuit(len(a)) \n",
    "     for i in range(len(a)): \n",
    "         if a[i] == \"1\": \n",
    "             cir += Circuit().x[i] \n",
    "     return cir\n",
    "\n",
    "def todecimal(A):\n",
    "    return int(str(A),2) \n",
    "\n",
    "def getb(result): \n",
    "     str = result[-1] \n",
    "     digi = int((len(result)-1)/3) \n",
    "     for i in range(digi): \n",
    "         str += result[-2-i*3] \n",
    "     return todecimal(str)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一般化回路\n",
    "以上で全ての準備が整ったので引き算回路を作ります。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minus(a,ab): \n",
    "     # 入れ替え\n",
    "     c = ab\n",
    "     ab = a\n",
    "     a = c\n",
    "\n",
    "     # 2進数表示のマッピング\n",
    "     qubits = len(digits(a,ab)) \n",
    "     cir1 = toX(digits(a,ab)) \n",
    "     digi = int((len(digits(a,ab))-1)/3) \n",
    "\n",
    "     # 前半のcarry回路とsum逆回路\n",
    "     cir4 = Circuit(qubits) \n",
    "     for i in range(digi-1): \n",
    "         cir4 += sum_reverse(i*3)\n",
    "         cir4 += carry(i*3) \n",
    "\n",
    "     # 最後の桁の処理\n",
    "     cir3 = sum_reverse((digi-1)*3) + Circuit(qubits).cx[-3,-2] \n",
    "\n",
    "     # carryの逆回路でbiに差を出力\n",
    "     cir2 = Circuit(qubits)     \n",
    "     for i in range(digi): \n",
    "         cir2 += carry_reverse((digi-1-i)*3)\n",
    "\n",
    "     result = (cir1 + cir4 + cir3 + cir2).m[:].run(shots=1) \n",
    "     return getb(result.most_common()[0][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "実際に計算してみます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "6"
     },
     "metadata": {},
     "execution_count": 7
    }
   ],
   "source": [
    "minus(8,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "2"
     },
     "metadata": {},
     "execution_count": 9
    }
   ],
   "source": [
    "minus(4,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "26"
     },
     "metadata": {},
     "execution_count": 10
    }
   ],
   "source": [
    "minus(50,24)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "計算できました。ちなみに $a > a + b$ のときは"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "14"
     },
     "metadata": {},
     "execution_count": 11
    }
   ],
   "source": [
    "minus(2,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "こちらもきちんと計算されています。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考文献\n",
    "https://arxiv.org/pdf/quant-ph/9511018.pdf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "008_basic_general.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "Python 3.7.6 64-bit ('dwave': conda)",
   "language": "python",
   "name": "python37664bitdwavecondaaa252b8d749942f1b803140f9f138e1e"
  },
  "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.6-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}