Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0408150

Quantum algorithms for a set of group theoretic problems

Stephen Fenner, Yong Zhang

Published Aug 24, 2004• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0408150

Related papers

Quantum Algorithms for a Set of Group Theoretic Problems

Stephen Fenner, Yong Zhang

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.

International Journal of Foundations of Computer Science•Feb 1, 2015•2 citations

Quantum algorithms for solvable groups

John Watrous

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.

arXiv:quant-ph/0011023•ACM Symposium on Theory of Computing (STOC)•Jul 6, 2001•86 citations

Quantum Algorithms for Minimum Generating Set

Bireswar Das, Udit Kumar, Kavita Samant +1 more

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 $S_d$ 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 $\textrm{NP} \cap \textrm{coAM}$.

quant-pharXiv:2609.40260•Oct 1, 2026•0 citations

Quantum circuits and quantum algorithms

Yong Zhang, Stephen Fenner

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.

•Jan 1, 2005•0 citations

Hidden translation and orbit coset in quantum computing

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez +2 more

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.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2003•8 citations

Hidden translation and orbit coset in quantum computing

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez +2 more

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.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•133 citations
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.
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.
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.
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Γ_dΓd​ of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group SdS_dSd​ for a fixed ddd. 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Γ_dΓd​. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from ΓdΓ_dΓd​. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from ΓdΓ_dΓd​. Finally, we show that the minimum generating set problem for general black-box groups is in NP∩coAM\textrm{NP} \cap \textrm{coAM}NP∩coAM.
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.
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.
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.