arXiv:2202.09697

A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem

Moore, Matthew, Young, Grace

Published Feb 19, 2022• 0 citations

Abstract

We present a polynomial-time quantum algorithm for the Hidden Subgroup Problem over $\mathbb{D}_{2^n}$. The usual approach to the Hidden Subgroup Problem relies on harmonic analysis in the domain of the problem, and the best known algorithm using this approach has time complexity in $2^{\mathcal{O}(\sqrt{n})}$. By focusing on structure encoded in the codomain of the problem, we develop a polynomial-time algorithm which uses this structure to direct a "walk" down the subgroup lattice of $\mathbb{D}_{2^n}$ terminating at the hidden subgroup.

DOI: 10.48550/arxiv.2202.09697

Related papers

Dihedral Hidden Subgroup Problem: A Survey

Hirotada Kobayashi, François Le Gall

IPSJ Digital CourierJan 1, 20057 citations

A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Greg Kuperberg

arXiv:quant-ph/0302112SIAM Journal on ComputingJan 1, 2005347 citations

Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups

Demerson Nunes Gonçalves, Renato Portugal

arXiv:1104.1361Apr 7, 20113 citations

Polynomial-time quantum algorithm for solving the hidden subgroup problem

Hefeng Wang

arXiv:2204.03295Apr 7, 20220 citations

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

Mauro E. S. Morales

quant-pharXiv:2608.05321Aug 7, 20260 citations

ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM

Stephen Fenner, Yong Zhang

International Journal of Foundations of Computer ScienceDec 1, 20132 citations

arXiv:2202.09697

A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem

Moore, Matthew, Young, Grace

Published Feb 19, 2022• 0 citations

arXiv HTML PDF

Abstract

We present a polynomial-time quantum algorithm for the Hidden Subgroup Problem over

\mathbb{D}_{2^n}

. The usual approach to the Hidden Subgroup Problem relies on harmonic analysis in the domain of the problem, and the best known algorithm using this approach has time complexity in

2^{\mathcal{O}(\sqrt{n})}

. By focusing on structure encoded in the codomain of the problem, we develop a polynomial-time algorithm which uses this structure to direct a "walk" down the subgroup lattice of

\mathbb{D}_{2^n}

terminating at the hidden subgroup.

DOI: 10.48550/arxiv.2202.09697

Related papers

Dihedral Hidden Subgroup Problem: A Survey

Hirotada Kobayashi, François Le Gall

After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.

IPSJ Digital CourierJan 1, 20057 citations

A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Greg Kuperberg

We present a quantum algorithm for the dihedral hidden subgroup problem (DHSP) with time and query complexity $2^{O(\sqrt{\log\ N})}$ . In this problem an oracle computes a function f on the dihedral group $D_N$ which is invariant under a hidden reflection in $D_N$ . By contrast, the classical query complexity of DHSP is $O(\sqrt{N})$ . The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins as usual with a quantum character transform, which in the case of $D_N$ is essentially the abelian quantum Fourier transform. This yields the name of a group representation of $D_N$ , which is not by itself useful, and a state in the representation, which is a valuable but indecipherable qubit. The algorithm proceeds by repeatedly pairing two unfavorable qubits to make a new qubit in a more favorable representation of $D_N$ . Once the algorithm obtains certain target representations, direct measurements reveal the hidden subgroup.We present a quantum algorithm for the dihedral hidden subgroup problem (DHSP) with time and query complexity $2^{O(\sqrt{\log\ N})}$. In this problem an oracle computes a function f on the dihedral group $D_N$ which is invariant under a hidden reflection in $D_N$. By contrast, the classical query complexity of DHSP is $O(\sqrt{N})$. The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins as usual with a quantum character transform, which in the case of $D_N$ is essentially the abelian quantum Fourier transform. This yields the name of a group representation of $D_N$, which is not by itself useful, and a state in the representation, which is a valuable but indecipherable qubit. The algorithm proceeds by repeatedly pairing two unfavorable qubits to make a new qubit in a more favorable representation of $D_N$. Once the algorithm obtains certain target representations, direct measurements reveal the hidden subgroup.

arXiv:quant-ph/0302112SIAM Journal on ComputingJan 1, 2005347 citations

Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups

Demerson Nunes Gonçalves, Renato Portugal

