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

DOI10.1007/978-3-540-70918-3_51MaRDI QIDQ3590967zbMATHOpenAlexFDO

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

Publication date 3 September 2007

Published in STACS 2007 (Search for Journal in Brave)

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)

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.

Recommendations

• The Symmetric Group Defies Strong Fourier Sampling
• The hidden subgroup problem and permutation group theory
• The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups
• Random measurement bases, quantum state distinction and applications to the hidden subgroup problem
• Automata, Languages and Programming

Cited in

(4)

• The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound
• Linear programming with unitary-equivariant constraints
• Random measurement bases, quantum state distinction and applications to the hidden subgroup problem
• Approximate orthogonality of permutation operators, with application to quantum information

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)