Knapsack problem with Qiskit¶

There, we will use thge example from Qiskit Knapsack.

In [38]:

from qiskit_optimization.applications import Knapsack

from qiskit_optimization.applications import Knapsack

Here, we first set our problem to have [3,4,5,6,7] coefficient of our variables, then set the variable weights as [2,3,4,5,6], following by the max_weight of 10.

In [48]:

# Setup our Knapsack problem
prob = Knapsack(values=[3,4,5,6,7], weights = [2,3,4,5,6], max_weight=10)
qp = prob.to_quadratic_program()
print(qp.prettyprint())

# Setup our Knapsack problem prob = Knapsack(values=[3,4,5,6,7], weights = [2,3,4,5,6], max_weight=10) qp = prob.to_quadratic_program() print(qp.prettyprint())

Problem name: Knapsack

Maximize
  3*x_0 + 4*x_1 + 5*x_2 + 6*x_3 + 7*x_4

Subject to
  Linear constraints (1)
    2*x_0 + 3*x_1 + 4*x_2 + 5*x_3 + 6*x_4 <= 10  'c0'

  Binary variables (5)
    x_0 x_1 x_2 x_3 x_4

In [49]:

# Using Numpy Eignesolver 
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit_algorithms import NumPyMinimumEigensolver

# Using Numpy Eignesolver from qiskit_optimization.algorithms import MinimumEigenOptimizer from qiskit_algorithms import NumPyMinimumEigensolver

In [50]:

meo = MinimumEigenOptimizer(min_eigen_solver = NumPyMinimumEigensolver())
result = meo.solve(qp)
print(result.prettyprint())
print("\n solution:", prob.interpret(result))
#TODO We can apply constraints that at least 1.

meo = MinimumEigenOptimizer(min_eigen_solver = NumPyMinimumEigensolver()) result = meo.solve(qp) print(result.prettyprint()) print("\n solution:", prob.interpret(result)) #TODO We can apply constraints that at least 1.

objective function value: 13.0
variable values: x_0=1.0, x_1=1.0, x_2=0.0, x_3=1.0, x_4=0.0
status: SUCCESS

 solution: [0, 1, 3]

1. An objective function value of says that we have a maximum value of 13.
2. The variable values means that we can have 1 of x_0, x_1, and x_3 each.
3. solution indices give states that the indices of x_0, x_1, and x_3 are the solution.

Checking Hamiltonian

In [51]:

from qiskit_optimization.converters import QuadraticProgramToQubo

from qiskit_optimization.converters import QuadraticProgramToQubo

In [52]:

# intermediate QUBO form of the optimization problem
conv = QuadraticProgramToQubo()
qubo = conv.convert(qp)
print(qubo.prettyprint())

# intermediate QUBO form of the optimization problem conv = QuadraticProgramToQubo() qubo = conv.convert(qp) print(qubo.prettyprint())

Problem name: Knapsack

Minimize
  26*c0@int_slack@0^2 + 104*c0@int_slack@0*c0@int_slack@1
  + 208*c0@int_slack@0*c0@int_slack@2 + 156*c0@int_slack@0*c0@int_slack@3
  + 104*c0@int_slack@1^2 + 416*c0@int_slack@1*c0@int_slack@2
  + 312*c0@int_slack@1*c0@int_slack@3 + 416*c0@int_slack@2^2
  + 624*c0@int_slack@2*c0@int_slack@3 + 234*c0@int_slack@3^2
  + 104*x_0*c0@int_slack@0 + 208*x_0*c0@int_slack@1 + 416*x_0*c0@int_slack@2
  + 312*x_0*c0@int_slack@3 + 104*x_0^2 + 312*x_0*x_1 + 416*x_0*x_2 + 520*x_0*x_3
  + 624*x_0*x_4 + 156*x_1*c0@int_slack@0 + 312*x_1*c0@int_slack@1
  + 624*x_1*c0@int_slack@2 + 468*x_1*c0@int_slack@3 + 234*x_1^2 + 624*x_1*x_2
  + 780*x_1*x_3 + 936*x_1*x_4 + 208*x_2*c0@int_slack@0 + 416*x_2*c0@int_slack@1
  + 832*x_2*c0@int_slack@2 + 624*x_2*c0@int_slack@3 + 416*x_2^2 + 1040*x_2*x_3
  + 1248*x_2*x_4 + 260*x_3*c0@int_slack@0 + 520*x_3*c0@int_slack@1
  + 1040*x_3*c0@int_slack@2 + 780*x_3*c0@int_slack@3 + 650*x_3^2 + 1560*x_3*x_4
  + 312*x_4*c0@int_slack@0 + 624*x_4*c0@int_slack@1 + 1248*x_4*c0@int_slack@2
  + 936*x_4*c0@int_slack@3 + 936*x_4^2 - 520*c0@int_slack@0
  - 1040*c0@int_slack@1 - 2080*c0@int_slack@2 - 1560*c0@int_slack@3 - 1043*x_0
  - 1564*x_1 - 2085*x_2 - 2606*x_3 - 3127*x_4 + 2600

