0-1 Knapsack Problem
Summary
The purpose of this article is to analyze the 0/1 Knapsack Problem and explore possible quantum algorithms for its computation on a quantum computer. The Knapsack problem is an interesting computer science problem where one has to maximize the total value of items in a knapsack of known capacity when given a list of items to select from. This article shows that a modified Grover’s search algorithm and the Quantum approximate optimization algorithm (QAOA) that can be used in exploring the creation a Quantum algorithm for the 0/1 Knapsack Problem.
Introduction
The rise in the popularity of Quantum computers and the success of Grover’s algorithm [1] for sorting and Shor’s algorithm [2] for factorization has raised questions on whether Quantum computing will bring forth solutions to other classically hard problems like combinatorics. However, scientists do not believe that quantum computing will be able to solve NP-Hard problems [3] but will be able to speed up operations involving searching [4]. The 0 1 Knapsack Problem is an optimization problem, which seeks the best solution from among many other solutions. It is an NP-complete problem and will be NP-hard in a Quantum computer [3]. However, Quantum computers have the capacity to improve time complexity.
Problem definition
The problem definition is: Given a knapsack and a set of N objects, each (i, i ∈ N) having a weight Wi and associated profit Pi, maximize (in profit) the set of items that are added to the knapsack. The knapsack has a maximum capacity of V and the maximized set must be less or equal to V. When an item is picked, it has a value 1 in the knapsack and 0 when it is not.
Brief Review
The typical structure of a quantum algorithm is as follows. The first part of the algorithm is to make an equal superposition of all 2^n states by applying Hadamard gates [5]. The second part is to encode the problem into states, perform gate logic, and put phases on all 2^n states [5]. The last part is to minimally superpose (interfere) all these states back to a few outcomes for measurement [5].
Quantum parallelism arises from superposition. A function performed once on the register in a superposition of states is performed on each of the components of the superposition [6].
Previous work
Schuler and Arvind [7] put forth an ~O(2^n/3 ) quantum algorithm for the 0-1 Knapsack problem with n variables using a generalization from Integer Linear Programs. The algorithm includes Grover’s search algorithm and the powerful method of amplitude amplification [7]. This algorithm defines a unitary transformation for a subroutine that is used to calculate the value of combinations for the knapsack. These values are then used in a modified Grover’s search. The various combinations are then sent to the Grover operator as a function which is equal to 1 when it is the optimal solution [7].
Proposed 0 1 Knapsack Algorithms
Modified Grover's algorithm
Following closely the work of [5], These are the steps for our proposed algorithm 1. Using N qubits, each basis state will represent a possible set. {|00000>,|00001> …|11111>} 2. Two prepared state vectors will represent the profit and weight vectors. 3. Inner product will be used to calculate the profit and weight of each possible solution set. 4. Sets with weights > V will be eliminated. 5. A modified Grover’s search is then applied to the remaining sets, using the profit value calculated in step 3.
Quantum parallelism and the efficiency of Grover’s algorithm will definitely give a speedup for this problem (Step 1-3 can be done simultaneously), however, we theorize that gate complexity for the functions necessary for implementing steps 2 and 3 will be exponentially large depending on the value of N. The time complexity of this algorithm is speculated to be about ~O(2^ (n/3)+n ).
The Quantum approximate optimization algorithm (QAOA)
Conclusion
The Modified Grover’s algorithm and the QAOA are two potential Quantum algorithms for the 0 1 Knapsack problem. Future work on this topic should involve in-depth algorithm analysis and circuit construction. This is my last article for the term, and I want to especially thank Professor. Parimala Thulasiraman for her guidance.
References
[1] Grover, L. K. (1996, July). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212-219).
[2] Ekert, A., & Jozsa, R. (1996). Quantum computation and Shor's factoring algorithm. Reviews of Modern Physics, 68(3), 733.
[3] Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. Quantum, 2, 79.
[4] Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack. Physical review letters, 79(2), 325.
[5] https://www.siam.org/conferences/cm/program/minitutorials/pp20- minitutorials
[6] https://quantum-algorithms.herokuapp.com/433/shor-par/node11.html