<jupyter_start><jupyter_text>Prepared by  <NAME>          Examples for QUBO Formulation In the previous section, we learnt about the objective functions and QUBO problems. Now, lets apply the QUBO formulation to some of the combinatorial optimization problems.   Maximum Cut Given a graph, the problem requires splitting the vertices/nodes into two disjoint groups so that there are as many edges as possible between the groups. The partition of two adjacent vertices into disjoint sets is called a cut. The goal of this problem is to find a cut in such a way that the cut covers the maximum number of edges.Since we have to partition the vertices in the graph, we will assign a binary variable for each vertex, i.e. variable $x_i$:* $x_i=0$ if vertex i is a part of Group 1* $x_i=1$ if vertex i is a part of Group 2**The objective function for optimization is maximizing the number of cut edges.** For a particular graph, let's consider a single edge. We only want to count an edge if the endpoints/vertices are in different groups. Let this be denoted by a function i.e. edge_count$(x_i,x_j)$ which depends on the values of $x_i$ & $x_j$. If vertices are in different groups, edge_count$(x_i,x_j)$ gives a 1; otherwise 0.|$x_i$ |$x_j$|edge_count$(x_i,x_j)$|Comment||:-----|:----:|:----:|:----:||0 |0 |0 |Vertices are in the same group||0 |1 |1 |Vertices are in different groups||1 |0 |1 |Vertices are in different groups||1 |1 |0 |Vertices are in the same group|From this table, we observe that we can use the expression $x_i+x_j-2x_ix_j$ to calculate the edge_count in the table.   Task 1Verify that the expression $x_i+x_j-2x_ix_j$ gives correct values of edge_count in the table.  [Click here for solution](QUBO_Examples_MaximumCut_Solutions.ipynbtask1)*** Since our objective function is maximizing the total number of cut edges, for our entire graph, our objective function is:$$\max \sum_{(i,j) \in E} (x_i+x_j-2x_ix_j)$$where the sum is over edge set E in the graph.Since QUBO formulation minimizes an objective function, we must convert this maximization problem to a minimization problem by multiplying the expression by -1. Our final QUBO expression is the following:$$\min \sum_{(i,j) \in E} (-x_i-x_j+2x_ix_j)$$ Example 1Let's assume we have a simple network of 5 vertices and 6 edges. Using the QUBO expression $\min \sum_{(i,j) \in E} (-x_i-x_j+2x_ix_j)$ and summing over the edges,$\min y = (-x_1-x_2+2x_1x_2)+(-x_1-x_3+2x_1x_3)+(-x_2-x_4+2x_2x_4)+(-x_3-x_4+2x_3x_4)+(-x_3-x_5+2x_3x_5)+(-x_4-x_5+2x_4x_5)$$\min y = -2x_1-2x_2-3x_3-3x_4-2x_5+2x_1x_2+2x_1x_3+2x_2x_4+2x_3x_4+2x_3x_5+2x_4x_5$Since QUBO doesn't have squared binary variables as its 0 and 1 values remain unchanged when squared, so we can replace any term $x_i^2$ with $x_i$, and vice versa (this doesnt apply to products $x_i x_j$).$\min y = -2x_1^2-2x_2^2-3x_3^2-3x_4^2-2x_5^2+2x_1x_2+2x_1x_3+2x_2x_4+2x_3x_4+2x_3x_5+2x_4x_5$This takes the desired form:$$\min_{x \in {0,1}^n} x^T Q x$$where $x$ is:$$x = \begin{pmatrix}x_1 \\x_2 \\x_3 \\x_4 \\x_5 \end{pmatrix}$$and the upper diagonal matrix Q is:$$Q = \begin{pmatrix}-2 & 2 & 2 & 0 & 0\\0 & -2 & 0 & 2 & 0\\0 & 0 & -3 & 2 & 2\\0 & 0 & 0 & -3 & 2\\0 & 0 & 0 & 0 & -2\end{pmatrix}$$If we dont replace the binary variables, this can be visualized this way that the linear terms determine the elements on the main diagonal of Q and the quadratic terms determine the off-diagonal elements.   Task 2Let's assume we have a simple network of 5 vertices and 7 edges. Using the QUBO expression $\min \sum_{(i,j) \in E} (-x_i-x_j+2x_ix_j)$, determine the matrix Q for this graph.  [Click here for solution](QUBO_Examples_MaximumCut_Solutions.ipynbtask2)*** Continuing Example 1, let's minimize our QUBO objective function and find the optimum $x$ that results in a division of vertices with the greatest edge-cut size. Edge-cut size is a measure of the total number of edges crossed by a cut. Testing all possibilities of $x$, our QUBO model has a **minima at $x=(0,1,1,0,0)$**. This means that the cut partitions vertices 1, 4 & 5 in Group 1 and vertices 2 & 3 in Group 2, with a **maximum edge-cut size of 5**.   Task 3By testing all possibilities of edge-cut sizes, verify that the QUBO model in Example 1 has a minima at $x=(0,1,1,0,0)$ with a maximum edge-cut size of 5. [Click here for solution](QUBO_Examples_MaximumCut_Solutions.ipynbtask3)*** Such a tedious task, right? Let's make our lives easier by doing it with Python.   Task 4Input matrix Q calculated in Example 1 to the function *qubo_solver()* and determine $x$ which minimizes $x^T Qx$ and the corresponding minimum value.$$Q = \begin{pmatrix}-2 & 2 & 2 & 0 & 0\\0 & -2 & 0 & 2 & 0\\0 & 0 & -3 & 2 & 2\\0 & 0 & 0 & -3 & 2\\0 & 0 & 0 & 0 & -2\end{pmatrix}$$<jupyter_code>#Access the qubo_solver() function
%run qubo_functions.py

# Define the Q matrix



# Pass the matrix as an argument to the function
qubo_solver(Q)<jupyter_output><empty_output><jupyter_text>[Click here for solution](QUBO_Examples_MaximumCut_Solutions.ipynbtask4)***  Task 5Repeat Task 4 for the matrix Q calculated in Task 2.<jupyter_code>#Access the qubo_solver() function
%run qubo_functions.py

# Define the Q matrix
#Assign it the name Q2



# Pass the matrix as an argument to the function
qubo_solver(Q2)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10488587059045464, 'fraction_numerical': 0.04074702886247878, 'mean_word_length': 4.410204081632653, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '527816', 'license': 'MIT', 'n_tokens_mistral': 1913, 'n_tokens_neox': 1775, 'n_words': 745, 'path': 'notebooks/.ipynb_checkpoints/QUBO_Examples_MaximumCut-checkpoint.ipynb', 'repo_name': 'ozlemsalehi/qa-edu', 'size': '5313'}