@article {1240,
title = {From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
},
year = {2005},
month = {2005/04/11},
abstract = { We approach the hidden subgroup problem by performing the so-called pretty
good measurement on hidden subgroup states. For various groups that can be
expressed as the semidirect product of an abelian group and a cyclic group, we
show that the pretty good measurement is optimal and that its probability of
success and unitary implementation are closely related to an average-case
algebraic problem. By solving this problem, we find efficient quantum
algorithms for a number of nonabelian hidden subgroup problems, including some
for which no efficient algorithm was previously known: certain metacyclic
groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including
the Heisenberg group, r=2). In particular, our results show that entangled
measurements across multiple copies of hidden subgroup states can be useful for
efficiently solving the nonabelian HSP.
},
doi = {10.1109/SFCS.2005.38},
url = {http://arxiv.org/abs/quant-ph/0504083v2},
author = {Dave Bacon and Andrew M. Childs and Wim van Dam}
}