PUBO_EN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Polynomial Unconstrained Boolean Optimization Problem in MBQC\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the tutorial [Measurement-based Quantum Approximate Optimization Algorithm](QAOA_EN.ipynb), we give a brief introduction to the **polynomial unconstrained boolean optimization (PUBO) problem** and propose the **measurement-based quantum approximate optimization algorithm (MB-QAOA)** to solve it. For interested readers, please refer to the previous tutorial for more information. In this tutorial, we will showcase two specific examples as practical demonstrations of MB-QAOA. The first one is a concrete PUBO problem, while the second one is a **maximum cut (MaxCut)** problem.\n",
    "\n",
    "## Example: PUBO Problem\n",
    "\n",
    "Let us first briefly review what a PUBO problem is. Consider a polynomial of $n$ variables $x = \\{x_1,\\cdots,x_n\\}$, \n",
    "\n",
    "$$\n",
    "C(x) = \\sum_{\\lambda \\in \\Lambda } \\alpha_{\\lambda} \\prod_{j \\in \\lambda} x_j,\\tag{1}\n",
    "$$\n",
    "\n",
    "where $x_i \\in \\{0,1\\}$ is a boolean variable, $\\underset{j \\in \\lambda}{\\prod} x_j$ is a monomial, $\\lambda \\subseteq [n]:= \\{1, 2, ..., n\\}$ is a set of indexes, $\\Lambda$ is the set of index sets, $\\alpha_\\lambda$ is the real coefficient of monomial. In PUBO, $C(x)$ is called the objective polynomial. We hope to find an optimal solution $x^* = \\{x_1^*, x_2^*, ..., x_n^*\\} $ maximizing the value of objective polynomial. That is to find\n",
    "\n",
    "$$\n",
    "x^* = \\underset{x}{\\text{argmax}} \\ C(x).\\tag{2}\n",
    "$$\n",
    "\n",
    "For code implementation, we require that a standard polynomial is input as a list whose first item is the number of variables and the second item is a dictionary of all the monomials ('cons' stands for the constant item). In the dictionary, we make monomial variables split with ',' as keys and the corresponding coefficients as values. For example, suppose we want to input a polynomial $x_1 + x_2 - x_3 + x_1 x_2 - x_1 x_2 x_3 + 0.5$, we need to code as follows:   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of variables\n",
    "var_num = 3\n",
    "# Polynomial as a dictionary\n",
    "poly_dict = {'x_1': 1, 'x_2': 1, 'x_3': -1, 'x_1,x_2': 1, 'x_1,x_2,x_3': -1, 'cons':0.5}\n",
    "# Construct the list required\n",
    "polynomial = [var_num, poly_dict]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** As the variables are boolean, the power of variables in a monomial should be no greater than 1. That is, each variable should appear at most once in a key of the dictionary. For instance, it is not a valid to input something like {'x_1,x_1,x_2': 1}. Also, we set variable subscripts by consecutive numbers starting from '1' to be consistent with math conventions. A polynomial like $x_1 x_2 + x_6$ will raise an error automatically. A valid polynomial should be like $x_1x_2 + x_3$.   \n",
    "\n",
    "For convenience, we provide a function `is_poly_valid` in `pubo` to check the validity of the user's input. If the polynomial is valid, it will print a statement \"The polynomial is valid.\". Otherwise, an error will be raised.\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.pubo import is_poly_valid\n",
    "```\n",
    "We also provide a function `random_poly` to generate a random boolean polynomial with a given number of variables.\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.pubo import random_poly\n",
    "```\n",
    "**Note:** The randomly generated polynomial is not always valid and we still need to check the validity before calculation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Code implementation to slove PUBO problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import time module\n",
    "from time import perf_counter\n",
    "# Import sympy module for syntax calculation\n",
    "from sympy import symbols\n",
    "# Import paddle module\n",
    "from paddle import seed, optimizer\n",
    "# Import pubo module\n",
    "from paddle_quantum.mbqc.QAOA.pubo import dict_to_symbol,is_poly_valid,brute_force_search\n",
    "# Import qaoa module\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import MBQC_QAOA_Net, get_solution_string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We define a function ``mbqc_pubo`` which takes in the objective polynomial and returns an optimal solution. **The core part of ``mbqc_pubo`` is the ``MBQC_QAOA_Net`` class**, which integrates MB-QAOA and the optimization net. Please refer to [Measurement-Based Quantum Approximate Optimization Algorithm](QAOA_EN.ipynb) for more details. Here we directly call the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the PUBO main function\n",
    "def mbqc_pubo(OBJ_POLY, DEPTH, SEED, LR, ITR, EPOCH, SHOTS=1024):\n",
    "    \n",
    "    # Symbolize the polynomial\n",
    "    obj_poly = dict_to_symbol(OBJ_POLY)\n",
    "    var_num, poly_symbol = obj_poly\n",
    "\n",
    "    # Print the QAOA depth\n",
    "    print(\"QAOA depth is:\", DEPTH)\n",
    "\n",
    "    #  Start timing\n",
    "    start_time = perf_counter()\n",
    "\n",
    "    # Instaniate a MB-QAOA traning net\n",
    "    seed(SEED)\n",
    "    mbqc_net = MBQC_QAOA_Net(DEPTH)\n",
    "    \n",
    "    # Choose Adams optimizer (or SGD optimizer)\n",
    "    opt = optimizer.Adam(learning_rate=LR, parameters=mbqc_net.parameters())\n",
    "\n",
    "    # Start training\n",
    "    for epoch in range(EPOCH):\n",
    "        # Update parameters for each iter\n",
    "        for itr in range(1, ITR + 1):\n",
    "            # Train with mbqc_net and return the loss\n",
    "            loss, state_out = mbqc_net(poly=obj_poly)\n",
    "            # Propagate loss backwards and optimize the parameters\n",
    "            loss.backward()\n",
    "            opt.minimize(loss)\n",
    "            opt.clear_grad()\n",
    "            if itr % 10 == 0:\n",
    "                print(\"iter:\", itr, \"  loss_MBQC:\", \"%.4f\" % loss.numpy())\n",
    "                \n",
    "    # Stop timing and print the running time\n",
    "    end_time = perf_counter()\n",
    "    print(\"MBQC running time is: \", end_time - start_time)\n",
    "\n",
    "    # Print the optimization parameters\n",
    "    print(\"Optimal parameter gamma: \", mbqc_net.gamma.numpy())\n",
    "    print(\"Optimal parameter beta: \", mbqc_net.beta.numpy())\n",
    "\n",
    "    # Decode the solution from the quantum state\n",
    "    solution_str = get_solution_string(state_out, SHOTS)\n",
    "\n",
    "    # Evaluate the corresponding value\n",
    "    relation = {symbols('x_' + str(j + 1)): int(solution_str[j]) for j in range(var_num)}\n",
    "    value = poly_symbol.evalf(subs=relation)\n",
    "    \n",
    "    # Return the solution and its corresponding value\n",
    "    opt = [solution_str, value]\n",
    "\n",
    "    return opt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To check the correctness of the training result, we provide a `brute_force_search` function in `pubo` that finds a global optimal value by brute force search. We can compare the training result with the optimal one.\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.pubo import brute_force_search\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Main function\n",
    "\n",
    "After defining the main function, let's input the parameters to run the code!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Define the main function\n",
    "def main():\n",
    "    \n",
    "    # Choose the example x_1 + x_2 - x_3 + x_1*x_2 -x_1*x_2*x_3 + 0.5\n",
    "    var_num = 3  \n",
    "    poly_dict = {'x_1': 1, 'x_2': 1, 'x_3': -1, 'x_1,x_2': 1, 'x_1,x_2,x_3': -1, 'cons':0.5}\n",
    "    polynomial = [var_num, poly_dict]\n",
    "    \n",
    "    # Print the input polynomial\n",
    "    print(\"The input polynomial is: \", polynomial)\n",
    "    \n",
    "    # We can also randomly generate an objective function\n",
    "    # polynomial = random_poly(var_num)\n",
    "\n",
    "    # Check the validity of the input polynomial\n",
    "    is_poly_valid(polynomial)\n",
    "\n",
    "    # Starting training and obtain the result\n",
    "    mbqc_result = mbqc_pubo(\n",
    "        OBJ_POLY=polynomial,  # Objective Function\n",
    "        DEPTH=6,  # QAOA Depth\n",
    "        SEED=1024,  # Plant Seed\n",
    "        LR=0.1,  # Learning Rate\n",
    "        ITR=120,  # Training Iters\n",
    "        EPOCH=1  # Epoch Times\n",
    "    )\n",
    "\n",
    "    # Print the result from MBQC model\n",
    "    print(\"Optimal solution by MBQC: \", mbqc_result[0])\n",
    "    print(\"Optimal value by MBQC: \", mbqc_result[1])\n",
    "    \n",
    "    # Compute the optimal result by brute-force search and print the result\n",
    "    brute_result = brute_force_search(polynomial)\n",
    "    print(\"Optimal solution by brute force search: \", brute_result[0])\n",
    "    print(\"Optimal value by brute force search: \", brute_result[1])\n",
    "    \n",
    "    # Compare the training result with the optimal one\n",
    "    print(\"Difference between optimal values from MBQC and brute force search: \", mbqc_result[1] - brute_result[1])\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Example: MaxCut\n",
    "\n",
    "### Graph and cut\n",
    "\n",
    "Maximum cut problem（MaxCut Problem）is a combinatorial optimization problem in graph theory, with plenty of applications in e.g. statistic physics and circuit design.\n",
    "\n",
    "In graph theory, a graph is represented by $G = (V, E)$, where $V$ is a set of vertices and $E$ is a set of edges. For example, a square can be characterized by the graph $G = (V,E)$ with $V = [1,2,3,4]$ and $E = [(1,2),(2,3),(3,4),(1,4)]$.\n",
    "\n",
    "For code implementation, we can use the `plot_graph` function in `maxcut` to plot a graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from paddle_quantum.mbqc.QAOA.maxcut import plot_graph\n",
    "V = [1,2,3,4]\n",
    "E = [(1,2),(2,3),(3,4),(1,4)]\n",
    "G = [V, E] \n",
    "plot_graph(G,\"A square\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A cut in the graph is a partition separating the vertices set $V$ into two complementary subsets $S_0$ and $S_1$. If two vertices of an edge in the graph are separated into different subsets, we score a goal. The size of a cut is defined by the total scores that we get. Then the MaxCut problem is to find a cut of graph with maximal size.  \n",
    "\n",
    "As for the above square $G$, one of the optimal solutions to the MaxCut problem is to put $1$ and $3$ into subset $S_0$ and put $2$ and $4$ into subset $S_1$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Transformation to a PUBO problem\n",
    "\n",
    "A MaxCut problem can be transformed into a PUBO problem. Assume the graph to be cut $G = (V, E)$ has $n=|V|$ vertices and $m =|E|$ edges, we can transform the MaxCut problem into a PUBO problem of $n$ variables. Each variable $x_v$ corresponds to a vertex $v \\in V$ in the graph $G$, with its domain $x_v \\in \\{0,1\\}$ corresponding to its belonging to subset $S_0$ or subset $S_1$. So, each value of the string $x = \\{x_1,\\cdots,x_n\\}$ corresponds to a cut. As a valid edge to score a goal is the one whose vertices $u$ and $v$ belong to different subsets, given a cut $x$, its size can be defined as:  \n",
    "\n",
    "$$\n",
    "C(x) = \\sum_{(u,v) \\in E} (x_u \\oplus x_v),\\tag{3}\n",
    "$$\n",
    "\n",
    "where $\\oplus$ represents XOR operation. Then the MaxCut problem is equivalent to solve the optimization $\\underset{x}{\\max} \\ C(x)$. Since $C(x)$ can be written as a polynomial: \n",
    "\n",
    "$$\n",
    "C(x) = \\sum_{(u, v) \\in E} (x_u + x_v - 2 x_u x_v).\\tag{4}\n",
    "$$\n",
    "\n",
    "this optimization is essentially a quadratic PUBO problem of $n$ variables. We hope to find an optimal solution $x^{*}$ maximizing the value of objective polynomial, that is,\n",
    "\n",
    "$$\n",
    "x^* = \\underset{x}{\\text{argmax}} \\left( \\sum_{(u, v) \\in E} (x_u + x_v - 2 x_u x_v) \\right).\\tag{5}\n",
    "$$\n",
    "\n",
    "We provide a function `graph_to_poly` in `maxcut` which takes in the graph to be cut and returns the equivalent objective polynomial in PUBO."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import maxcut module\n",
    "from paddle_quantum.mbqc.QAOA.maxcut import graph_to_poly\n",
    "\n",
    "# Input the vertices and edges\n",
    "V = [1,2,3,4]\n",
    "E = [(1,2),(2,3),(3,4),(1,4)]\n",
    "# Construct the graph to be cut\n",
    "G = [V, E] \n",
    "\n",
    "# Transform the graph to the equivalent polynomial\n",
    "poly = graph_to_poly(G)\n",
    "print(\"The equivalent objective polynomial is：\\n\", poly)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Code implementation to solve MaxCut problem\n",
    "\n",
    "Once obtaining the objective polynomial, we can follow the same process as the previous example and solve the MaxCut problem as a special case of PUBO. The complete code implementation is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import symbol calculaion module\n",
    "from sympy import symbols\n",
    "# Import paddle module\n",
    "from paddle import seed, optimizer\n",
    "# Import qaoa module\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import MBQC_QAOA_Net, get_solution_string\n",
    "# Import maxcut module\n",
    "from paddle_quantum.mbqc.QAOA.maxcut import plot_graph, graph_to_poly, plot_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We define the main function for MaxCut that takes in the graph to be cut and returns the optimal training results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the MaxCut main function\n",
    "def mbqc_maxcut(GRAPH, DEPTH, SEED, LR, ITR, EPOCH, SHOTS=1024):\n",
    "    \n",
    "    # Plot the graph to be cut\n",
    "    plot_graph(graph=GRAPH, title=\"Graph to be cut\")\n",
    "\n",
    "    # Obtain the objective polynomial\n",
    "    polynomial = graph_to_poly(GRAPH)\n",
    "    print(\"Corresponding objective polynomial of the graph is:\", polynomial[1])\n",
    "\n",
    "    # Start timing\n",
    "    start_time = perf_counter()\n",
    "    \n",
    "    # Instantiate a MB-QAOA training net\n",
    "    seed(SEED)\n",
    "    mbqc_net = MBQC_QAOA_Net(DEPTH)\n",
    "    \n",
    "    # Choose Adams optimizer (or SGD optimizer)\n",
    "    opt = optimizer.Adam(learning_rate=LR, parameters=mbqc_net.parameters())\n",
    "\n",
    "    # Start training\n",
    "    for epoch in range(EPOCH):\n",
    "        # Update parameters for each iter\n",
    "        for itr in range(1, ITR + 1):\n",
    "            # Train with mbqc_net and return the loss\n",
    "            loss, state_out = mbqc_net(poly=polynomial)\n",
    "            # Propagate loss backwards and optimize the parameters\n",
    "            loss.backward()\n",
    "            opt.minimize(loss)\n",
    "            opt.clear_grad()\n",
    "            if itr % 10 == 0:\n",
    "                print(\"iter:\", itr, \"  loss_MBQC:\", \"%.4f\" % loss.numpy())\n",
    "\n",
    "    # Stop timing and print the running time\n",
    "    end_time = perf_counter()\n",
    "    print(\"MBQC running time: \", end_time - start_time)\n",
    "    \n",
    "    # Print the optimized parameters\n",
    "    print(\"Optimal parameter gamma: \", mbqc_net.gamma.numpy())\n",
    "    print(\"Optimal parameter beta: \", mbqc_net.beta.numpy())\n",
    "\n",
    "    # Decode the MaxCut solution from the final state\n",
    "    mbqc_solution = get_solution_string(state_out, SHOTS)\n",
    "    # Plot the MaxCut solution\n",
    "    plot_solution(GRAPH, mbqc_solution)\n",
    "\n",
    "    # Evaluate the number of cuts\n",
    "    var_num, poly_symbol = polynomial\n",
    "    relation = {symbols('x_' + str(j + 1)): int(mbqc_solution[j]) for j in range(var_num)}\n",
    "    \n",
    "    mbqc_value = int(poly_symbol.evalf(subs=relation))\n",
    "    mbqc_opt = [mbqc_solution, mbqc_value]\n",
    "\n",
    "    return mbqc_opt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Main function\n",
    "\n",
    "After defining the main function, let's input the parameters to run the code!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def main():\n",
    "    #  A graph to be cut\n",
    "    V = [1, 2, 3, 4]\n",
    "    E = [(1, 2), (2, 3), (3, 4), (4, 1)]\n",
    "    G = [V, E]\n",
    "    \n",
    "    # MaxCut under MBQC\n",
    "    mbqc_result = mbqc_maxcut(\n",
    "        GRAPH=G,  # Graph to be cut\n",
    "        DEPTH=6,  # Depth\n",
    "        SEED=1024,  # Plant Seed\n",
    "        LR=0.1,  # Learning Rate\n",
    "        ITR=120,  # Training Iters\n",
    "        EPOCH=1,  # Epoch Times\n",
    "        SHOTS=1024  # Shots for decoding the solution\n",
    "    )\n",
    "\n",
    "    # Print the result from MBQC model\n",
    "    print(\"Optimal solution by MBQC: \", mbqc_result[0])\n",
    "    print(\"Optimal value by MBQC: \", mbqc_result[1])\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we have completed the demonstration of two examples. The implementation of MB-QAOA indicates a great potential of MBQC in the field of quantum machine learning. Apparently, MBQC model can realize quantities of algorithms far beyond QAOA. We therefore are \n",
    "looking forward to exploring more on this and to show some unparalleled advantages in practice.\n",
    "\n",
    "As a matter of fact, we have found an interesting application of MBQC in simulating a special class of quantum circuits! So, let's continue our exploration to the next tutorial together:\n",
    "\n",
    "[Speeding up Quantum Circuit Simulation by MBQC](Pattern_EN.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "---\n",
    "\n",
    "## References\n",
    "\n",
    "[1] Farhi, Edward, et al. \"A quantum approximate optimization algorithm.\" [arXiv preprint arXiv:1411.4028 (2014).](https://arxiv.org/abs/1411.4028)"
   ]
  }
 ],
 "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.7.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}