# How to convert QUBO (with non-zero diagonal elements) to Maxcut?

I want to solve QUBO with non-zero diagonal elements in matrix Q using QAOA. But I want to solve for a large enough problem size (30+ variables) and hence want to divide my circuit into subcircuits. Circuit cutting didn't work out for me, because graph is dense, so I want to try divide-and-conquer approaches proposed here and here. However, both papers divide the Maxcut problem. Hence the question: How to convert QUBO (with non-zero diagonal elements) to Maxcut? In this paper it is stated and shown that QUBO and Maxcut are equivalent. However, I haven't fully understood the proof and my code based on this proof isn't working (optimal cut isn't an optimal solution). Here's the code:

h, J, ising_offset = from_Q_to_Ising(Q, qubo_offset)
G = nx.Graph()
for ki, v in h.items():
if abs(v) > 1e-3:
# add new node and connect it with other nodes where diagonal weight is non-zero
# flip the weight sign
G.add_edge(0, ki[0] + 1, weight = -v)
for kij, vij in J.items():
if abs(vij) > 1e-3:
# flip the weight sign
G.add_edge(kij[0] + 1, kij[1] + 1, weight = -v)


Would be thankful for any suggestions regarding conversion, or any other way to use these divide-and-conquer approaches or other ways to split the QAOA circuit.

• You confused several concepts. MaxCut is an optimization problem; as the name suggests, it finds the maximum cut in a graph. QUBO is the name of the framework for formulating optimization problems. You can convert many optimization problems into QUBO formulation. Asking to convert QUBO into MaxCut is a meaningless question. Besides, all non-linear QUBO problems have non-zero non-diagonal elements. MaxCut is already formulated as a QUBO problem (in many physics papers), which is why it is used as a canonical example for many quantum optimization tutorials. Commented Apr 13 at 18:02
• @MonteNero I have a problem to solve (RCPSP to be exact), that I formulated as QUBO. However, I don't understand how to use all the MaxCut research (more specifically divide-and-conquer) for my QUBO formulation, as it has a linear component. Commented Apr 13 at 18:29
• I think I understand what you want to do. I suggest formulating a concrete, specific question. Currently, you posted a code unrelated to optimization and asked several vague general questions. This will improve your chances of getting an answer you are looking for. Commented Apr 13 at 21:09

It is well-known that any QUBO problem can be translated into an equivalent maximum cut problem (MaxCut), see ref 1. Given a weighted graph ( G = (V, E) ) with edge weights ( w_{ij} ), where ( ij \in E ), MaxCut asks for a partition of the vertices into two subsets such that the weight of connecting edges is maximized. More formally, for a vertex subset ( W \subset V ), we define the cut

$$\delta(W) = \{ ij \in E \mid i \in W, j \notin W \}$$

Furthermore, the weight of a cut ( \delta(W) ) is defined as

$$\sum_{e \in \delta(W)} w_e$$

MaxCut asks for a cut of maximum weight. The decision version of MaxCut is NP-complete [45].

A QUBO problem on ( n ) variables, defined by the coefficients ({q_{ij}}, j \in {1, \ldots, n}), can be transformed into an equivalent MaxCut problem on ( n + 1 ) vertices. To this end, we consider the complete graph ( K_{n+1} ) with vertices

$$V = \{0, 1, \ldots, n\}$$

For an edge ( ij ) with ( i, j > 0 ), we define its weight as

$$w_{ij} = q_{ij} + q_{ji}$$

Moreover, for all edges of the form ( 0i ) with ( i > 0 ), we set

$$w_{0i} = \sum_{j=1}^{n} q_{ij} + q_{ji}$$

Deleting edges with zero weight finally yields a weighted MaxCut instance ( G = (V, E) ). Given a cut ( \delta(W) ), we construct a solution ( Q ) as follows. For ( i \in {1, \ldots, n} ), we set ( x_i = 1 ) if ( i \notin \delta(W) ), otherwise we set ( x_i = 0 ). It is easily verified that if the cut has weight ( M ), the QUBO solution has value

$$Q = -\frac{M}{2} + C$$

where

$$C = \frac{1}{4} \left( \sum_{e \in E} w_e + 2 \sum_{i} q_{ii} + \sum_{i < j} q_{ij} + q_{ji} \right)$$