Skip to content
This repository has been archived by the owner on Aug 21, 2024. It is now read-only.

Latest commit

 

History

History

BoundedKnapsack

Welcome!

The "BoundedKnapsack" quantum kata is a series of exercises designed to teach you to use Grover's search algorithm to solve the knapsack problem - a prominent computational problem that is very applicable in industries like e-commerce. The overall goal in this kata is to solve the knapsack optimization problem by running Grover's algorithm. You will implement oracles that implement various parts of the knapsack problem, and use these oracles with Grover's algorithm to solve the problem.

  • More information on the knapsack problem can be found on Wikipedia.
  • It is strongly recommended to complete the Grover's Algorithm kata before proceeding to this one. You can also refer to its README for the list of resources on Grover's algorithm.
  • You may find this kata to be more challenging than other Grover search katas, so you might want to complete SolveSATWithGrover or GraphColoring first.
  • Much of the reference implementation provided in this kata is based on the circuits described in the paper "Quantum-based algorithm and circuit design for bounded knapsack optimization problem" by Wenjun Hou and Marek Perkowski in the journal Quantum Information and Computation.