We introduce two decision problems, STABILIZERD and TRANSLATING COSETD, and give quantum reductions from them to the problem ORBIT SUPERPOSITION, as well as quantum reductions to them from two group theoretic problems GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP. Based on these reductions, efficient quantum algorithms are obtained for GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP in the setting of black-box groups. Specifically, for solvable groups, this gives efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also show that GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP are in the complexity class SZK.
We introduce two decision problems, STABILIZERD and TRANSLATING COSETD, and give quantum reductions from them to the problem ORBIT SUPERPOSITION, as well as quantum reductions to them from two group theoretic problems GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP. Based on these reductions, efficient quantum algorithms are obtained for GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP in the setting of black-box groups. Specifically, for solvable groups, this gives efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also show that GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP are in the complexity class SZK.
We study two group theoretic problems, GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, in the setting of black-box groups, where DOUBLE COSET MEMBERSHIP generalizes a set of problems, including GROUP MEMBERSHIP, GROUP FACTORIZATION, and COSET INTERSECTION. No polynomial-time classical algorithms are known for these problems. We show that for solvable groups, there exist efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also study the decision versions of STABILIZER and ORBIT COSET, which generalizes GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, respectively. We show that they reduce to ORBIT COSET under certain conditions. Finally, we show that DOUBLE COSET MEMBERSHIP and DOUBLE COSET NONMEMBERSHIP have zero knowledge proof systems.
In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. Several other problems, such as testing membership in solvable groups, testing equality of subgroups in a given solvable group, and testing normality of a subgroup in a given solvable group, reduce to computing orders of solvable groups and therefore admit polynomial-time quantum algorithms as well. Our algorithm works in the setting of black-box groups, wherein none of these problems can be computed classically in polynomial time. As an important byproduct, our algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which yields a natural way to apply existing quantum algorithms to factor groups of solvable groups.
We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z pn, whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup, and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N, for any solvable normal subgroup N of G.
In this paper, we present a polynomial-time quantum algorithm for computing a minimum-sized generating set of solvable black-box groups. Next, we consider the class Γd of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group Sd for a fixed d. We design polynomial-time quantum algorithms to compute the direct product decomposition of abelian factor groups and solve the constructive membership problem for factor groups of groups from Γd. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from Γd. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from Γd. Finally, we show that the minimum generating set problem for general black-box groups is in NP∩coAM.
We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z pn, whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup, and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N, for any solvable normal subgroup N of G.
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 e and δ. 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.