simulate_cirquit.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:40.942026Z",
     "start_time": "2017-12-18T15:21:40.661350Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import scipy.sparse as sp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 量子ビット(Qubit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:40.974113Z",
     "start_time": "2017-12-18T15:21:40.947036Z"
    }
   },
   "outputs": [],
   "source": [
    "class Qubits(object):\n",
    "    def __init__(self, n_bits):\n",
    "        self.n_bits = n_bits\n",
    "        self.n_states = 2**n_bits\n",
    "        self._amp = np.zeros(self.n_states, dtype=np.complex)\n",
    "        self._amp[0] = 1\n",
    "        \n",
    "    def set_bits(self, bits):\n",
    "        idx = sum(bit<<i for i, bit in enumerate(bits[::-1]))\n",
    "        self._amp = np.zeros(self.n_states, dtype=np.complex)\n",
    "        self._amp[idx] = 1.0\n",
    "        return self\n",
    "        \n",
    "    def measure(self):\n",
    "        p = np.abs(self._amp)**2\n",
    "        idx = np.random.choice(range(len(self._amp)), p=p)\n",
    "        bits = [idx>>i & 1 for i in range(self.n_bits)]\n",
    "        return bits[::-1]\n",
    "    \n",
    "    def apply(self, *operators):\n",
    "        amp = self._amp\n",
    "        for op in operators:\n",
    "            amp = op(amp)\n",
    "        applied = self.__class__(self.n_bits)\n",
    "        applied._amp = amp\n",
    "        return applied\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \" + \".join(\n",
    "            (\"{}|{:0\" + str(self.n_bits) + \"b}>\").format(amp, i)\n",
    "            for i, amp in enumerate(self._amp) if amp\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:40.996382Z",
     "start_time": "2017-12-18T15:21:40.979860Z"
    }
   },
   "outputs": [],
   "source": [
    "# Tests\n",
    "qubits = Qubits(5)\n",
    "qubits.set_bits([0, 0, 0, 1, 0])\n",
    "assert(len(qubits._amp) == 2**5)\n",
    "assert(qubits._amp[int('00010', 2)] == 1)\n",
    "assert(qubits._amp.sum() == 1)\n",
    "\n",
    "# Test Mearure\n",
    "assert(qubits.measure() == [0, 0, 0, 1, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 演算子を作用させる\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.015508Z",
     "start_time": "2017-12-18T15:21:41.003301Z"
    }
   },
   "outputs": [],
   "source": [
    "import abc\n",
    "\n",
    "class Operator(object):\n",
    "    __metaclass__ = abc.ABCMeta\n",
    "    \n",
    "    def __init__(self, n_bits):\n",
    "        self.n_bits = n_bits\n",
    "    \n",
    "    @abc.abstractproperty\n",
    "    def matrix(self):\n",
    "        pass\n",
    "\n",
    "    def __call__(self, amp):\n",
    "        return self._matrix.dot(amp)\n",
    "        \n",
    "    def __str__(self):\n",
    "        return str(self._matrix.todense())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.033817Z",
     "start_time": "2017-12-18T15:21:41.024210Z"
    }
   },
   "outputs": [],
   "source": [
    "class Id(Operator):\n",
    "    def __init__(self, n_bits):\n",
    "        super(Id, self).__init__(n_bits)\n",
    "        self._matrix = sp.eye(2**n_bits)\n",
    "    \n",
    "    @property\n",
    "    def matrix(self):\n",
    "        return self._matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.060282Z",
     "start_time": "2017-12-18T15:21:41.039963Z"
    }
   },
   "outputs": [],
   "source": [
    "class X(Operator):\n",
    "    def __init__(self, n_bits, target):\n",
    "        super(X, self).__init__(n_bits)\n",
    "        self.target = target\n",
    "        \n",
    "        self._matrix = sp.dok_matrix((2**n_bits, 2**n_bits))\n",
    "        for upper in range(2**target):\n",
    "            for lower in range(2**(n_bits - 1 - target)):\n",
    "                idx0 = upper*2**(n_bits - target) + lower\n",
    "                idx1 = idx0 + 2**(n_bits - 1 - target)\n",
    "                self._matrix[idx0, idx1] = 1\n",
    "                self._matrix[idx1, idx0] = 1\n",
    "    \n",
    "    @property\n",
    "    def matrix(self):\n",
    "        return self._matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.079456Z",
     "start_time": "2017-12-18T15:21:41.066665Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  1.]\n",
      " [ 1.  0.]]\n"
     ]
    }
   ],
   "source": [
    "# Test X\n",
    "\n",
    "x = X(1, 0)\n",
    "assert (x.matrix == np.array([[0, 1], [1, 0]])).all()\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.099157Z",
     "start_time": "2017-12-18T15:21:41.089438Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1+0j)|0>\n",
      "(1+0j)|1>\n"
     ]
    }
   ],
   "source": [
    "qubits = Qubits(1)\n",
    "print(qubits)\n",
    "qubits = qubits.apply(X(1, 0))\n",
    "print(qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 重ね合わせの状態を作る"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.127113Z",
     "start_time": "2017-12-18T15:21:41.105840Z"
    }
   },
   "outputs": [],
   "source": [
    "class H(Operator):\n",
    "    def __init__(self, n_bits, target):\n",
    "        super(H, self).__init__(n_bits)\n",
    "        self.target = target\n",
    "        \n",
    "        self._matrix = sp.dok_matrix((2**n_bits, 2**n_bits))\n",
    "        for upper in range(2**target):\n",
    "            for lower in range(2**(n_bits - 1 - target)):\n",
    "                idx0 = upper*2**(n_bits - target) + lower\n",
    "                idx1 = idx0 + 2**(n_bits - 1 - target)\n",
    "                self._matrix[idx0, idx0] = 1/np.sqrt(2)\n",
    "                self._matrix[idx0, idx1] = 1/np.sqrt(2)\n",
    "                self._matrix[idx1, idx0] = 1/np.sqrt(2)\n",
    "                self._matrix[idx1, idx1] = -1/np.sqrt(2)\n",
    "    \n",
    "    @property\n",
    "    def matrix(self):\n",
    "        return self._matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.149755Z",
     "start_time": "2017-12-18T15:21:41.134103Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.70710678  0.70710678]\n",
      " [ 0.70710678 -0.70710678]]\n"
     ]
    }
   ],
   "source": [
    "# Test H\n",
    "\n",
    "h = H(1, 0)\n",
    "assert (h.matrix == np.array([[1, 1], [1, -1]])/np.sqrt(2)).all()\n",
    "print(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.169060Z",
     "start_time": "2017-12-18T15:21:41.159003Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: (1+0j)|0>\n",
      "after: (0.707106781187+0j)|0> + (0.707106781187+0j)|1>\n"
     ]
    }
   ],
   "source": [
    "qubits = Qubits(1)\n",
    "print('before: {}'.format(qubits))\n",
    "print('after: {}'.format(qubits.apply(H(1, 0))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 量子もつれを発生させる"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.204884Z",
     "start_time": "2017-12-18T15:21:41.176040Z"
    }
   },
   "outputs": [],
   "source": [
    "class CNot(Operator):\n",
    "    def __init__(self, n_bits, control, target):\n",
    "        super(CNot, self).__init__(n_bits)\n",
    "        self.control = control\n",
    "        self.target = target\n",
    "        \n",
    "        self._matrix = sp.dok_matrix((2**n_bits, 2**n_bits))\n",
    "        for upper in range(2**target):\n",
    "            for lower in range(2**(n_bits - 1 - target)):\n",
    "                idx0 = upper*2**(n_bits - target) + lower\n",
    "                idx1 = idx0 + 2**(n_bits - 1 - target)\n",
    "                if self._get_control_bit(idx0):\n",
    "                    self._matrix[idx0, idx1] = 1\n",
    "                    self._matrix[idx1, idx0] = 1\n",
    "                else:\n",
    "                    self._matrix[idx0, idx0] = 1\n",
    "                    self._matrix[idx1, idx1] = 1\n",
    "    \n",
    "    @property\n",
    "    def matrix(self):\n",
    "        return self._matrix\n",
    "    \n",
    "    def _get_control_bit(self, bits):\n",
    "        return 1 & (bits >> (self.n_bits - 1 - self.control))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.220353Z",
     "start_time": "2017-12-18T15:21:41.210496Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 1.  0.  0.  0.]\n",
      " [ 0.  1.  0.  0.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  0.  1.  0.]]\n"
     ]
    }
   ],
   "source": [
    "# Test CNot\n",
    "\n",
    "cnot = CNot(2, 0, 1)\n",
    "assert(cnot.matrix == np.array([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]])).all()\n",
    "print(cnot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.236733Z",
     "start_time": "2017-12-18T15:21:41.223840Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0.707106781187+0j)|000> + (0.707106781187+0j)|110>\n"
     ]
    }
   ],
   "source": [
    "qubits = Qubits(3)\n",
    "qubits = qubits.apply(H(3, 0), CNot(3, 0, 1))\n",
    "print(qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# アルゴリズムを書いてみる\n",
    "## ベルンシュタイン・ヴァジラニの問題を解く\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.261146Z",
     "start_time": "2017-12-18T15:21:41.244158Z"
    }
   },
   "outputs": [],
   "source": [
    "# その前に、 compose を用意しておく\n",
    "\n",
    "class ComposedOperator(Operator):\n",
    "    def __init__(self, *operators):\n",
    "        n_bits = operators[0].n_bits\n",
    "        super(ComposedOperator, self).__init__(n_bits)\n",
    "        \n",
    "        self.operators = operators\n",
    "        self._matrix = self.operators[0]._matrix\n",
    "        for operator in self.operators[1:]:\n",
    "            self._matrix = operator._matrix.dot(self._matrix)\n",
    "    \n",
    "    @property\n",
    "    def matrix(self):\n",
    "        return self._matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.290194Z",
     "start_time": "2017-12-18T15:21:41.268003Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0] -> [0, 0, 0]\n",
      "[0, 1, 0] -> [0, 1, 1]\n",
      "[1, 0, 0] -> [1, 0, 1]\n",
      "[1, 1, 0] -> [1, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "# a0 = a1 = 1\n",
    "oracle = ComposedOperator(CNot(3, 0, 2), CNot(3, 1, 2))\n",
    "qubits = Qubits(3)\n",
    "\n",
    "for bits in ([0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0]):\n",
    "    qubits.set_bits(bits)\n",
    "    print('{} -> {}'.format(bits, qubits.apply(oracle).measure()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.308870Z",
     "start_time": "2017-12-18T15:21:41.295835Z"
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0] -> [0, 0, 0]\n",
      "[0, 1, 0] -> [0, 1, 0]\n",
      "[1, 0, 0] -> [1, 0, 1]\n",
      "[1, 1, 0] -> [1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "# a0 = 1 a1 = 0\n",
    "oracle = ComposedOperator(CNot(3, 0, 2))\n",
    "qubits = Qubits(3)\n",
    "\n",
    "\n",
    "for bits in ([0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0]):\n",
    "    qubits.set_bits(bits)\n",
    "    print('{} -> {}'.format(bits, qubits.apply(oracle).measure()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.326196Z",
     "start_time": "2017-12-18T15:21:41.315478Z"
    }
   },
   "outputs": [],
   "source": [
    "def solve_bv(oracle):\n",
    "    n = oracle.n_bits\n",
    "    preprocess = ComposedOperator(X(n, n - 1), *(H(n, i) for i in range(n)))\n",
    "    postprocess = ComposedOperator(*(H(n, i) for i in range(n)))\n",
    "    qubits = Qubits(n)\n",
    "    return qubits.apply(preprocess, oracle, postprocess).measure()[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.366311Z",
     "start_time": "2017-12-18T15:21:41.331084Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "oracle = CNot(3, 0, 2)\n",
    "solve_bv(oracle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-18T15:21:41.400021Z",
     "start_time": "2017-12-18T15:21:41.372199Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "oracle = ComposedOperator(CNot(3, 0, 2), CNot(3, 1, 2))\n",
    "solve_bv(oracle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}