# QAOA not returning solution for simple clustering problem

I am following University's of toronto QML course and there's a section where QAOA is applied to cluster a set of vectors by mapping the clustering problem into a Maxcut problem. Unfortunately qiskit's QAOA is not returning the right solution (even within the course's notebook lecture), so I am a bit lost in the implementation.

The (4) points are (top two are on the top left corner and bottom two on the bottom right corner)

data = array([[ 0.11 ,  0.143],
[ 0.121,  0.109],
[-1.515,  1.629],
[-1.512,  1.678]])


And the distance matrix (used as the 'weight' matrix of the maxcut graph) is

w = array([[0.   , 0.   , 2.202, 2.234],
[0.   , 0.   , 2.233, 2.265],
[2.202, 2.233, 0.   , 0.   ],
[2.234, 2.265, 0.   , 0.   ]])


(distances < 0.5 were mapped to 0 as pre-processing).

Using Qiskit's max_cut class, we map w into an Ising problem. We also verify the best solution

qubit_operators, offset = max_cut.get_max_cut_qubitops(-w)
// checking for solutions (cleary 0011 and 1100 are the solutions)
(0, 0, 0, 0) 4.466870101471442
(0, 0, 0, 1) 0.031168254348417523
(0, 0, 1, 0) -0.031168254348417523
(0, 0, 1, 1) -4.466870101471442
(0, 1, 0, 0) 0.03160476231770515
(0, 1, 0, 1) 0.0001477223286934226
(0, 1, 1, 0) -0.0001477223286934226
(0, 1, 1, 1) -0.03160476231770515
(1, 0, 0, 0) -0.03160476231770515
(1, 0, 0, 1) -0.0001477223286934226
(1, 0, 1, 0) 0.0001477223286934226
(1, 0, 1, 1) 0.03160476231770515
(1, 1, 0, 0) -4.466870101471442
(1, 1, 0, 1) -0.031168254348417523
(1, 1, 1, 0) 0.031168254348417523
(1, 1, 1, 1) 4.466870101471442


after inputting the mapped operator and running it on Qiskit's QAOA

from qiskit.aqua import get_aer_backend, QuantumInstance
from qiskit.aqua.algorithms import QAOA
from qiskit.aqua.components.optimizers import COBYLA
from qiskit.aqua.translators.ising import max_cut

p = 1

#w = -w
qubit_operators, offset = max_cut.get_max_cut_qubitops(-w)
p = 1
optimizer = COBYLA()
qaoa = QAOA(qubit_operators, optimizer, p)
backend = get_aer_backend('statevector_simulator')
quantum_instance = QuantumInstance(backend, shots=10)
result = qaoa.run(quantum_instance)


The output is the following:

{'num_optimizer_evals': 13,
'min_val': 0.0,
'opt_params': array([0., 0.]),
'eval_time': 0.32109689712524414,
'eval_count': 13,
'energy': 0.0,
'eigvals': array([0.]),
'min_vector': array([0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j,
0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j,
0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j]),
'eigvecs': array([[0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j,
0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j,
0.25+0.j, 0.25+0.j, 0.25+0.j, 0.25+0.j]])}


It seems as if the QAOA never evolves (optimal $$\gamma$$ and $$\beta$$ are 0) and stays in the mixer's ground state.

Has anyone experienced the same problem?

I'm using Qiskit's 0.9.0 (otherwise code is not compatible with the course).

• This makes sense, since $|0\rangle^n$ is indeed an eigenstate. But isn't the point of the mixer is to help to avoid such local minimum in the first place? I don't know what type of circuit is the OP used but I am assuming it's a typical QAOA circuit deriving from the discretization of the adiabatic quantum annealing process. Commented May 24, 2021 at 14:58