Subject to
  No constraints

  Binary variables (9)
    x_0 x_1 x_2 x_3 x_4 c0@int_slack@0 c0@int_slack@1 c0@int_slack@2
    c0@int_slack@3

In [53]:

# qubit Hamiltonian and offset
op, offset = qubo.to_ising()
print(f"num qubits:{op.num_qubits}, offset:{offset}\n")
print(op)

# qubit Hamiltonian and offset op, offset = qubo.to_ising() print(f"num qubits:{op.num_qubits}, offset:{offset}\n") print(op)

num qubits:9, offset:1417.5

SparsePauliOp(['IIIIIIIIZ', 'IIIIIIIZI', 'IIIIIIZII', 'IIIIIZIII', 'IIIIZIIII', 'IIIZIIIII', 'IIZIIIIII', 'IZIIIIIII', 'ZIIIIIIII', 'IIIIIIIZZ', 'IIIIIIZIZ', 'IIIIIZIIZ', 'IIIIZIIIZ', 'IIIZIIIIZ', 'IIZIIIIIZ', 'IZIIIIIIZ', 'ZIIIIIIIZ', 'IIIIIIZZI', 'IIIIIZIZI', 'IIIIZIIZI', 'IIIZIIIZI', 'IIZIIIIZI', 'IZIIIIIZI', 'ZIIIIIIZI', 'IIIIIZZII', 'IIIIZIZII', 'IIIZIIZII', 'IIZIIIZII', 'IZIIIIZII', 'ZIIIIIZII', 'IIIIZZIII', 'IIIZIZIII', 'IIZIIZIII', 'IZIIIZIII', 'ZIIIIZIII', 'IIIZZIIII', 'IIZIZIIII', 'IZIIZIIII', 'ZIIIZIIII', 'IIZZIIIII', 'IZIZIIIII', 'ZIIZIIIII', 'IZZIIIIII', 'ZIZIIIIII', 'ZZIIIIIII'],
              coeffs=[-258.5+0.j, -388. +0.j, -517.5+0.j, -647. +0.j, -776.5+0.j, -130. +0.j,
 -260. +0.j, -520. +0.j, -390. +0.j,   78. +0.j,  104. +0.j,  130. +0.j,
  156. +0.j,   26. +0.j,   52. +0.j,  104. +0.j,   78. +0.j,  156. +0.j,
  195. +0.j,  234. +0.j,   39. +0.j,   78. +0.j,  156. +0.j,  117. +0.j,
  260. +0.j,  312. +0.j,   52. +0.j,  104. +0.j,  208. +0.j,  156. +0.j,
  390. +0.j,   65. +0.j,  130. +0.j,  260. +0.j,  195. +0.j,   78. +0.j,
  156. +0.j,  312. +0.j,  234. +0.j,   26. +0.j,   52. +0.j,   39. +0.j,
  104. +0.j,   78. +0.j,  156. +0.j])