The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms can be casted in the HSP structure. In this paper, we present a new polynomial-time quantum algorithm that solves the HSP over the group $\Z_{p^r} \rtimes \Z_{q^s}$ , when $p^r/q= \up{poly}(\log p^r)$, where $p$ , $q$ are any odd prime numbers and $r, s$ are any positive integers. To find the hidden subgroup, our algorithm uses the abelian quantum Fourier transform and a reduction procedure that simplifies the problem to find cyclic subgroups.The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms can be casted in the HSP structure. In this paper, we present a new polynomial-time quantum algorithm that solves the HSP over the group $\Z_{p^r} \rtimes \Z_{q^s}$, when $p^r/q= \up{poly}(\log p^r)$, where $p$, $q$ are any odd prime numbers and $r, s$ are any positive integers. To find the hidden subgroup, our algorithm uses the abelian quantum Fourier transform and a reduction procedure that simplifies the problem to find cyclic subgroups.

arXiv:1104.1361Apr 7, 20113 citations

Polynomial-time quantum algorithm for solving the hidden subgroup problem

Hefeng Wang

The hidden subgroup problem~(HSP) is one of the most important problems in quantum computation. Many problems for which quantum algorithm achieves exponential speedup over its classical counterparts can be reduced to the Abelian HSP. However, there is no efficient quantum algorithm for solving the non-Abelian HSP. We find that the HSP can be reduced to a nested structured search problem that is solved efficiently by using a quantum algorithm via multistep quantum computation. Then we solve the HSP and problems that can be reduced to both the Abelian and the non-Abelian HSP in polynomial time by using this algorithm.The hidden subgroup problem~(HSP) is one of the most important problems in quantum computation. Many problems for which quantum algorithm achieves exponential speedup over its classical counterparts can be reduced to the Abelian HSP. However, there is no efficient quantum algorithm for solving the non-Abelian HSP. We find that the HSP can be reduced to a nested structured search problem that is solved efficiently by using a quantum algorithm via multistep quantum computation. Then we solve the HSP and problems that can be reduced to both the Abelian and the non-Abelian HSP in polynomial time by using this algorithm.

arXiv:2204.03295Apr 7, 20220 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

ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM

Stephen Fenner, Yong Zhang

We study the computational complexity of the HIDDEN SUBGROUP problem, a well-studied problem in quantum computing. First we show that several proposed generalizations or variants of this problem, including HIDDEN COSET, HIDDEN SHIFT, and ORBIT COSET, are all equivalent or reducible to HIDDEN SUBGROUP. Then we study the relationship between the decision version and search version of HIDDEN SUBGROUP over various group classes. We show that the two versions are polynomial-time equivalent over permutation groups, and over dihedral groups given the order of the group is smooth. Finally, we give nonadaptive program checkers for HIDDEN SUBGROUP and its decision version.We study the computational complexity of the HIDDEN SUBGROUP problem, a well-studied problem in quantum computing. First we show that several proposed generalizations or variants of this problem, including HIDDEN COSET, HIDDEN SHIFT, and ORBIT COSET, are all equivalent or reducible to HIDDEN SUBGROUP. Then we study the relationship between the decision version and search version of HIDDEN SUBGROUP over various group classes. We show that the two versions are polynomial-time equivalent over permutation groups, and over dihedral groups given the order of the group is smooth. Finally, we give nonadaptive program checkers for HIDDEN SUBGROUP and its decision version.

International Journal of Foundations of Computer ScienceDec 1, 20132 citations

We present a polynomial-time quantum algorithm for the Hidden Subgroup Problem over

\mathbb{D}_{2^n}

. The usual approach to the Hidden Subgroup Problem relies on harmonic analysis in the domain of the problem, and the best known algorithm using this approach has time complexity in

2^{\mathcal{O}(\sqrt{n})}

. By focusing on structure encoded in the codomain of the problem, we develop a polynomial-time algorithm which uses this structure to direct a "walk" down the subgroup lattice of

\mathbb{D}_{2^n}

terminating at the hidden subgroup.

We present a quantum algorithm for the dihedral hidden subgroup problem (DHSP) with time and query complexity

2^{O(\sqrt{\log\ N})}

. In this problem an oracle computes a function f on the dihedral group

D_N

which is invariant under a hidden reflection in

D_N

. By contrast, the classical query complexity of DHSP is

O(\sqrt{N})

. The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins as usual with a quantum character transform, which in the case of

D_N

is essentially the abelian quantum Fourier transform. This yields the name of a group representation of

D_N

, which is not by itself useful, and a state in the representation, which is a valuable but indecipherable qubit. The algorithm proceeds by repeatedly pairing two unfavorable qubits to make a new qubit in a more favorable representation of

D_N

. Once the algorithm obtains certain target representations, direct measurements reveal the hidden subgroup.

\Z_{p^r} \rtimes \Z_{q^s}

, when $p^r/q= \up{poly}(\log p^r)$, where

p

q

are any odd prime numbers and

r, s

are any positive integers. To find the hidden subgroup, our algorithm uses the abelian quantum Fourier transform and a reduction procedure that simplifies the problem to find cyclic subgroups.

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).