An illustration of adiabatic quantum computation: solution of the knapsack problem

The knapsack problem is one of the standard and important difficult challenges for computer science, having broad applications in financial transactions and packing and stock-cutting contexts. As an optimization problem, the main idea is to maximize benefit (profit) subject to weight (cost) constraints. Moreover, solutions of this problem may serve as a facilitator for resolving more complicated problems, including scheduling. This presentation reviews this problem, and briefly its applications, before discussing how a version of quantum computing could be implemented for its solution. This alternative methodology of quantum computing uses systems which have been widely used to model magnetic and other phenomena. It is mentioned that a commercial claimed quantum computing architecture for such problems is available. The aspect of easy- versus difficult-problem instances for NP-hard problems such as knapsack and its subproblem subset sum may also be touched upon.