Max_continued

https://learning.quantum.ibm.com/tutorial/quantum-approximate-optimization-algorithm

Started work on the Max-Cut problem on a quantum computer. The tutorial

runs first on a modest problem with 5 vertices and 6 edges; later runs again on

a 125-node graph. I am currently on part 1. Interestingly, I will need to use

the quantum computer twice for each subproblem: once with Estimator and once

with Sampler. I am waiting on ibm_brisbane to process my Estimator run.

First, I had to clarify the statement of the problem for myself, which is just math

at this point. How does this formula represent a Max-Cut problem?

                                                                    

Graph theory; help me understand how this formula maximizes the possible number of cuts in a graph.

Explanation

• Binary Variables: $x_i\in \{0,1\}x\_i\; \backslash in\; \backslash \{0,\; 1\backslash \}$ for $i=1,2,\dots ,ni\; =\; 1,\; 2,\; \backslash ldots,\; n$. Each variable $x_{i}x\_i$ represents whether a vertex $ii$ is in one of the two sets (0 or 1).

• Objective Function: The goal is to maximize the sum of the expression $x_i+x_j-2x_i{x}_{j}x\_i\; +\; x\_j\; -\; 2x\_i\; x\_j$ over all edges $(i,j)(i,\; j)$ in the graph.

How It Works

1. Same Set: If both vertices $ii$ and $jj$ are in the same set (either both 0 or both 1), then:

   • $x_i=x_{j}x\_i\; =\; x\_j$

   • $x_i+x_j-2x_i{x}_j=0x\_i\; +\; x\_j\; -\; 2x\_i\; x\_j\; =\; 0$

   • This means no cut is made between these vertices.

2. Different Sets: If vertices $ii$ and $jj$ are in different sets (one is 0 and the other is 1), then:

   • $x_i\mathrm{\ne }{x}_{j}x\_i\; \backslash neq\; x\_j$

   • $x_i+x_j-2x_i{x}_j=1x\_i\; +\; x\_j\; -\; 2x\_i\; x\_j\; =\; 1$

   • This means a cut is made between these vertices.

Maximizing the Cuts

The formula sums up the values for all edges in the graph. By maximizing this sum, the algorithm ensures that as many edges as possible are between vertices in different sets, thus maximizing the number of cuts.

                                                                          *      *     *

I got timed out for running a session too long. I was only running half the code, so I assume

the computer was waiting for the second part. Running again with the whole MaxCut mini code!!!