© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:quant-ph/0011023 · ACM Symposium on Theory of Computing (STOC)

Quantum algorithms for solvable groups

John Watrous

Published Jul 6, 2001• 86 citations

Abstract

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.

DOI: 10.1145/380752.380759

Related papers

Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem

Gábor Ivanyos, Frédéric Magniez, Miklós Sántha

In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.

ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)•Jul 3, 2001•30 citations

Quantum algorithms for a set of group theoretic problems

Stephen Fenner, Yong Zhang

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.

arXiv:quant-ph/0408150•Aug 24, 2004•1 citation

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

Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem

Gábor Ivanyos, Frédéric Magniez, Miklós Sántha

In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.

arXiv:quant-ph/0102014•Feb 2, 2001•2 citations

An exact quantum hidden subgroup algorithm and applications to solvable groups

Muhammad Imran, Gábor Ivanyos

We present a polynomial time exact quantum algorithm for the hidden subgroup problem in $\Z_{m^k}^n$. The algorithm uses the quantum Fourier transform modulo $m$ and does not require factorization of $m$. For smooth $m$, i.e., when the prime factors of $m$ are of size $(\log m)^{O(1)}$, the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general $m$, the algorithm of Mosca and Zalka is available. Even for $m=3$ and $k=1$ our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as $m$. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.

arXiv:2202.04047•Quantum Information and Computation•May 30, 2022•1 citation

EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM

Gábor Ivanyos, Frédéric Magniez, Miklós Sántha

In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.

International Journal of Foundations of Computer Science•Oct 1, 2003•76 citations

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 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 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}

.

We present a polynomial time exact quantum algorithm for the hidden subgroup problem in

\Z_{m^k}^n

. The algorithm uses the quantum Fourier transform modulo

m

and does not require factorization of

m

. For smooth

m

, i.e., when the prime factors of

m

are of size

(\log m)^{O(1)}

, the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general

m

, the algorithm of Mosca and Zalka is available. Even for

m=3

and

k=1

our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as

m

. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.