  We present quantum complexity lower and upper bounds for independent set
problems in graphs. In particular, we give quantum algorithms for computing a
maximal and a maximum independent set in a graph. We present applications of
these algorithms for some graph problems. Our results improve the best
classical complexity bounds for the corresponding problems.
