  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$.
