• Members 12 posts

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)

• Members 22 posts

When it comes to applying the optimization algorithms, the algorithms usually require problems to satisfy certain criteria to be applicable. For example, variational algorithms such as VQE and QAOA can only be applied to Quadratic Unconstrained Binary Optimization (QUBO) problems