search

qiskit-community / qiskit-camp-asia-19

31 stars 7 forks source link

Implement the 0/1 knapsack problem using a VQE #39

Open sorin-bolos opened 4 years ago

sorin-bolos commented 4 years ago

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

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 commented 4 years ago

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

R07222062 commented 4 years ago

I'd like to participate in this project.

ylchen0918 commented 4 years ago

Interesting

sorin-bolos commented 4 years ago

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