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

Question

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.

Answer 1

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) $$

ref 1: Experiments in 0-1 programming