The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems

V. Arvind, Rainer Schuler

We first give an $Ø(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$ inequali…