{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Max Cut\n", "\n", "### Definition\n", "\n", "We are given an undirected graph with vertex set $V$ and edge set $E$. \n", "\n", "Our aim is to partition the graph into two subgraphs connected by the maximum number of edges.\n", "\n", "### Applications\n", "\n", "MaxCut is a ubiquitous problem in fields like Network Design, Statistical Physics, Very Large Scale Integration (VLSI), Circuit Layout Design, Data Clustering.\n", "\n", "### Path to solving the problem\n", "\n", "MaxCut is a maximization problem and its cost function can be cast to an Ising problem through its respective Hamiltonian (see the [Introduction](./introduction_combinatorial_optimization_myqlm.ipynb) and a [reference](https://en.wikipedia.org/wiki/Maximum_cut#Theoretical_physics)),\n", "\n", "$$ \\displaystyle \\large\n", "H = \\displaystyle \\textstyle\\sum\\limits_{uv \\in E} s_{u} s_{v}\n", "$$\n", "\n", "where $v, u \\in V$ and $s_u$ is a spin variable, which is $1$ if vertex $u$ is in the one subgraph and $-1$ if it is in the other.\n", "\n", "The myQLM allows us to encode a problem in this Hamiltonian form by using the `MaxCut` class with some specified graph. We can then create a job from the problem and send it to a Simulated Annealer (SA) wrapped with a Quantum Processing Unit (QPU) interface. The SA will minimize the Hamiltonian, hence we find the best solution to our problem.\n", "\n", "In fact, the QLM contains an even more powerful solver $-$ Simulated Quantum Annealing (SQA). This quantum annealer has been tested on numerous benchmarks for the NP problems supported and produces results with a quality usually exceeding $98\\%$. More details can be found in the [documentation](https://myqlm.github.io/advanced_combinatorial_optimization.html#simulated-quantum-annealing-benchmarking-and-performance).\n", "\n", "### Quantum resources\n", "\n", "To represent the problem as Ising, myQLM would need $N$ spins (one spin per vertex). " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Example problem" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Imagine we are given a tree graph with $30$ vertices and $29$ edges, as shown below (left). One may quickly figure that we can partition the graph into two subgraphs, connected by all the graph edges. To achieve this, we can simply colour the nodes on the even levels of the tree graph by one colour, and the nodes on the odd levels $-$ by the other (right).\n", "\n", "

\n", "\n", "Let us now describe how one can reach this answer using tools from myQLM. Furthermore, the approach will be applicable to finding the MaxCut of any graph!\n", "\n", "We will start by specifying the graph with the `networkx` library, which allows us to explore a huge variety of graphs." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "# Specify the graph \n", "graph = nx.full_rary_tree(2, 30)\n", "\n", "# Draw the graph - may take time for bigger graphs\n", "nodes_positions = nx.spring_layout(graph, iterations=len(graph.nodes()) * 100)\n", "plt.figure(figsize=(14, 9))\n", "nx.draw_networkx(graph, \n", " pos=nodes_positions, \n", " node_color='#4EEA6A', \n", " node_size=440, \n", " font_size=14)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The `MaxCut` class can now be called with this graph as input." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from qat.opt import MaxCut\n", "\n", "max_cut_problem = MaxCut(graph)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Resolution of the problem using a BatchGenerator\n", "\n", "A high level solver of the MaxCut problem is available in the QLM under the form of a BatchGenerator called `MaxCutGenerator`.\n", "It is designed as simple interface to solve the problem on an input graph, while hiding the complexities of the underlying\n", "algorithms.\n", "\n", "The different resolution methods that can be selected are \"qaoa\" (for QAOA Circuit Generation), \"annealing\" (for\n", "Simulated Quantum Annealing), and \"schedule\" (for Analog Quantum Scheduler Generation). A user-interpretable result is\n", "returned from the job execution, where the two resulting partitions of the nodes and the number of edges cut can be retrieved\n", "from the subsets and cost attribute respectively. A display method is also provided by the result object to visualize the\n", "partitioning of the graph.\n", "\n", "An example of using the batch generator to generate a quantum annealing job and executing it with SimulatedAnnealing is provided below." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from qat.generators import MaxCutGenerator\n", "from qat.qpus import SimulatedAnnealing\n", "from qat.core import Variable\n", "\n", "# 1. Extract parameters for SA\n", "problem_parameters_dict = max_cut_problem.get_best_parameters()\n", "n_steps = problem_parameters_dict[\"n_steps\"]\n", "temp_max = problem_parameters_dict[\"temp_max\"]\n", "temp_min = problem_parameters_dict[\"temp_min\"]\n", "\n", "# 2. Create a temperature schedule and a QPU\n", "tmax = 1.0\n", "t = Variable(\"t\", float)\n", "temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)\n", "\n", "max_cut_application = MaxCutGenerator(job_type=\"sqa\") | SimulatedAnnealing(temp_t=temp_t, n_steps=n_steps)\n", "combinatorial_result = max_cut_application.execute(graph)\n", "\n", "print(\"The nodes in the first subgraph are\", combinatorial_result.subsets[0])\n", "print(\"The nodes in the second subgraph are\", combinatorial_result.subsets[1])\n", "# The cost here is negative since all combinatorial optimization problems are defined as a minimization problem, so a factor of -1 is needed\n", "print(\"The number of edges that are cut is\", -1 * combinatorial_result.cost)\n", "\n", "combinatorial_result.display(with_figure=True, figsize=(14, 9), node_size=440, font_size=14, pos=nodes_positions)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Simulated Annealing\n", "\n", "If we want to solve the problem with SA straight, we can still do so via the following steps:\n", "\n", "1. Extract some fine-tuned parameters for MaxCut (found for SQA) which are needed for the temperature schedule.\n", "\n", "\n", "2. Create the temperature schedule using the `t` time variable (instance of the class `Variable`) and thus the `SimulatedAnnealing` QPU.\n", "\n", "\n", "3. Create a job from the problem by calling the `to_job()` method and send it to the QPU.\n", "\n", "\n", "4. Extract the `Result` and present the solution spin configuration.\n", "\n", "\n", "5. Draw the respective nodes of each subgraph.\n", "\n", "Each spin from the solution configuration corresponds to a node from the graph at the same position. Note that if the numbering of the input nodes starts from $1$ and not from $0$, one still needs to look at the $0$th spin to extract information for this first node, numbered as $1$.\n", "\n", "When a spin has the value of $1$ or $-1$, this means that the respective node belongs to the one or the other subgraph. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from qat.qpus import SimulatedAnnealing\n", "from qat.simulated_annealing import integer_to_spins\n", "from qat.core import Variable\n", "\n", "# 1. Extract parameters for SA\n", "problem_parameters_dict = max_cut_problem.get_best_parameters()\n", "n_steps = problem_parameters_dict[\"n_steps\"]\n", "temp_max = problem_parameters_dict[\"temp_max\"]\n", "temp_min = problem_parameters_dict[\"temp_min\"]\n", "\n", "# 2. Create a temperature schedule and a QPU\n", "tmax = 1.0\n", "t = Variable(\"t\", float)\n", "temp_t = temp_min * (t / tmax) + temp_max * (1 - t / tmax)\n", "sa_qpu = SimulatedAnnealing(temp_t=temp_t, n_steps=n_steps)\n", "\n", "# 3. Create a job and send it to the QPU\n", "problem_job = max_cut_problem.to_job('sqa', tmax=tmax)\n", "problem_result = sa_qpu.submit(problem_job)\n", "\n", "# 4. Extract and print solution configuration\n", "state = problem_result.raw_data[0].state.int # raw_data is a list of Samples - one per computation\n", "solution_configuration = integer_to_spins(state, len(graph.nodes()))\n", "print(\"Solution configuration: \\n\" + str(solution_configuration) + \"\\n\")\n", "indices_spin_1 = np.where(solution_configuration == 1)[0]\n", "print(\"The nodes in the first subgraph:\\n\" + str(indices_spin_1) + \"\\n\")\n", "indices_spin_minus_1 = np.where(solution_configuration == -1)[0]\n", "print(\"The nodes in the second subgraph:\\n\" + str(indices_spin_minus_1))\n", "\n", "# 5. Draw the coloured subgraphs - may take longer for larger graphs\n", "plt.figure(figsize=(14, 9))\n", "node_size = 440\n", "font_size = 14\n", "nx.draw_networkx(graph, \n", " pos=nodes_positions, \n", " nodelist=indices_spin_1.tolist(), \n", " node_color='#FFE033', \n", " node_size=node_size, \n", " font_size=font_size)\n", "\n", "nx.draw_networkx(graph, \n", " pos=nodes_positions, \n", " nodelist=indices_spin_minus_1.tolist(), \n", " node_color='#7B9BF2', \n", " node_size=node_size, \n", " font_size=font_size)\n", "\n", "nx.draw_networkx_edges(graph, pos=nodes_positions)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution analysis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We are interested in how well the partitioning went. We know that for a tree, the number of connecting edges should be all edges. So we can compare this to the number of edges between the nodes we coloured." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "number_of_edges_connecting_subgraphs = 0\n", "for (u, v) in graph.edges():\n", " if solution_configuration[u] * solution_configuration[v] == (-1):\n", " number_of_edges_connecting_subgraphs += 1\n", "\n", "print(\"For a MaxCut partitioned tree graph the number of connecting edges is:\")\n", "print(len(graph.edges()))\n", "\n", "print(\"Number of edges, which connect the two partitioned subgraphs:\")\n", "print(number_of_edges_connecting_subgraphs)" ] } ], "metadata": { "authors": [ "Grigori Matein" ], "documentation-tags": { "icon": [ "share-android", ":material-outlined:`format_align_justify;3em`" ], "level": "beginner" }, "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.12.11" } }, "nbformat": 4, "nbformat_minor": 4 }