# MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

A paper was published recently in Science where the authors minimized the following function:

$$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$

where $$s_i$$ denotes the $$i$$th Ising spin, which takes a value of 1 or -1, $$s = (s_1 s_2 \cdots s_N)$$ is the vector representation of a spin configuration, and $$J_{i,j}(=J_{j,i})$$ is the coupling coefficient between the $$i$$th and $$j$$ spins ($$J_{i,i}=0$$). The problem is to find a spin configuration minimizing the Ising energy. This problem is mathematically equivalent to a famous combinatorial optimization problem named MAX-CUT (5, 17, 18, 39): divide the nodes of a weighted graph into two groups maximizing the total weight (called "cut value") of the edges cut by the division. By setting the coupling coefficient as $$J_{i,j} = - w_{i,j}$$ ($$w_{i,j} = w_{j,i}$$ is the weight between $$i$$th and $$j$$th nodes), we can solve MAX-CUT using Ising machines.

In particular, it appears that they are solving instances of weighted MAX-CUT where the input graph is the complete graph on 2000 vertices with edge weights assigned from $$\{-1,1\}$$ independently and uniformly at random.

They say they found solutions in 0.5 ms and the other specifics such as the criteria for calling something a "solution" are also given.

They say in the abstract that 0.5ms is 10 times faster than the Coherent Ising Machine (a type of quantum calculator), but I would like it to instead be compared to state-of-the-art for conventional algorithms on classical computers.

It should be possible to generate the same type of random instances of MAX-CUT as the authors, and solve the problem with a conventional algorithm for classical computing (e.g. CPUs, GPUs, FPGAs), and compare the performance to what is claimed in the paper, when using the same criteria for what is considered a good enough solution. Are there any algorithms or codes apart from just general SAT/CSP solvers, that could be applied to this specific problem?

• With @mhum's insight about the specific values of $J_{ij}$ and how they are chosen, we can easily generate many random instances of the MAX-CUT problem treated in this paper, and see how conventional classical-computer algorithms would perform. Does anyone know which research groups might have good tools to check such a thing? I am indeed aware that things will depend on the hardware (e.g. 2007 AMD CPU vs 2019 Intel CPU vs 2019 NVidia GPU) and how many machines are running in parallel, but once we know what the state-of-the-art algorithms and software are, I'm not too worried anymore. – user1271772 May 8 at 17:14
• A problem is that the authors don't care about finding optimal solutions, making the comparison even more difficult. I really don't think this question can be answered in a meaningful way and have voted to close it as opinion-based. – Juho May 8 at 18:07
• @Juho: I completely disagree that this should be closed as an "opinion-based" question. The paper compared their FPGA implementation to the CIM implementation and found that they were 10x faster for the same types of instances and the same definition of "good solutions". I am asking to compare to conventional SAT solvers (for example) instead of comparing to this obscure and largely unknown "coherent Ising machine" or CIM. I have improved the language in the question again. – user1271772 May 8 at 18:38
• But the problem is that there are too many moving parts and things that are not precisely quantified, such as the quality of the solutions accepted. Let us let the community decide, but I hope that I am proved wrong and you get a satisfying answer. – Juho May 8 at 18:45
• Could you add this criteria to the question? It's always better if the reader does not have to follow external links which also have a habit of dying. – Juho May 8 at 19:08