I came across a qiskit example of solving max-cut problem with QAOA (see below). While defining this problem, the max-cut problem is converted to a quadratic program. Can anyone help me understand why the quadratically constrained quadratic program is suitable for max-cut problems?
Here is the qiskit example:
import networkx as nx
# Make a graph with degree=2 node=5
graph = nx.random_regular_graph(d=2, n=5, seed=111)
pos = nx.spring_layout(graph, seed=111)
# Application class for a Max-cut problem
# Make a max-cut problem from the graph
from qiskit_optimization.applications import Maxcut
maxcut = Maxcut(graph)
# Make a QuadraticProgram by calling to_quadratic_program()
qp = maxcut.to_quadratic_program()
# Solving max-cut problem with QAOA
from qiskit import Aer
from qiskit.utils import QuantumInstance
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit.algorithms import QAOA, NumPyMinimumEigensolver
qins = QuantumInstance(backend = Aer.get_backend('qasm_simulator'), shots = 1000, seed_simulator = 123)
# Define QAOA solver
meo = MinimumEigenOptimizer(min_eigen_solver = QAOA(reps = 1, quantum_instance = qins))
result = meo.solve(qp)