|
An exact quantum hidden subgroup
algorithm and applications to solvable groups
(pp770-789)
Muhammad
Imran and Gabor Ivanyos
doi:
https://doi.org/10.26421/QIC22.9-10-4
Abstracts:
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.
Key Words:
exact quantum algorithm,
hidden subgroup problem,
abelian
group, solvable group |
