Blog de Frédéric  To content | To menu | To search  Tag - markov
process  Entries feed - Comments feed  Sunday, April 22 2012
Cyclic HSP based on Subgroup Reduction  In my master thesis on
quantum computing, I designed a version of the Abelian HSP
algorithm based on subgroup reduction. In a previous blog post,
I wondered whether this algorithm could be extended to the
Dedekindian HSP and if it would be more efficient than the
standard one. I’m going to prove that the latter is false in the
cyclic case, where the two algorithms have exactly the same
associated Markov chain.  Recall that the HSP is - given a
finite group GG, an unknown subgroup HH and an "oracle" ff
hiding HH (i.e. a function on GG which factorizes on the coset
space G/HG/H in a function with pairwise distinct values) - to
determine the subgroup HH using a number of oracle calls
polynomial in the size of GG.  In the standard Dedekindian HSP
algorithm, GG is a dedekind group and we use Fourier Sampling to
measure a polynomial number of represen