Physics – Quantum Physics
Scientific paper
2002-12-09
Physics
Quantum Physics
10 pages
Scientific paper
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$.
Arvind Vikraman
Schuler Rainer
No associations
LandOfFree
The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-488971