2
$\begingroup$

In QAOA, for the MaxCut problem, one tries to find a good ratio, as close to 1 as possible, of $\epsilon = \frac{C_{approx}}{C_{opt}}$, where $C_{approx}$ is the approximate value of the cost function for some configuration of spins and $C_{opt}$ is the optimum cost value for the given graph. I want to calculate $\epsilon$ for some random instances of the MaxCut problem (with small number of vertices) and test how good the algorithm behaves.

In order to do that though, I need the exact solution of a given instance. I was wondering what is the best way to calculate it? Do a brute force in the whole configuration space? Finally, is there any Python library that will help me with my problem of obtaining the optimum solution, given the graph?

$\endgroup$
2
$\begingroup$

Until a better solution is provided, I hope this suggestion is helpful.

Reducing MaxCut to Max-2SAT is straightforward (https://cs.stackexchange.com/a/93492/115012)

And there are many free, highly optimized MaxSAT solvers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.