Skip to content

Instantly share code, notes, and snippets.

@ohtaman

ohtaman/simulate_cirquit.ipynb

Created December 18, 2017 15:22
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ohtaman/cca53fd4b82970c7d8e1991371bb3d20 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ohtaman/cca53fd4b82970c7d8e1991371bb3d20 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment