Quantum algorithm analysis of knapsack problem

Hongying Liu, Shuzhi Nie

Huy Phuc Nguyen Ha, Viết Hùng Nguyễn, Anh Son Ta

Kampa Lavanya, T. Surekha, J. David Sukeerthi Kumar +2 more

Abhishek Awasthi, Francesco Bär, Joseph A. Doetsch +16 more

K. A. Stepanenko

Abstract The knapsack problem is an important example of a combinatorial optimization problem with a wide range of applications in direct practical applications. In this article, the author considers the classical version of the problem (0-1 knapsack) and proposes a quantum algorithm for solving it based on a hybrid approach that combines the Grover quantum search algorithm with the procedure for finding the Durr–Hoyer minimum. The paper presents an analysis of the computational complexity of the proposed algorithm, and in addition to theoretical analysis, the article contains an explicit description of the quantum circuit implementing the proposed algorithm.

Xiang-Qun Fu, Wan‐Su Bao, Jianhong Shi +2 more

In order to research the security of the knapsack problem under quantum algorithm attack, we study the quantum algorithm for knapsack problem over Z_r based on the relation between the dimension of the knapsack vector and r. First, the oracle function is designed based on the knapsack vector B and S, and the quantum algorithm for the knapsack problem over Z_r is presented. The observation probability of target state is not improved by designing unitary transform, but oracle function. Its complexity is polynomial. And its success probability depends on the relation between n and r. From the above discussion, we give the essential condition for the knapsack problem over Z_r against the existing quantum algorithm attacks, i.e. r