arXiv:0809.2445

Finding conjugate stabilizer subgroups in PSL(2; q) and related groups

Aaron Denney, Cristopher Moore, Alexander C. Russell

Published Sep 15, 2008• 1 citation

Abstract

We reduce a case of the hidden subgroup problem (HSP) in SL(2; q), PSL(2; q), and PGL(2; q), three related families of finite groups of Lie type, to efficiently solvable HSPs in the affine group AGL(1; q). These groups act on projective space in an almost 3-transitive way, and we use this fact in each group to distinguish conjugates of its Borel (upper triangular) subgroup, which is also the stabilizer subgroup of an element of projective space. Our observation is mainly group-theoretic, and as such breaks little new ground in quantum algorithms. Nonetheless, these appear to be the first positive results on the HSP in finite simple groups such as PSL(2; q).

DOI: 10.48550/arxiv.0809.2445

Related papers

Finding conjugate stabilizer subgroups in $\PSL$ and related groups

Aaron Denney, Cristopher Moore, Alexander C. Russell

Quantum Information and ComputationMar 1, 20107 citations

Finding hidden Borel subgroups of the general linear group

Gábor Ivanyos

We present a quantum algorithm for solving the hidden subgroup problem in the general linear group over a finite field where the hidden subgroup is promised to be a conjugate of the group of the invertible lower triangular matrices. The complexity of the algorithm is polynomial when size of the base field is not much smaller than the degree.

Quantum Information and ComputationJul 1, 20124 citations

Finding hidden Borel subgroups of the general linear group

Gábor Ivanyos

arXiv:1105.4416May 23, 20110 citations

The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups

Mauro E. S. Morales

quant-pharXiv:2608.05321Aug 7, 20260 citations

Hidden subgroup problem in quantum computing

Shuhong Gao, Prasit Limbupasiriporn

Jan 1, 20050 citations

Finding hidden Borel subgroups of the general linear group

IvanyosGábor

Quantum Information and ComputationJul 1, 20120 citations

arXiv:0809.2445

Finding conjugate stabilizer subgroups in PSL(2; q) and related groups

Aaron Denney, Cristopher Moore, Alexander C. Russell

Published Sep 15, 2008• 1 citation

arXiv HTML PDF

Abstract

DOI: 10.48550/arxiv.0809.2445

Related papers

Finding conjugate stabilizer subgroups in $\PSL$ and related groups

Aaron Denney, Cristopher Moore, Alexander C. Russell

We reduce a case of the hidden subgroup problem (HSP) in $\SL$, $\PSL$, and $\PGL$, three related families of finite groups of Lie type, to efficiently solvable HSPs in the affine group $\AGL$. These groups act on projective space in an ``almost'' 3-transitive way, and we use this fact in each group to distinguish conjugates of its Borel (upper triangular) subgroup, which is also the stabilizer subgroup of an element of projective space. Our observation is mainly group-theoretic, and as such breaks little new ground in quantum algorithms. Nonetheless, these appear to be the first positive results on the HSP in finite simple groups such as $\PSL$.We reduce a case of the hidden subgroup problem (HSP) in $\SL$, $\PSL$, and $\PGL$, three related families of finite groups of Lie type, to efficiently solvable HSPs in the affine group $\AGL$. These groups act on projective space in an ``almost'' 3-transitive way, and we use this fact in each group to distinguish conjugates of its Borel (upper triangular) subgroup, which is also the stabilizer subgroup of an element of projective space. Our observation is mainly group-theoretic, and as such breaks little new ground in quantum algorithms. Nonetheless, these appear to be the first positive results on the HSP in finite simple groups such as $\PSL$.

Quantum Information and ComputationMar 1, 20107 citations

Finding hidden Borel subgroups of the general linear group

Gábor Ivanyos

Quantum Information and ComputationJul 1, 20124 citations

Finding hidden Borel subgroups of the general linear group

Gábor Ivanyos

arXiv:1105.4416May 23, 20110 citations

The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups

Mauro E. S. Morales

Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively. In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form $G=A\rtimes_{\varphi} \mathbb{Z}_{p^k}$ , with $A$ finite Abelian, $p$ prime, $k\in \mathbb{N}$ and the action of $\mathbb Z_{p^k}$ is generated by the scalar automorphism $a\mapstoμa$ , for some $μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times$ , where $\mathrm{Exp}(A)$ is the exponent of $A$ . Our algorithm is efficient when $A$ has bounded generator rank and $\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)$ . This includes the case $A=\mathbb{Z}_N$ for $N\in\mathbb{N}$ and $k=1$ , studied by Bacon, Childs and van Dam (FOCS 2005), and $A=\mathbb{Z}_{q^r}$ with $q$ prime and $r\in \mathbb{N}$ studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively. In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form $G=A\rtimes_{\varphi} \mathbb{Z}_{p^k}$, with $A$ finite Abelian, $p$ prime, $k\in \mathbb{N}$ and the action of $\mathbb Z_{p^k}$ is generated by the scalar automorphism $a\mapstoμa$, for some $μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times$, where $\mathrm{Exp}(A)$ is the exponent of $A$. Our algorithm is efficient when $A$ has bounded generator rank and $\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)$. This includes the case $A=\mathbb{Z}_N$ for $N\in\mathbb{N}$ and $k=1$, studied by Bacon, Childs and van Dam (FOCS 2005), and $A=\mathbb{Z}_{q^r}$ with $q$ prime and $r\in \mathbb{N}$ studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).

quant-pharXiv:2608.05321Aug 7, 20260 citations

Hidden subgroup problem in quantum computing

Shuhong Gao, Prasit Limbupasiriporn

We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups. We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture. For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem. In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups. We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture. For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem. In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.

Jan 1, 20050 citations

Finding hidden Borel subgroups of the general linear group

IvanyosGábor

Quantum Information and ComputationJul 1, 20120 citations

G=A\rtimes_{\varphi} \mathbb{Z}_{p^k}

, with

A

finite Abelian,

p

prime,

k\in \mathbb{N}

and the action of

\mathbb Z_{p^k}

is generated by the scalar automorphism

a\mapstoμa

, for some

μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times

, where

\mathrm{Exp}(A)

is the exponent of

A

. Our algorithm is efficient when

A

has bounded generator rank and

\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)

. This includes the case

A=\mathbb{Z}_N

for

N\in\mathbb{N}

and

k=1

, studied by Bacon, Childs and van Dam (FOCS 2005), and

A=\mathbb{Z}_{q^r}

with

q

prime and

r\in \mathbb{N}

studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).