Unsure if the QOKit MaxCut examples are working -- `brute_force` method.

[vivekkatial]

I have been trying to use the QOKit simulator for larger instances but before that I wanted to verify it works for some trivial small ones.

I'd love some insight into if I'm doing something wrong -- thank you in advance 😁

I have created a basic 2-regular or ring graph

The solution for the two subsets are trivial:

• Subset 0: Node 0, Node 2, Node 4
• Subset 1: Node 1, Node 3, Node 5

However; when I run the code (see below) -- brute-force output is incorrect.

Pls let me know if I'm implementing this wrong?

from qokit.utils import brute_force
from qokit.qaoa_objective_maxcut import get_qaoa_maxcut_objective
from qokit.qaoa_circuit_maxcut import get_parameterized_qaoa_circuit

import gurobipy as gp
from gurobipy import GRB

# Define # of Layers
N_LAYERS = 20
# Generate a random 2-regular graph
N = 6
d = 2
seed = 1
G = nx.random_regular_graph(d,N,seed=seed)

# Build QC Circuit
qc = get_parameterized_qaoa_circuit(G, N_LAYERS)
qaoa_obj = get_qaoa_maxcut_objective(N, N_LAYERS, G)

brute_force_sol = brute_force(qaoa_obj, N, minimize=True)
print(brute_force_sol)

>>> (-1.091045519270739, array([1, 1, 0, 1, 1, 0]))

Here is a plot:

I also validated with Gurobi and it can produce the correct solution:

import gurobipy as gp
from gurobipy import GRB

for (u, v) in G.edges():
    G.edges[u, v]['weight'] = 1   # Set to 1 or some other weight if needed

# Create a new model
m = gp.Model("max_cut")
x = m.addVars(G.nodes(), vtype=GRB.BINARY, name="x")
m.setObjective(gp.quicksum(G[u][v]['weight'] * (x[u] + x[v] - 2 * x[u] * x[v]) for u, v in G.edges()), GRB.MAXIMIZE)

m.optimize()

if m.status == GRB.OPTIMAL:
    solution = m.getAttr('x', x)
    print("Solution:")
    for v in solution:
        print(f"Vertex {v}: {int(solution[v])}")
else:
    print("No optimal solution found.")

[rsln-s]

Vivek,

Apologies for the confusion! brute_force function is not meant to optimize the QAOA objective. Instead, it is meant to optimize the underlying cost function. In your example:

import networkx as nx
from functools import partial

from qokit.utils import brute_force
from qokit.maxcut import maxcut_obj, get_adjacency_matrix

# Generate a cycle graph
N = 6
G = nx.Graph()
G.add_edges_from([(i,(i+1)%N) for i in range(N)])

w = get_adjacency_matrix(G)

obj = partial(maxcut_obj, w=w)

optimal_cut, bitstring_encoding_cut = brute_force(obj, N, minimize=False, function_takes='bits')
print(f"Optimal cut: {optimal_cut}, encoded by bitstring {''.join(str(x) for x in bitstring_encoding_cut)}")

outputs

Optimal cut: 6.0, encoded by bitstring 101010

As your plot shows, this is indeed the optimal solution.