Objective function of a general QUBO problem

[eegzheng]

In you example "Simulation of QAOA applied to a general problem", you gave an example specified by 'terms' below:

N = 4 np.random.seed(10) terms = [(np.random.normal(), spin_pair) for spin_pair in combinations(range(N), r=2)]

I wonder how to get the objective function in order to optimize this general Hamiltonian. Many thanks.

[rsln-s]

@eegzheng, I would like to apologize for the slow response on this. Could you clarify your question? Specifically, what kind of objective function are you looking for? The example you listed shows how to get QAOA objective for this problem.

[eegzheng]

@rsln-s, thank you for your reply.

Let us say we have an objective function whose coefficients are specified in terms = [(np.random.normal(), spin_pair) for spin_pair in combinations(range(N), r=2)] in your example.

I simply want to have the objective function that can be passed to a minimizer to optimize the parameters gamma and beta.

It is similar to qaoa_obj that is shown in another example https://github.com/jpmorganchase/QOKit/blob/main/examples/QAOA_portfolio_optimization.ipynb where qaoa_obj is obtained by a high-level API get_qaoa_portfolio_objective. I just wonder how to obtain the objective function in the general case if we know the above 'terms'.

[rsln-s]

Thank you for explaining! I added the example you requested here. Let me know if it works for you!

[eegzheng]

@rsln-s, that's excellent and it works well!

BTW, if we have a QUBO in a general form, say, to minimize y = z'Az + b'z, how to encode the problem into the variable 'terms'? If there is only A without b, what I did is to use G = nx.from_numpy_array(A), and then enumerate all edges in A to add items to 'terms', but in this way, I don't know how to add b'z. Could you advise further? Thank you.

[rsln-s]

I believe the QAOA objective should support "single-body" z terms directly. For example, you should be able to pass in something like this with no problem:

terms = [
(-1, [0,1]),
(0.5, [1]),
...
]

Here I'm encoding objective equal to -1*z[0]*z[1] + 0.5*z[1].

Let me know if you see any issues!

[eegzheng]

Single-body z terms work as well, but the optimized results are not what I expected because I know the optimal solution in this case. Does the matrix A need to be represented as an upper triangular matrix in 'terms'?

After solving gamma and beta, is there a way to recover the original binary variables, so that I can check what went wrong? Or can I share a minimum code with you to check?

[eegzheng]

I just give an example below to show the problem. The optimize objective value (even not fully optimized yet) is lower than the brute force one.

import numpy as np import qokit import scipy from qokit.qaoa_objective import get_qaoa_objective from qokit.utils import brute_force

num_nodes=8 terms = [[0.3362264869566366, [0, 0]], [0.25056948398589207, [0, 1]], [0.25056948398589207, [1, 0]], [-0.6724529739132732, [0, 2]], [-0.6724529739132732, [2, 0]], [-0.5011389679717841, [0, 3]], [-0.5011389679717841, [3, 0]], [0.17924810168710348, [0, 5]], [0.17924810168710348, [5, 0]], [-0.35849620337420696, [0, 7]], [-0.35849620337420696, [7, 0]], [1.2528742426345536, [1, 1]], [-0.5011389679717841, [1, 2]], [-0.5011389679717841, [2, 1]], [-2.505748485269107, [1, 3]], [-2.505748485269107, [3, 1]], [-0.17924810168710348, [1, 4]], [-0.17924810168710348, [4, 1]], [0.35849620337420696, [1, 6]], [0.35849620337420696, [6, 1]], [1.3449059478265464, [2, 2]], [1.0022779359435683, [2, 3]], [1.0022779359435683, [3, 2]], [-0.35849620337420696, [2, 5]], [-0.35849620337420696, [5, 2]], [0.7169924067484139, [2, 7]], [0.7169924067484139, [7, 2]], [5.011496970538214, [3, 3]], [0.35849620337420696, [3, 4]], [0.35849620337420696, [4, 3]], [-0.7169924067484139, [3, 6]], [-0.7169924067484139, [6, 3]], [0.3362264869566366, [4, 4]], [0.25056948398589207, [4, 5]], [0.25056948398589207, [5, 4]], [-0.6724529739132732, [4, 6]], [-0.6724529739132732, [6, 4]], [-0.5011389679717841, [4, 7]], [-0.5011389679717841, [7, 4]], [1.2528742426345536, [5, 5]], [-0.5011389679717841, [5, 6]], [-0.5011389679717841, [6, 5]], [-2.505748485269107, [5, 7]], [-2.505748485269107, [7, 5]], [1.3449059478265464, [6, 6]], [1.0022779359435683, [6, 7]], [1.0022779359435683, [7, 6]], [5.011496970538214, [7, 7]], [-1.6256792439756234, [0]], [-3.829944110202449, [1]], [3.2513584879512467, [2]], [7.659888220404898, [3]], [-0.5501906338530025, [4]], [-4.188440313576656, [5]], [1.100381267706005, [6]], [8.376880627153312, [7]]]

print(terms)

p = 8

Compute true optimal solution

def f_from_terms_ground_truth(s): """ground truth for debugging """ out = 0 for coeff, ij in terms: if len(ij)==2: i = ij[0] j=ij[1] out += coeff s[i] s[j] else: out += coeff * s[ij]
return out

optimal_obj = brute_force(f_from_terms_ground_truth, num_nodes, minimize=True)[0] optimal_var = brute_force(f_from_terms_ground_truth, num_nodes, minimize=True)[1] print('Brute force minimum: ', optimal_obj) # minimum is -6.01377491 print('Brute force optimal solution: ', optimal_var)

f = get_qaoa_objective(num_nodes, p, terms=terms, parameterization='theta') initial_gamma = -np.linspace(0, 1, p) initial_beta = np.linspace(1, 0, p)

res = scipy.optimize.minimize(f, np.hstack([initial_gamma, initial_beta]), method='COBYLA', options={'rhobeg':0.01,"maxiter": 10000}) print(res)
print(f"Approximation objective after optimization: {f(res.x)}") # Got -24.14, even lower than the above brute force optimal_obj?

[eegzheng]

It seems the QAOA objective does not support "single-body" z terms well. In your example, https://github.com/jpmorganchase/QOKit/blob/b4e46230ba2672a42f8647356a8e27538353dbcc/examples/QAOA_objective_for_general_Hamiltonian.ipynb, if I add single-body z to terms like below, QAOA cannot get close-to-optimal solution (there is a clear gap) even I increase the value of p. Could you help look at it again?

for node in range(N): weight = np.random.normal() temp = [weight,([node])] terms.append(temp)

[rsln-s]

@eegzheng – this indeed appears to be an issue with the single body terms support! Thank you for pointing it out. We will look into it.