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[11]).controlled_by(*(qq[5:11]))

def oracle_computation2(qq):
    yield oracle2(qq)
    yield Z(qq[11])
    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)
    circuit = cirq.Circuit()
    for i in range(2):

    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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.