0
$\begingroup$

I am benchmarking different QUBO solvers for a very simple instance of the knapsack problem.

Some of these solvers require the matrix, Q, and offset, b, from the equation:

$$ \begin{equation} x^{\top}Qx + b \end{equation} $$

I use pyqubo to construct the problem as a QUBO and solve it which returns the optimal solution. I then attempt to extract the qubo matrix and offset by doing:

model = QUBO_equation.compile()
qubo, offset = model.to_qubo()

and convert the dictionary qubo into a numpy array.

However, when I import this numpy array to other solvers, I get very different and wrong results. Manually comparing the different solutions by using the equation above, I see that these solutions I see that these wrong solutions have lower minimum energy than the correct optimal solution. (Note: I reformulated the knapsack problem to a minimisation problem)

Is this the correct way to extract the QUBO matrix and if so why does the optimal solution that pyqubo returns not correspond to the minimum energy state of the QUBO matrix equation.

EDIT - More code showing how the Q matrix is constructed as a numpy array:

Q_matrix = np.zeros(shape = (len(binary_variables) + num_slack_bits, len(binary_variables) + num_slack_bits))

for i in range(len(binary_variables) + num_slack_bits):
    for j in range(len(binary_variables) + num_slack_bits):
        try:
            Q_matrix[i][j] = qubo[("x"+str(i),"x"+str(j))]
            Q_matrix[j][i] = qubo[("x"+str(i),"x"+str(j))]
        except KeyError: 
            pass

This creates a square symmetric matrix which is required for the other solvers.

$\endgroup$
2
  • $\begingroup$ Your question is really vague and there are millions things that you could be doing wrong. You should provide the smallest possible working example with outputs. On the first glance the difference in objective values might be coming from the offset $b$. $\endgroup$
    – MonteNero
    Commented Apr 18, 2023 at 15:58
  • $\begingroup$ Thanks for the feedback, I'll add more code showing how the Q matrix is constructed as an array (for now and will add a small example later). Also I have tried both considering and not considering the offset and the results were the same regardless. $\endgroup$ Commented Apr 19, 2023 at 9:50

0

Your Answer

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