2002/12/09 by V. Arvind, Arvind, V., Rainer Schuler +1
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.quant-ph/0212048
We first give an Ø(2n/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 Ø(2n/3nd) quantum algorithm. For d =o(n/log n) this running time is bounded by Ø(2n(1/3+ε)) for every ε>0 and in particular it is better than the Ø(2n/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 Ø(2n/4) for its quantum query complexity. We have an Ø(2n/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-α)n/2 quantum algorithm for satisfiability in this case, where α is a constant depending on c.