Implement the 0/1 knapsack problem using a VQE

[sorin-bolos]

Abstract

Implement the "0/1 knapsack problem" using VQE/QAOA. The challenge is to find the Hamiltonian that encodes the problem to use in the VQE algorithm.

Description

The 0/1 knapsack problem: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. We need to define the problem mathematically and find a Hamiltonian for which the ground state is the solution to this problem. Aqua already contains implementations of optimization problems like Max Cut and Traveling Salesman Problem. We can add this implementation too.

Members

@dongsin-kim @sorin-bolos @R07222062 @ylchen0918

• Qiskit Coach: @a-matsuo

Deliverable

A jupyter notebook containing the implementation of the cost function expressed as a list of Pauli terms

GitHub repo

https://github.com/sorin-bolos/QiskitCampAsia2019

[dongsin-kim]

I'm interested in the issue-! :-)

[R07222062]

I'd like to participate in this project.

[ylchen0918]

Interesting

[sorin-bolos]

Presentation https://github.com/sorin-bolos/QiskitCampAsia2019/blob/master/knapsack_%2339_FINAL.pdf