{ "cells": [ { "cell_type": "markdown", "id": "99b74687", "metadata": {}, "source": [ "# QUBO as a QAOAProblem\n", "\n", "In this tutorial you'll be guided through the process of defining a new phase separator to be used within the scope of the [Alternating Operator Ansatz](../../../reference/Algorithms/qaoa/QAOA.rst) focussed on solving various QUBO problems with only needing the QUBO matrix $Q$ as an input.\n", "QUBO, or [Quadratic Unconstrained Binary Optimization](https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization), is a type of problem that involves optimizing a quadratic function of binary variables.\n", "\n", "After first translating the QUBO Hamiltonian $H_C$ from the binary basis $x_i$​ to the state basis with the translation $x_i\\rightarrow \\frac{\\mathbb{I}-Z_i}{2}$, we'll construct the phase separator unitary and run QAOA to solve the set partitioning problem.\n", "\n", "Not to get too ahead of ourselves with how to do it, let's first show how to solve a QUBO problem using Qrisp. To obtain the optimal solutions to a problem, we only need to know the QUBO matrix $Q$. In order to get familiar with that, we propose having a look at the [Tutorial on Formulating and Using QUBO Models](https://arxiv.org/abs/1811.11538), which explains how to derive such a matrix $Q$. \n", "\n", "One can then simply minimize the cost function $\\min C(x)=\\min x^TQx$ for binary variables $x_i\\in\\{0,1\\}$. This is done either by sending the QUBO matrix $Q$ to the annealer/quantum computer, which calculates and returns the bitstrings with corresponding values of $C(x)$. The lower the $C(x)$, the better the solution. In other words, we want to find the Hamiltonian $H_C|x\\rangle=C(x)|x\\rangle$.\n", "\n", "Let's borrow the QUBO matrix (explained in depth in the above mentioned [tutorial](https://arxiv.org/abs/1811.11538)) for the set partitioning problem. The QUBO matrix in that case is \n", "\n", "$$Q = \\begin{pmatrix}-17&10&10&10&0&20\\\\10&-18&10&10&10&20\\\\10&10&-29&10&20&20\\\\10&10&10&-19&10&10\\\\0&10&20&10&-17&10\\\\20&20&20&10&10&-28\\end{pmatrix}$$\n", "\n", "Usually, QUBO matrices are upper triangular (by convention) - this means that only elements above the diagonal (with the diagonal included) are not equal to zero. This is because the variables in QUBO problems are binary, which results in the identity $q_iq_j=q_jq_i$ for binary variables. Because of this, the elements above the diagonal are doubled compared to the symmetrized version of $Q$ we wrote down above.\n", "\n", "Of course it's easy to go from the conventional QUBO $Q_{\\text{up}\\Delta}$ formulation to the symmetrized $Q_\\text{sym}$ QUBO: $Q_\\text{sym}=\\frac{1}{2}\\big(Q_{\\text{up}\\Delta}+Q_{\\text{up}\\Delta}^T\\big)$, and back:" ] }, { "cell_type": "code", "execution_count": 1, "id": "51a388fe", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "\n", "\n", "def upper_triangular_to_symmetric(Q_up_triang):\n", " # Convert upper triangular QUBO matrix to symmetrized version\n", " return 0.5 * (Q_up_triang + Q_up_triang.T)\n", "\n", "\n", "def symmetric_to_upper_triangular(Q_sym):\n", " # Convert symmetrized QUBO matrix to upper triangular version\n", " return 2 * np.triu(Q_sym) - np.diag(np.diag(Q_sym))\n", "\n", "\n", "# Example from the notebook\n", "Q_sym = np.array(\n", " [\n", " [-17, 10, 10, 10, 0, 20],\n", " [10, -18, 10, 10, 10, 20],\n", " [10, 10, -29, 10, 20, 20],\n", " [10, 10, 10, -19, 10, 10],\n", " [0, 10, 20, 10, -17, 10],\n", " [20, 20, 20, 10, 10, -28],\n", " ]\n", ")\n", "\n", "# Convert symmetric to upper triangular\n", "Q_up_triang = symmetric_to_upper_triangular(Q_sym)" ] }, { "cell_type": "markdown", "id": "44d9b2a0", "metadata": {}, "source": [ "Our implementation of solving QUBO problems using QAOA works for both the upper triangular, as well as symmetrized matrix conventions. As promised, we can now immediately solve the QUBO by calling the [solve_QUBO](../../../reference/Algorithms/qaoa/implementations/QUBO.rst) method:" ] }, { "cell_type": "code", "execution_count": 2, "id": "3c69fd4c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " \u001b[2K\u001b[2K\u001b[2K\r" ] }, { "data": { "text/plain": [ "[(np.int64(-34),\n", " OutcomeArray(['1', '0', '0', '0', '1', '0'], dtype=object),\n", " 0.0496),\n", " (np.int64(-29),\n", " OutcomeArray(['0', '0', '1', '0', '0', '0'], dtype=object),\n", " 0.0584),\n", " (np.int64(-28),\n", " OutcomeArray(['0', '0', '0', '0', '0', '1'], dtype=object),\n", " 0.0614),\n", " (np.int64(-28),\n", " OutcomeArray(['0', '0', '1', '1', '0', '0'], dtype=object),\n", " 0.0412),\n", " (np.int64(-27),\n", " OutcomeArray(['0', '0', '0', '1', '0', '1'], dtype=object),\n", " 0.044)]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from qrisp.qaoa import *\n", "import numpy as np\n", "\n", "Q = np.array(\n", " [\n", " [-17, 10, 10, 10, 0, 20],\n", " [10, -18, 10, 10, 10, 20],\n", " [10, 10, -29, 10, 20, 20],\n", " [10, 10, 10, -19, 10, 10],\n", " [0, 10, 20, 10, -17, 10],\n", " [20, 20, 20, 10, 10, -28],\n", " ]\n", ")\n", "\n", "solve_QUBO(Q, depth=1, shots=5000)[:5]" ] }, { "cell_type": "markdown", "id": "adc83423", "metadata": {}, "source": [ "That's it! You can try running this block of code on the website using the Thebe interactivity integration, or run it on your own Qrispy environment. \n", "We see that we obtain the 5 best solutions with the corresponding bitsring of the binary variables. \n", "You can test the statements above, and convert the symmetrized matrix into the upper triangular one, and run ``solve_QUBO`` again.\n", "\n", "We see, that we only needed to provide the matrix $Q$, specify the depth of the QAOA circuit that is running in the background, and the backend you want to run the algorithm on. Clean and qrispy!\n", "\n", "## From QUBO to QAOA\n", "\n", "Of course it's beneficial to not only know the \"how\", but also understand the \"why\". So let's dig in!\n", "\n", "To construct such a circuit with quantum gates and run it on a quantum computer, one has to translate between the basis of $x_i$ to Pauli gate operators.\n", "\n", "$$Z_i|x\\rangle=(-1)^{x_i}\\rightarrow\\frac{\\mathbb{1}-Z_i}{2}|x\\rangle=x_i$$\n", "\n", "To find $H_C$ one can calculate\n", "\n", "$$\\begin{align*}H_C=&\\sum_{i,j=1}^nQ_{ij}\\frac{\\mathbb{1}-Z_i}{2}\\frac{\\mathbb{1}-Z_j}{2}\\\\=&\\sum_{i,j=1}^n\\frac{Q_{ij}}{4}+\\sum_{i,j}^n\\frac{Q_{ij}}{4}Z_iZ_j\\\\&-\\sum_{i=1}^n\\bigg(\\sum_{j=1}^n\\frac{Q_{ij}}{4}\\bigg)Z_i-\\sum_{j=1}^n\\bigg(\\sum_{i=1}^n\\frac{Q_{ij}}{4}\\bigg)Z_j\\end{align*}$$\n", "\n", "Swapping the indices $i$ and $j$ in the last sum, and using the identity $Z_iZ_i=\\mathbb{1}$, we get \n", "\n", "$$H_C=\\frac{1}{4}\\sum_{i\\neq j}Q_{ij}Z_iZ_j-\\frac{1}{4}\\sum_{i=1}^n\\sum_{j=1}^n(Q_{ij}+Q_{ji})Z_i+\\frac{1}{4}\\sum_{i,j=1}^nQ_{ij}+\\frac{1}{4}\\sum_{i=1}^nQ_{ii}$$\n", "\n", "Note that for each single $Z_i$ we sum the $i$-th row and the $i$-th column of the matrix $Q$. \n", "\n", "\n", "For the cost operator $U_C$, which we feed into ``QAOAProblem``, we get\n", "\n", "$$\\begin{align*}U_C=e^{-i\\gamma H_C}=&\\prod_{i,j=1}^nR_{Z_iZ_j}\\Bigg(\\frac{\\gamma}{2}Q_{ij}\\Bigg)\\times\\prod_{i=1}^nR_{Z_i}\\Bigg(-\\frac{\\gamma}{2}\\bigg(\\sum_{j=1}^n(Q_{ij}+Q_{ji})\\bigg)\\Bigg)\\\\&\\times\\exp\\Bigg(-\\frac{i\\gamma}{4}\\sum_{i,j=1}^nQ_{ij}-\\frac{i\\gamma}{4}\\sum_{i=1}^nQ_{ii}\\Bigg)\\end{align*}$$\n", "\n", "Here, the last factor correspods to a global phase.\n", "\n", "Let's translate this into a function:" ] }, { "cell_type": "code", "execution_count": 3, "id": "0bebb71d", "metadata": {}, "outputs": [], "source": [ "def create_QUBO_cost_operator(Q):\n", "\n", " def QUBO_cost_operator(qv, gamma):\n", "\n", " # Rescaling for enhancing the performance of the QAOA\n", " gamma = gamma / np.sqrt(np.linalg.norm(Q))\n", "\n", " gphase(-gamma / 4 * (np.sum(Q) + np.trace(Q)), qv[0])\n", " for i in range(len(Q)):\n", " rz(-gamma / 2 * (sum(Q[i]) + sum(Q[:, i])), qv[i])\n", " for j in range(len(Q)):\n", " if i != j and Q[i][j] != 0:\n", " rzz(gamma / 2 * Q[i][j], qv[i], qv[j])\n", "\n", " return QUBO_cost_operator" ] }, { "cell_type": "markdown", "id": "1ffddd18", "metadata": {}, "source": [ "Like we did for MaxCut and M-$\\kappa$-CS we also define the general QUBO objective function, the classical cost function, as well as construct the ``QUBOProblem`` blueprint bringing everything together." ] }, { "cell_type": "code", "execution_count": 4, "id": "ceecabaf", "metadata": {}, "outputs": [], "source": [ "from qrisp import rzz, rz, gphase\n", "import numpy as np\n", "\n", "\n", "def QUBO_obj(bitstring, Q):\n", " x = np.array(list(bitstring), dtype=int)\n", " cost = x.T @ Q @ x\n", " return cost\n", "\n", "\n", "def create_QUBO_cl_cost_function(Q):\n", "\n", " def cl_cost_function(counts):\n", "\n", " def QUBO_obj(bitstring, Q):\n", " x = np.array(list(bitstring), dtype=int)\n", " cost = x.T @ Q @ x\n", " return cost\n", "\n", " energy = 0\n", " for meas, meas_count in counts.items():\n", " obj_for_meas = QUBO_obj(meas, Q)\n", " energy += obj_for_meas * meas_count\n", " return energy\n", "\n", " return cl_cost_function\n", "\n", "\n", "def QUBO_problem(Q):\n", "\n", " from qrisp.qaoa import QAOAProblem, RX_mixer\n", "\n", " return QAOAProblem(\n", " create_QUBO_cost_operator(Q), RX_mixer, create_QUBO_cl_cost_function(Q)\n", " )" ] }, { "cell_type": "markdown", "id": "6dfe058f", "metadata": {}, "source": [ "That's it for the necessary ingredients you learned about in the QAOA tutorial! Let's solve the set partitioning problem from above using this newly acquired information, and combine with how we already ran the QAOA algorithm using the ``run`` method:\n", "\n", "- define the QUBO matrix $Q$,\n", "- define the quantum argument ``qarg`` as a [QuantumArray](../../../reference/Core//QuantumArray.rst) of [QuantumVariables](../../../reference/Core/QuantumVariable.rst),\n", "- create the QUBO instance using ``QUBO_problem`` we defined above,\n", "- run the algorithm using the ``run`` method, and last but not least,\n", "- examine the QAOA solutions and perform for classical post processing: compute the cost functions, sort the solutions by their cost in ascending order, and print the solutions with their costs.\n", "\n", "\n", ">⚠️ **Warning**\n", "\n", "> For small QUBO instance the number of ``shots`` typically exceeds the number of possible solutions.\n", "> In this case, even QAOA with ``depth=0``, i.e., sampling from a uniform superposition, may yield the optimal solution as the classical post-processing amounts to brute force search!\n", "Performance of [solve_QUBO](../../../reference/Algorithms/qaoa/implementations/QUBO.rst) for small instance may not be indicative of performance for large instances. \n", "\n", "\n", "These are exactly the pieces in the mosaic of code that ``solve_QUBO`` consists of and performs: " ] }, { "cell_type": "code", "execution_count": 5, "id": "e5da1c1b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Solution 1: ['1' '0' '0' '0' '1' '0'] with cost: -34 and probability: 0.0386 \u001b[2K\n", "Solution 2: ['0' '0' '0' '0' '0' '1'] with cost: -28 and probability: 0.0398\n", "Solution 3: ['0' '0' '1' '1' '0' '0'] with cost: -28 and probability: 0.0254\n", "Solution 4: ['0' '1' '1' '0' '0' '0'] with cost: -27 and probability: 0.0054\n", "Solution 5: ['0' '0' '0' '1' '0' '1'] with cost: -27 and probability: 0.0024\n" ] } ], "source": [ "from qrisp.default_backend import def_backend\n", "from qrisp import QuantumVariable, QuantumArray\n", "from operator import itemgetter\n", "\n", "Q = np.array(\n", " [\n", " [-17, 20, 20, 20, 0, 40],\n", " [0, -18, 20, 20, 20, 40],\n", " [0, 0, -29, 20, 40, 40],\n", " [0, 0, 0, -19, 20, 20],\n", " [0, 0, 0, 0, -17, 20],\n", " [0, 0, 0, 0, 0, -28],\n", " ]\n", ")\n", "\n", "qarg = QuantumArray(qtype=QuantumVariable(1), shape=len(Q))\n", "\n", "QUBO_instance = QUBO_problem(Q)\n", "\n", "depth = 1\n", "res = QUBO_instance.run(qarg, depth, mes_kwargs={\"backend\": def_backend}, max_iter=50)\n", "\n", "costs_and_solutions = [(QUBO_obj(bitstring, Q), bitstring) for bitstring in res.keys()]\n", "\n", "sorted_costs_and_solutions = sorted(costs_and_solutions, key=itemgetter(0))\n", "\n", "for i in range(5):\n", " print(\n", " f\"Solution {i+1}: {sorted_costs_and_solutions[i][1]} with cost: {sorted_costs_and_solutions[i][0]} and probability: {res[sorted_costs_and_solutions[i][1]]}\"\n", " )" ] }, { "cell_type": "markdown", "id": "7baf8649", "metadata": {}, "source": [ "Now you are prepared to solve all QUBOs you derive and want to solve. On the other hand, if you would just like to play around instead, try out some QUBOs from this [list of QUBO formulations](https://blog.xa0.de/post/List-of-QUBO-formulations)." ] } ], "metadata": { "kernelspec": { "display_name": "qrisp", "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.10.16" } }, "nbformat": 4, "nbformat_minor": 5 }