A quantum computer can efficiently find the order of an element in a group, factors of composite integers, discrete logarithms, stabilisers in Abelian groups, and `hidden' or `unknown' subgroups of Abelian groups. It is already known how to phrase the first four problems as the estimation of eigenvalues of certain unitary operators. Here we show how the solution to the more general Abelian `hidden subgroup problem' can also be described and analysed as such. We then point out how certain instances of these problems can be solved with only one control qubit, or `flying qubits', instead of entire registers of control qubits.
We examine the application of quantum algorithms to the non-Abelian hidden subgroup problem and focus on the dihedral hidden subgroup problem (DHSP). Ettinger and Høyer have recently discovered an algorithm which, although efficient in the number of operations of the quantum computation, requires classical post-processing which grows exponentially with the size of the input. We first show that the DHSP can be reduced to another problem: how to efficiently estimate an unknown shift k , in a one-to-one map f : M → M , given two oracles which provide x → f ( x ), and x → f ( x ⊕ k ), with k and f unknown. We devise an algorithm which uses amplitude amplification to obtain an estimate for the unknown shift k in a number (( M ) 1/2 ) oracle calls.
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
Zpr⋊Zqs, 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.