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

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.

21 pages

References in corpus (19)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum fingerprinting
• An approximate Fourier transform useful in quantum factoring
• Quantum Algorithm for the Collision Problem
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Estimating the spectrum of a density operator
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• Quantum universal variable-length source coding
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• Applications of coherent classical communication and the Schur transform to quantum information theory
• A Quantum Observable for the Graph Isomorphism Problem
• Hidden Subgroup States are Almost Orthogonal
• Measuring the purity of a qubit state: entanglement estimation with fully separable measurements
• Purity estimation with separable measurements
• The Quantum Schur Transform: I. Efficient Qudit Circuits
• The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
• On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
• Random measurement bases, quantum state distinction and applications to the hidden subgroup problem

Cited by in corpus (19)

• Sample-optimal tomography of quantum states
• Quantum Algorithmic Measurement
• A Survey of Quantum Property Testing
• Measuring Quantum Entropy
• Efficient classical algorithms for simulating symmetric quantum systems
• Quantum Schur Sampling Circuits can be Strongly Simulated
• Approximate orthogonality of permutation operators, with application to quantum information
• A Classical Algorithm for Quantum $\text{SU}(2)$ Schur Sampling
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• Entanglement theory with limited computational resources
• Linear programming with unitary-equivariant constraints
• Symmetric functions of qubits in an unknown basis
• Abelian Hypergroups and Quantum Computation
• How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
• Time-Efficient Quantum Entropy Estimator via Samplizer
• A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
• Cosine series quantum sampling method with applications in signal and image processing
• Quantum Spectrum Testing
• Towards Symmetry-Aware Efficient Simulation of Quantum Systems and Beyond