0
$\begingroup$

Say I want to fill a knapsack with as many things as possible. I don't care about what they are, simply the number. But I don't want the total weight to exceed a set limit.

[https://qiskit.org/textbook/ch-applications/qaoa.html#1.-Constructing-Problem-Hamiltonian-]

  1. Would my cost function be a weighted average of the total weight of a set and the number?
  2. Would S be the set of weights?
  3. Would the number of required qubits be log_2(max(S))?

Thanks

$\endgroup$

1 Answer 1

1
$\begingroup$

The goal of the knapsack problem is to pick items such that the total value of the knapsack is maximized subject to the knapsack weight constraint. This already implies that your cost function has nothing to do with weights but values of each individual item.

I suggest first reading Wikipedia or some other resources before posting such questions.

Since your questions (1) and (2) are clearly explained and illustrated with pictures on Wikipedia, I will not bother answering that.

As for your question (3), if you read the Wikipedia page, you will immediately see that the knapsack constraint is an inequality constraint. This means you will need extra qubits to incorporate it into a Hamiltonian as a penalty term.

The short answer is that you need about $n + \log_2(W) + 1$ qubits, in general. Here, $n$ is the number of variables (knapsack items), and $W$ is the constraint bound.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.