The Symmetric Group Defies Strong Fourier Sampling: Part I

Simple item page
dc.creatorMoore, Cristopher
dc.creatorRussell, Alexander
dc.creatorSchulman, Leonard J.
dc.date2005-01-12
dc.date2005-10-14
dc.date.accessioned2026-07-07T06:40:50Z
dc.date.available2026-07-07T06:40:50Z
dc.descriptionWe resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem. Specifically, we show that the hidden subgroup problem over the symmetric group cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. Our results apply to the special case relevant to the Graph Isomorphism problem.
dc.description19 pages; v2 fix typos; v3 adds material on structured permutations
dc.identifierhttps://arxiv.org/abs/quant-ph/0501056
dc.identifierhttp://arxiv.org/abs/quant-ph/0501056
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/101501
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleThe Symmetric Group Defies Strong Fourier Sampling: Part I
dc.typetext

Files

Collections

arXiv