Skip to content

Instantly share code, notes, and snippets.

@tdgunes
Last active September 19, 2019 18:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tdgunes/100d67372b9787f48918e428d6392b2d to your computer and use it in GitHub Desktop.
Save tdgunes/100d67372b9787f48918e428d6392b2d to your computer and use it in GitHub Desktop.
Grover basis - generic algorithm
19 September 2019 - A day with an attempt to generate Graver basis vectors
- https://ie.technion.ac.il/~onn/Nachdiplom/3.pdf (Followed this lecture notes, and replicated the example)
- https://ie.technion.ac.il/~onn/Book/NDO.pdf (Also followed the book)
Display the source blob
Display the rendered blob
Raw
{
"cells": [
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import math"
]
},
{
"cell_type": "code",
"execution_count": 285,
"metadata": {},
"outputs": [],
"source": [
"A = np.array([[1, 2, 1]])\n",
"x = np.array([[1], [2], [0]])\n",
"I = np.eye(3)"
]
},
{
"cell_type": "code",
"execution_count": 286,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[1],\n",
" [2],\n",
" [1]])"
]
},
"execution_count": 286,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A.T"
]
},
{
"cell_type": "code",
"execution_count": 287,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(1, 3)"
]
},
"execution_count": 287,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A.shape"
]
},
{
"cell_type": "code",
"execution_count": 288,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[1],\n",
" [2],\n",
" [0]])"
]
},
"execution_count": 288,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"x"
]
},
{
"cell_type": "code",
"execution_count": 289,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[5]])"
]
},
"execution_count": 289,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"np.dot(A, x)"
]
},
{
"cell_type": "code",
"execution_count": 290,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(3, 3)"
]
},
"execution_count": 290,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"I\n",
"I.shape"
]
},
{
"cell_type": "code",
"execution_count": 291,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[1.],\n",
" [2.],\n",
" [0.]])"
]
},
"execution_count": 291,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"np.dot(I, x)"
]
},
{
"cell_type": "code",
"execution_count": 292,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 292,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"np.linalg.matrix_rank(I)"
]
},
{
"cell_type": "code",
"execution_count": 293,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 293,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"np.linalg.matrix_rank(A)"
]
},
{
"cell_type": "code",
"execution_count": 294,
"metadata": {},
"outputs": [],
"source": [
"def get_all_points(minimum, maximum, dimension):\n",
" x = np.arange(minimum, maximum, 1.0)\n",
" Z = np.meshgrid(*[x for _ in range(dimension)])\n",
" return np.array([z.flatten() for z in Z]).T\n",
"\n",
"def partially_ordered_2(x, y):\n",
" # this checks if two vectors are partially ordered with constraint 2\n",
" flag = True\n",
" for i in range(x.shape[0]):\n",
" if abs(x[i]) <= abs(y[i]):\n",
" flag = True\n",
" else:\n",
" flag = False\n",
" break\n",
" \n",
" return flag\n",
" \n",
"def distill_set(X):\n",
"# print(\"Distill\", X)\n",
" for x in X.copy():\n",
" for y in X.copy():\n",
" # print(x, y)\n",
" if x == y:\n",
" continue\n",
" if partially_ordered_2(np.array(x), np.array(y)):\n",
" X.remove(y)\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 295,
"metadata": {},
"outputs": [],
"source": [
"def generate_graver_basis(A):\n",
" # construct non-zero lattice of A, L(A)\n",
" L = set() \n",
" \n",
" # delta(A) upper bound\n",
" m, n = A.shape\n",
" delta_A = math.pow(math.sqrt(m)*np.max(A), m)\n",
" \n",
" # n=A.shape[0], m=1\n",
" bound = (n-np.linalg.matrix_rank(A))*delta_A\n",
" \n",
" print(delta_A)\n",
" print(bound)\n",
" # create all points in Z^n bounded by <bound\n",
" Z = np.arange(-bound, bound, 1.0) \n",
" grid = np.meshgrid(*[Z for i in range(n)])\n",
" x_points = np.array([g.flatten() for g in grid]).T\n",
" \n",
" # select x points that make A zero\n",
" for x in x_points:\n",
" if np.dot(A, x) == 0:\n",
" L.add(tuple(x))\n",
" \n",
" \n",
" # distill the vectors \n",
" L.remove(tuple(np.zeros(n)))\n",
" \n",
" # there are 2^n orthants in n-dimensional space, need to find and select partial minimal in each orthant\n",
" G = set() # graver basis set\n",
" groups = {}\n",
" for mask in (get_all_points(0, 2, n)*2 - 1):\n",
" groups[tuple(mask)] = set()\n",
" \n",
" for l in L:\n",
" for mask in groups:\n",
" flag = 0\n",
" for i in range(n):\n",
" if mask[i]*l[i] >= 0:\n",
" flag += 1\n",
" \n",
" \n",
" if flag == n:\n",
" groups[mask].add(l)\n",
" break\n",
" \n",
" # TODO: distill the basis by partial minimal \n",
" for mask, value in groups.items():\n",
" # print(mask)\n",
" if len(value) == 0:\n",
" continue\n",
" distill_set(value)\n",
"# print(\"Distilled:\", value)\n",
" for v in value:\n",
" G.add(v)\n",
" \n",
" return G\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 296,
"metadata": {
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2.0\n",
"4.0\n"
]
},
{
"data": {
"text/plain": [
"{(-3.0, 1.0, 1.0),\n",
" (-2.0, 1.0, 0.0),\n",
" (-1.0, 0.0, 1.0),\n",
" (-1.0, 1.0, -1.0),\n",
" (0.0, -1.0, 2.0),\n",
" (0.0, 1.0, -2.0),\n",
" (1.0, -1.0, 1.0),\n",
" (1.0, 0.0, -1.0),\n",
" (1.0, 1.0, -3.0),\n",
" (2.0, -1.0, 0.0)}"
]
},
"execution_count": 296,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"generate_graver_basis(A)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 297,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[-1. -1.]\n",
"[ 1. -1.]\n",
"[-1. 1.]\n",
"[1. 1.]\n"
]
}
],
"source": [
"for p in get_all_points(0, 2, 2)*2 - 1:\n",
" print(p)"
]
},
{
"cell_type": "code",
"execution_count": 298,
"metadata": {},
"outputs": [],
"source": [
"x = np.matrix([[1, 1], [2, -3]])\n",
"xmax = x.flat[abs(x).argmax()]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 299,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 299,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"x = np.array([-1.0, 0.0, 1.0])\n",
"y = np.array([-3.0, 0.0, 3.0])\n",
"\n",
"partially_ordered_2(x, y)"
]
},
{
"cell_type": "code",
"execution_count": 300,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{(0.0, -1.0, 2.0), (-2.0, 0.0, 2.0), (-1.0, 0.0, 1.0), (-1.0, -1.0, 3.0), (-3.0, 0.0, 3.0)}\n",
"(-1.0, 0.0, 1.0) (-1.0, 0.0, 1.0)\n",
"(-1.0, 0.0, 1.0) (0.0, -1.0, 2.0)\n",
"(-1.0, 0.0, 1.0) (-2.0, 0.0, 2.0)\n",
"Remove (-2.0, 0.0, 2.0)\n",
"(-1.0, 0.0, 1.0) (-1.0, -1.0, 3.0)\n",
"Remove (-1.0, -1.0, 3.0)\n",
"(-1.0, 0.0, 1.0) (-3.0, 0.0, 3.0)\n",
"Remove (-3.0, 0.0, 3.0)\n",
"(0.0, -1.0, 2.0) (-1.0, 0.0, 1.0)\n",
"(0.0, -1.0, 2.0) (0.0, -1.0, 2.0)\n",
"(-2.0, 0.0, 2.0) (-1.0, 0.0, 1.0)\n",
"(-2.0, 0.0, 2.0) (0.0, -1.0, 2.0)\n",
"(-1.0, -1.0, 3.0) (-1.0, 0.0, 1.0)\n",
"(-1.0, -1.0, 3.0) (0.0, -1.0, 2.0)\n",
"(-3.0, 0.0, 3.0) (-1.0, 0.0, 1.0)\n",
"(-3.0, 0.0, 3.0) (0.0, -1.0, 2.0)\n",
"Final: {(0.0, -1.0, 2.0), (-1.0, 0.0, 1.0)}\n",
"Final: {(0.0, -1.0, 2.0), (-1.0, 0.0, 1.0)}\n"
]
}
],
"source": [
"Xs = set()\n",
"Xs.add((0.0, -1.0, 2.0))\n",
"Xs.add((-2.0, 0.0, 2.0))\n",
"Xs.add((-1.0, 0.0, 1.0))\n",
"Xs.add((-1.0, -1.0, 3.0))\n",
"Xs.add((-3.0, 0.0, 3.0))\n",
"\n",
"print(Xs)\n",
"for x in Xs.copy():\n",
" for y in Xs.copy():\n",
" print(x, y)\n",
" if x == y:\n",
" continue\n",
" if partially_ordered_2(np.array(x), np.array(y)):\n",
" Xs.remove(y)\n",
" print(\"Remove\", y)\n",
"\n",
"print(\"Final:\", Xs)\n",
"\n",
"Xs = set()\n",
"Xs.add((0.0, -1.0, 2.0))\n",
"Xs.add((-2.0, 0.0, 2.0))\n",
"Xs.add((-1.0, 0.0, 1.0))\n",
"Xs.add((-1.0, -1.0, 3.0))\n",
"Xs.add((-3.0, 0.0, 3.0))\n",
"\n",
"distill_set(Xs)\n",
"print(\"Final:\", Xs)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.6.7"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment