# Grover's algorithm for max cut problem - Implementation in cirq

I am using the Grover's algorithm for max cut problem using an oracle for the graph described below to check whether it admits a valid 2-coloring.

Here are the edges: (0,3),(0,4),(1,3),(1,4),(2,3),(2,4)

Qubits 0-4 are for the vertices, 5-10 for the edges and 11 for the ancilla.

The results make sense intuitively (The most frequent outputs are 00011 and 11100, so the max-cut cuts the edges between (0,1 and 2) and (3,4) ) but It seems that the implementation is not correct. I want to make sure the Oracle implementation is correct.

s = cirq.Simulator()

qq = cirq.LineQubit.range(12)

def edge_check(a, b, c):
yield CX(qq[a], qq[c])
yield CX(qq[b], qq[c])

def oracle2(qq):
#     qubits 0-4 for the vertices, 5-10 for the edges and 11 as the ancilla.

# check 0-3 edge and store at 5th qubit
yield edge_check(0, 3, 5)

# check 0-4 edge and store at 6th qubit
yield edge_check(0, 4, 6)

# check 1-3 edge and store at 7th qubit
yield edge_check(1, 3, 7)

# check 1-4 edge and store at 8th qubit
yield edge_check(1, 4, 8)

# check 2-3 edge and store at 9th qubit
yield edge_check(2, 3, 9)

# check 2-4 edge and store at 10th qubit
yield edge_check(2, 4, 10)

# check all edge qubits
yield X(qq).controlled_by(*(qq[5:11]))

def oracle_computation2(qq):
yield oracle2(qq)
yield Z(qq)
yield inverse(oracle2(qq))

def grover2(trials_number):
import cirq
from cirq import X, H, Z, inverse, CX
s = cirq.Simulator()

qq = cirq.LineQubit.range(12)
n=5

circuit = cirq.Circuit()
circuit.append(H.on_each(*(qq[0:n])))
for i in range(2):
circuit.append(oracle_computation2(qq))
circuit.append(grover_diffusion(qq,n))

circuit.append(cirq.measure(*(qq[0:n]), key='result'))

# determine the statistics of the measurements
samples = s.run(circuit, repetitions=trials_number)
result  = samples.measurements["result"]

def bitstring(bits):
return "".join(str(int(b)) for b in bits)

counts = samples.histogram(key="result",fold_func=bitstring)
return counts

shots = 1000
grover2(shots)