Title

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. © Springer-Verlag Berlin Heidelberg 2007.

Publication Date

1-1-2007

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

4393 LNCS

Number of Pages

598-609

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/978-3-540-70918-3_51

Socpus ID

38049181353 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/38049181353

This document is currently not available here.

Share

COinS