0
$\begingroup$

I am trying to find the minimum cut for a given graph. I am using QAOA and refering to the qiskit textbook: https://qiskit.org/textbook/ch-applications/qaoa.html. I understand I need to find the minimum eigenvalue.

I am confused on 2 main points:

  1. How the graph is connected to the circuit, we change it to a bit string and then parameterize it with the unitary Rx ...?
  2. how this maxcut def works so how can I change it to mincut?

Still working on understanding what max/min cut is.

def maxcut_obj(x, G): """ Given a bitstring as a solution, this function returns the number of edges shared between the two partitions of the graph.

Args:
    x: str
       solution bitstring
       
    G: networkx graph
    
Returns:
    obj: float
         Objective
"""
obj = 0
for i, j in G.edges():
    if x[i] != x[j]:
        obj -= 1
        
return obj
Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I think that it is certainly possible to formulate a QAOA instance for Minimum Cut, however I should mention that Minimum Cut is equivalent to max flow and there exist classical polynomial time algorithms to solve that problem (see here and here). Maximum Cut though is NP-Hard.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It is possible, it's a matter of looking for the minimum eigenvalue instead of the maximum. I am actually trying to do a max flow however I don't think your answer is helpful here. I'm looking for how to switch from max to min, not if it's possible or applications $\endgroup$
    – epsilonolispe
    Jan 18 at 12:19
  • 1
    $\begingroup$ @epsilonolispe, Elijah brought up a good point about min cut being solvable exactly in poly time by a classical algorithm. Doing this with QAOA just doesn't make any sense because it is a heuristic and can only give a probabilistic answer. Also, max cut is NP-complete and min-cut is in P, so it will not just be switching from max to min. $\endgroup$
    – MonteNero
    Jan 18 at 13:59
  • $\begingroup$ I'm not sure I agree with you on the point that it' switching from a max to a min, it's grabbing the minimum eigenvalue, no? Sure, perhaps it's not better but I'm still hoping to attempt it! $\endgroup$
    – epsilonolispe
    Jan 18 at 17:32

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.