From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups

Simple item page
dc.creatorBacon, Dave
dc.creatorChilds, Andrew M.
dc.creatorvan Dam, Wim
dc.date2005-04-11
dc.date2005-04-26
dc.date.accessioned2026-07-07T06:22:48Z
dc.date.available2026-07-07T06:22:48Z
dc.descriptionWe 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.
dc.description18 pages; v2: updated references on optimal measurement
dc.identifierhttps://arxiv.org/abs/quant-ph/0504083
dc.identifierhttp://arxiv.org/abs/quant-ph/0504083
dc.identifierProc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 469-478
dc.identifierdoi:10.1109/SFCS.2005.38
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/96020
dc.subjectQuantum Physics
dc.titleFrom optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
dc.typetext

Files

Collections

arXiv