It is well known that quantum computers can efficiently find a hidden subgroup $H$ of a finite Abelian group $G$ . This implies that after only a polynomial (in $\log |G|$ ) number of calls to the oracle function, the states corresponding to different candidate subgroups have exponentially small inner product. We show that this is true for noncommutative groups also. We present a quantum algorithm which identifies a hidden subgroup of an arbitrary finite group $G$ in only a linear (in $\log |G|$ ) number of calls to the oracle function. This is exponentially better than the best classical algorithm. However our quantum algorithm requires an exponential amount of time, as in the classical case.It is well known that quantum computers can efficiently find a hidden subgroup $H$ of a finite Abelian group $G$. This implies that after only a polynomial (in $\log |G|$) number of calls to the oracle function, the states corresponding to different candidate subgroups have exponentially small inner product. We show that this is true for noncommutative groups also. We present a quantum algorithm which identifies a hidden subgroup of an arbitrary finite group $G$ in only a linear (in $\log |G|$) number of calls to the oracle function. This is exponentially better than the best classical algorithm. However our quantum algorithm requires an exponential amount of time, as in the classical case.

arXiv:quant-ph/9901034Jan 14, 199940 citations

On the Quantum Complexity of the Continuous Hidden Subgroup Problem

Koen de Boer, Léo Ducas, Serge Fehr

Lecture notes in computer scienceJan 1, 20207 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

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups

Gábor Ivanyos, Luc Sanselme, Miklós Sántha

Lecture notes in computer scienceJan 1, 200837 citations

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups

Hari Krovi, Martin Rötteler

Lecture notes in computer scienceJan 1, 20089 citations

It is well known that quantum computers can efficiently find a hidden subgroup

H

of a finite Abelian group

G

. This implies that after only a polynomial (in

\log |G|

) number of calls to the oracle function, the states corresponding to different candidate subgroups have exponentially small inner product. We show that this is true for noncommutative groups also. We present a quantum algorithm which identifies a hidden subgroup of an arbitrary finite group

G

in only a linear (in

\log |G|

) number of calls to the oracle function. This is exponentially better than the best classical algorithm. However our quantum algorithm requires an exponential amount of time, as in the classical case.

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