{ "id": "quant-ph/0212048", "version": "v1", "published": "2002-12-09T05:05:58.000Z", "updated": "2002-12-09T05:05:58.000Z", "title": "The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems", "authors": [ "V. Arvind", "Rainer Schuler" ], "comment": "10 pages", "categories": [ "quant-ph" ], "abstract": "We first give an $\\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 $\\O(2^{n/3}n^d)$ quantum algorithm. For $d =o(n/\\log n)$ this running time is bounded by $\\O(2^{n(1/3+\\epsilon)})$ for every $\\epsilon>0$ and in particular it is better than the $\\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 \\emph{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 $\\O(2^{n/4})$ for its quantum query complexity. We have an $\\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 clauses in $F$ bounded by $cn$ for a constant $c$, where $n$ is the number of variables. We give a $2^{(1-\\alpha)n/2}$ quantum algorithm for satisfiability in this case, where $\\alpha$ is a constant depending on $c$.", "revisions": [ { "version": "v1", "updated": "2002-12-09T05:05:58.000Z" } ], "analyses": { "keywords": [ "quantum query complexity", "associated claw problems", "quantum algorithm", "upper bound", "integer linear programs" ], "note": { "typesetting": "TeX", "pages": 10, "language": "en", "license": "arXiv", "status": "editable", "adsabs": "2002quant.ph.12048A" } } }