The Quantum Query Complexity Of 0-1 Knapsack And Associated Claw Problems

Abstract

We first give an $\text{O}(2^{\{}n/3\})$ quantum algorithm for the 0-1 Knapsack problem with $n$ variables. More generally, for 0-1 Integer Linear Programs with $n$ variables and $d$ inequalities we give an $\text{O}(2^{\{}n/3\}{n}^d)$ quantum algorithm. For $d=o(n/logn)$ this running time is bounded by $\text{O}(2^{\{}n(1/3+ϵ)\})$ for every $ϵ>0$ and in particular it is better than the $\text{O}(2^{\{}n/2\})$ upper bound for general quantum search. To investigate whether better algorithms for these NP-hard problems are possible, we formulate a *symmetric* claw problem corresponding to 0-1 Knapsack and study its quantum query complexity. For the symmetric claw problem we establish a lower bound of $\text{O}(2^{\{}n/4\})$ for its quantum query complexity. We have an $\text{O}(2^{\{}n/3\})$ upper bound given by essentially the same quantum algorithm that works for Knapsack. Additionally, we consider CNF satisfiability of CNF formulas $F$ with no restrictions on clause size, but with the number of