Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem

Simple item page
dc.creatorChilds, Andrew M.
dc.creatorHarrow, Aram W.
dc.creatorWocjan, Pawel
dc.date2006-09-14
dc.date.accessioned2026-07-07T08:09:39Z
dc.date.available2026-07-07T08:09:39Z
dc.descriptionSchur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur duality to the problem of distinguishing coset states in the standard approach to the hidden subgroup problem. We observe that simply measuring the partition (a procedure we call weak Schur sampling) provides very little information about the hidden subgroup. Furthermore, we show that under quite general assumptions, even a combination of weak Fourier sampling and weak Schur sampling fails to identify the hidden subgroup. We also prove tight bounds on how many coset states are required to solve the hidden subgroup problem by weak Schur sampling, and we relate this question to a quantum version of the collision problem.
dc.description21 pages
dc.identifierhttps://arxiv.org/abs/quant-ph/0609110
dc.identifierhttp://arxiv.org/abs/quant-ph/0609110
dc.identifierProc. 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007), Lecture Notes in Computer Science 4393, pp. 598-609
dc.identifierdoi:10.1007/978-3-540-70918-3_51
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/131602
dc.subjectQuantum Physics
dc.titleWeak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
dc.typetext

Files

Collections

arXiv