|
Deterministic algorithms for the hidden
subgroup problem
(pp755-769)
Ashwin
Nayak
doi:
https://doi.org/10.26421/QIC22.9-10-3
Abstracts:
We present deterministic algorithms for the
Hidden Subgroup Problem. The first algorithm, for
abelian
groups, achieves the same asymptotic worst-case query complexity as the
optimal randomized algorithm, namely~$
\Order(\sqrt{ n}\, )$, where~$n$
is the order of the group. The analogous algorithm for non-abelian
groups comes within a~$\sqrt{ \log
n}$ factor of the optimal randomized
query complexity. The best known randomized algorithm for the Hidden
Subgroup Problem has \emph{expected\/}
query complexity that is sensitive to the input, namely~$
\Order(\sqrt{ n/m}\, )$, where~$m$
is the order of the hidden subgroup. In the first version of this
article~\cite[Sec.~5]{Nayak21-hsp-classical},
we asked if there is a deterministic algorithm whose query complexity
has a similar dependence on the order of the hidden subgroup. Prompted
by this question, Ye and Li~\cite{YL21-hsp-classical}
present deterministic algorithms for
\emph{abelian\/}
groups which solve the problem with~$
\Order(\sqrt{ n/m }\, )$ queries,
and find the hidden subgroup with~$
\Order( \sqrt{ n (\log m) / m} + \log m ) $
queries. Moreover, they exhibit instances which show that in general,
the deterministic query complexity of the problem may be~$\order(\sqrt{
n/m } \,)$, and that of
\emph{finding\/}
the entire subgroup may also be~$\order(\sqrt{
n/m } \,)$ or even~$\upomega(\sqrt{
n/m } \,) $.}We present a different
deterministic algorithm for the Hidden Subgroup Problem that also has
query complexity~$ \Order(\sqrt{ n/m
}\, )$ for
abelian
groups. The algorithm is arguably simpler. Moreover, it works for non-abelian
groups, and has query complexity~$
\Order(\sqrt{ (n/m) \log (n/m) }\,) $
for a large class of instances, such as those over
supersolvable
groups. We build on this to design deterministic algorithms to find the
hidden subgroup for all
abelian
and some non-abelian
instances, at the cost of a~$\log m$
multiplicative factor increase in the query complexity.
Key Words:
Hidden Subgroup Problem,
deterministic algorithm, query complexity,
abelian
group, non-abelian
group, generating pair,
bicrossed
product |
