Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem

DOI10.1007/978-3-540-70918-3_51zbMATH Open1186.81038arXivquant-ph/0609110OpenAlexW2096150384MaRDI QIDQ3590967FDOQ3590967

Aram W. Harrow, Pawel Wocjan, Andrew M. Childs

Publication date: 3 September 2007

Published in: STACS 2007 (Search for Journal in Brave)

Abstract: Schur 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.

Full work available at URL: https://arxiv.org/abs/quant-ph/0609110

Mathematics Subject Classification ID

Quantum computation (81P68) Finite nilpotent groups, (p)-groups (20D15)

Cited In (4)

• The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound
• Approximate orthogonality of permutation operators, with application to quantum information
• Quantum spectrum testing
• Linear programming with unitary-equivariant constraints

This page was built for publication: Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3590967)