Quantum circuits and quantum algorithms

In the dissertation we study topics in quantum computation. First, we study the model of constant-depth quantum circuits. We study the family QNC0 of constant-depth quantum circuits, and the complexity classes associated with QNC0 circuits: EQNC0, NQNC0, and BQNC0e,d . We show certain containment results such as NQNC 0 = NQACC = NQP = coC =P and BQNC0e,d is in P for certain epsilon and delta. Our results essentially refute a conjecture of Green et al. that NQACC ⊆ TC0. We also define and study complexity classes postEQP, postRQP, postNQP, and postBQNC0 We show containment results such as postBQNC0 = postBQP = PP and NQP = postRQP = postNQP.; Second, we study applications of quantum algorithms in computational group theory. We give results about quantum algorithms and reductions for group theoretic problems, concentrating mostly on solvable groups. We study two particular group theoretic problems---GROUP I NTERSECTION and DOUBLE COSET M EMBERSHIP. We show that these problems reduce to other group problems with known efficient quantum algorithms for many instances, yielding efficient quantum algorithms for GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP on the same types of groups. Then we generalize and refine our results by introducing decision versions of the STABILIZER and ORBIT COSET problems, and showing that these new problems lie in between GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP on the one hand, and the problem ORBIT SUPERPOSITION, on the other. We also show that GROUP INTERSECTION and D OUBLE COSET MEMBERSHIP have statistical zero knowledge proofs. Finally we give an alternative quantum algorithm for the problem of decomposing finite abelian groups.