hidden-linear-func.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "484d4bb1",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import cirq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e115621c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# prep and brute force\n",
    "class HiddenLinearFunctionProblem:\n",
    "    \"\"\"Instance of Hidden Linear Function problem.\n",
    "\n",
    "    The problem is defined by matrix A and vector b, which are\n",
    "    the coefficients of quadratic form, in which linear function\n",
    "    is \"hidden\".\n",
    "    \"\"\"\n",
    "    def __init__(self, A, b):\n",
    "        self.n = A.shape[0]\n",
    "        assert A.shape == (self.n, self.n)\n",
    "        assert b.shape == (self.n, )\n",
    "        for i in range(self.n):\n",
    "            for j in range(i+1):\n",
    "                assert A[i][j] == 0, 'A[i][j] can be 1 only if i<j'\n",
    "\n",
    "        self.A = A\n",
    "        self.b = b\n",
    "\n",
    "    def q(self, x):\n",
    "        \"\"\"Action of quadratic form on binary vector (modulo 4).\n",
    "\n",
    "        Corresponds to `q(x)` in problem definition.\n",
    "        \"\"\"\n",
    "        assert x.shape == (self.n, )\n",
    "        return (2 * (x @ self.A @ x) + (self.b @ x)) % 4\n",
    "\n",
    "    def bruteforce_solve(self):\n",
    "        \"\"\"Calculates, by definition, all vectors `z` which are solutions to the problem.\"\"\"\n",
    "\n",
    "        # All binary vectors of length `n`.\n",
    "        all_vectors = [np.array([(m>>i) % 2 for i in range(self.n)]) for m in range(2**self.n)]\n",
    "\n",
    "        def vector_in_L(x):\n",
    "            for y in all_vectors:\n",
    "                if self.q( (x + y)%2 ) != (self.q(x) + self.q(y))%4:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # L is subspace to which we restrict domain of quadratic form.\n",
    "        # Corresponds to `L_q` in the problem definition.\n",
    "        self.L = [x for x in all_vectors if vector_in_L(x)]\n",
    "\n",
    "        # All vectors `z` which are solutions to the problem.\n",
    "        self.all_zs = [z for z in all_vectors if self.is_z(z)]\n",
    "\n",
    "    def is_z(self, z):\n",
    "        \"\"\"Checks by definition, whether given vector `z` is solution to this problem.\"\"\"\n",
    "        assert z.shape == (self.n, )\n",
    "        assert self.L is not None\n",
    "        for x in self.L:\n",
    "            if self.q(x) != 2 * ((z @ x) % 2):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4e04828a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of subspace L: 4\n",
      "Number of solutions: 256\n"
     ]
    }
   ],
   "source": [
    "# generate random problem with given Lq\n",
    "def random_problem(n, seed=None):\n",
    "    \"\"\"Generates instance of the problem with given `n`.\n",
    "\n",
    "    Args:\n",
    "        n: dimension of the problem.\n",
    "    \"\"\"\n",
    "    if seed is not None:\n",
    "        np.random.seed(seed) \n",
    "    A = np.random.randint(0, 2, size=(n,n))\n",
    "    for i in range(n):\n",
    "        for j in range(i+1):\n",
    "            A[i][j] = 0\n",
    "    b = np.random.randint(0, 2, size=n)\n",
    "    problem = HiddenLinearFunctionProblem(A, b)\n",
    "    return problem\n",
    "\n",
    "def find_interesting_problem(n, min_L_size):\n",
    "    \"\"\"Generates \"interesting\" instance of the problem.\n",
    "\n",
    "    Returns instance of problem with given `n`, such that size of \n",
    "    subspace `L_q` is at least `min_L_size`.\n",
    "\n",
    "    Args:\n",
    "        n: dimension of the problem.\n",
    "        min_L_size: minimal cardinality of subspace L.\n",
    "    \"\"\"\n",
    "    for _ in range(1000):\n",
    "        problem = random_problem(n)\n",
    "        problem.bruteforce_solve()\n",
    "        if len(problem.L) >= min_L_size and not np.max(problem.A) == 0:\n",
    "            return problem\n",
    "    return None\n",
    "\n",
    "problem = find_interesting_problem(10, 4)\n",
    "print(\"Size of subspace L: %d\" % len(problem.L))\n",
    "print(\"Number of solutions: %d\" % len(problem.all_zs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "71b96027",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of subspace L: 16\n",
      "Number of solutions: 64\n"
     ]
    }
   ],
   "source": [
    "# n = 10, Lq = 16 instance definition\n",
    "A = np.array([[0, 1, 1, 0, 0, 1, 0, 0, 1, 1],\n",
    "              [0, 0, 0, 1, 1, 1, 1, 1, 1, 1],\n",
    "              [0, 0, 0, 0, 0, 0, 1, 1, 0, 1],\n",
    "              [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],\n",
    "              [0, 0, 0, 0, 0, 1, 0, 0, 0, 1],\n",
    "              [0, 0, 0, 0, 0, 0, 1, 1, 0, 0],\n",
    "              [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],\n",
    "              [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],\n",
    "              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])\n",
    "b = np.array([0, 0, 0, 0, 1, 1, 1, 0, 0, 1])\n",
    "problem_10_64 = HiddenLinearFunctionProblem(A, b)\n",
    "problem_10_64.bruteforce_solve()\n",
    "print(\"Size of subspace L: %d\" % len(problem_10_64.L))\n",
    "print(\"Number of solutions: %d\" % len(problem_10_64.all_zs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ffb5e1e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# solve with quantum circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e4a011ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "def edge_coloring(A):\n",
    "    \"\"\"Solves edge coloring problem.\n",
    "\n",
    "    Args:\n",
    "        A: adjacency matrix of a graph.\n",
    "\n",
    "    Returns list of lists of edges, such as edges in each list \n",
    "    do not have common vertex. \n",
    "    Tries to minimize length of this list.\n",
    "    \"\"\"\n",
    "    A = np.copy(A)\n",
    "    n = A.shape[0]\n",
    "    ans = []\n",
    "    while np.max(A) != 0:\n",
    "        edges_group = []\n",
    "        used = np.zeros(n, dtype=np.bool)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if A[i][j] == 1 and not used[i] and not used[j]:\n",
    "                    edges_group.append((i, j))\n",
    "                    A[i][j] = 0\n",
    "                    used[i] = used[j] = True\n",
    "        ans.append(edges_group)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6afee5de",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "          ┌───┐   ┌──┐   ┌───┐   ┌───┐   ┌───┐\n",
      "0: ───H────@───────@──────@───────@───────@──────────────────────H───M───\n",
      "           │       │      │       │       │\n",
      "1: ───H────@───────┼@─────┼@──────┼@──────┼@─────@───@───@───────H───M───\n",
      "                   ││     ││      ││      ││     │   │   │\n",
      "2: ───H────@───────@┼─────┼┼@─────┼┼@─────┼┼─────┼───┼───┼───────H───M───\n",
      "           │        │     │││     │││     ││     │   │   │\n",
      "3: ───H────┼@───────@─────┼┼┼─────┼┼┼─────┼┼─────┼───┼───┼───────H───M───\n",
      "           ││             │││     │││     ││     │   │   │\n",
      "4: ───H────┼┼@─────@──────┼@┼─────┼┼┼─────┼┼─────┼───┼───┼───S───H───M───\n",
      "           │││     │      │ │     │││     ││     │   │   │\n",
      "5: ───H────┼┼@─────┼@─────@─┼─────┼@┼─────┼┼@────┼───┼───┼───S───H───M───\n",
      "           ││      ││       │     │ │     │││    │   │   │\n",
      "6: ───H────@┼──────┼@─────@─┼─────┼─┼─────┼@┼────┼───┼───┼───S───H───M───\n",
      "            │      │      │ │     │ │     │ │    │   │   │\n",
      "7: ───H────@┼──────┼@─────┼─@─────┼─┼─────┼─@────@───┼───┼───────H───M───\n",
      "           ││      ││     │       │ │     │          │   │\n",
      "8: ───H────┼@──────┼@─────┼───────@─┼─────┼──────────@───┼───────H───M───\n",
      "           │       │      │         │     │              │\n",
      "9: ───H────@───────@──────@─────────@─────@──────────────@───S───H───M───\n",
      "          └───┘   └──┘   └───┘   └───┘   └───┘\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/tmp/ipykernel_2286/644644906.py:16: DeprecationWarning: `np.bool` is a deprecated alias for the builtin `bool`. To silence this warning, use `bool` by itself. Doing this will not modify any behavior and is safe. If you specifically wanted the numpy scalar type, use `np.bool_` here.\n",
      "Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations\n",
      "  used = np.zeros(n, dtype=np.bool)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([0, 1, 0, 1, 1, 1, 1, 0, 1, 1], dtype=uint8)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def generate_circuit_for_problem(problem):\n",
    "    \"\"\"Generates `cirq.Circuit` which solves instance of Hidden Linear Function problem.\"\"\"\n",
    "\n",
    "    qubits = cirq.LineQubit.range(problem.n)\n",
    "    circuit = cirq.Circuit()\n",
    "\n",
    "    # Hadamard gates at the beginning (creating equal superposition of all states).\n",
    "    circuit += cirq.Moment([cirq.H(q) for q in qubits])\n",
    "\n",
    "    # Controlled-Z gates encoding the matrix A.\n",
    "    for layer in edge_coloring(problem.A):\n",
    "        for i, j in layer:\n",
    "            circuit += cirq.CZ(qubits[i], qubits[j])\n",
    "\n",
    "    # S gates encoding the vector b.\n",
    "    circuit += cirq.Moment([cirq.S.on(qubits[i]) for i in range(problem.n) if problem.b[i] == 1])\n",
    "\n",
    "    # Hadamard gates at the end.\n",
    "    circuit += cirq.Moment([cirq.H(q) for q in qubits])\n",
    "\n",
    "    # Measurements.\n",
    "    circuit += cirq.Moment([cirq.measure(qubits[i], key=str(i)) for i in range(problem.n)]) \n",
    "\n",
    "    return circuit\n",
    "\n",
    "def solve_problem(problem, print_circuit=False):\n",
    "    \"\"\"Solves instance of Hidden Linear Function problem.\n",
    "\n",
    "    Builds quantum circuit for given problem and simulates\n",
    "    it with the Clifford simulator. \n",
    "\n",
    "    Returns measurement result as binary vector, which is\n",
    "    guaranteed to be a solution to given problem.\n",
    "    \"\"\"\n",
    "    circuit = generate_circuit_for_problem(problem)\n",
    "\n",
    "    if print_circuit:\n",
    "        print(circuit)\n",
    "\n",
    "    sim = cirq.CliffordSimulator()\n",
    "    result = sim.simulate(circuit)\n",
    "    z = np.array([result.measurements[str(i)][0] for i in range(problem.n)])\n",
    "    return z\n",
    "\n",
    "solve_problem(problem_10_64, print_circuit=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "cc896896",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/tmp/ipykernel_2286/644644906.py:16: DeprecationWarning: `np.bool` is a deprecated alias for the builtin `bool`. To silence this warning, use `bool` by itself. Doing this will not modify any behavior and is safe. If you specifically wanted the numpy scalar type, use `np.bool_` here.\n",
      "Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations\n",
      "  used = np.zeros(n, dtype=np.bool)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK\n"
     ]
    }
   ],
   "source": [
    "# testing\n",
    "def test_problem(problem):\n",
    "    problem.bruteforce_solve()\n",
    "    tries = 100\n",
    "    for _ in range(tries):\n",
    "        z = solve_problem(problem)\n",
    "        assert problem.is_z(z)\n",
    "\n",
    "test_problem(problem_10_64)\n",
    "print('OK')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "81c26e1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# repeat for n = 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "2c349aa3",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/tmp/ipykernel_2286/644644906.py:16: DeprecationWarning: `np.bool` is a deprecated alias for the builtin `bool`. To silence this warning, use `bool` by itself. Doing this will not modify any behavior and is safe. If you specifically wanted the numpy scalar type, use `np.bool_` here.\n",
      "Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations\n",
      "  used = np.zeros(n, dtype=np.bool)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK\n"
     ]
    }
   ],
   "source": [
    "for _ in range(10):\n",
    "    test_problem(find_interesting_problem(8, 4))\n",
    "print('OK')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "3a4cbf2d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 µs, sys: 1e+03 ns, total: 5 µs\n",
      "Wall time: 8.82 µs\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/tmp/ipykernel_2286/644644906.py:16: DeprecationWarning: `np.bool` is a deprecated alias for the builtin `bool`. To silence this warning, use `bool` by itself. Doing this will not modify any behavior and is safe. If you specifically wanted the numpy scalar type, use `np.bool_` here.\n",
      "Deprecated in NumPy 1.20; for more details and guidance: https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations\n",
      "  used = np.zeros(n, dtype=np.bool)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1,\n",
       "       0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1,\n",
       "       1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0,\n",
       "       0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,\n",
       "       0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1,\n",
       "       0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,\n",
       "       0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1,\n",
       "       1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,\n",
       "       1, 0], dtype=uint8)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# run with n = 200\n",
    "%time\n",
    "tries = 200\n",
    "problem = random_problem(tries, seed=0)\n",
    "solve_problem(problem, print_circuit=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75948a49",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}