Quantum Algorithm & Circuit Design for Bounded Knapsack Optimization Problem

Presented by Wenjun Hou, Jesuit High School / Portland State University

The Knapsack Problem is a prominent problem that is used in resource allocation and cryptography. Wenjun's project presents an oracle and a circuit design that verifies solutions to the decision problem form of the Bounded Knapsack Problem. This oracle can be used by Grover Search to solve the optimization problem form of the Bounded Knapsack Problem. This algorithm leverages the quadratic speed-up offered by Grover Search to achieve a quantum algorithm for the Knapsack Problem that shows improvement with regard to classical algorithms. The quantum circuits were designed using the Microsoft Q# Programming Language and verified on its local quantum simulator. The project also provides analyses of the complexity and gate cost of the proposed oracle. The work in this project is the first such proposed method for the Knapsack Optimization Problem.