REVIEW
The Symmetric Group Defies Strong Fourier Sampling: Part I
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
The Symmetric Group Defies Strong Fourier Sampling: Part I
classification
quant-ph
cs.CC
keywords
fourierproblemsamplingefficientlygrouphiddenstrongsubgroup
read the original abstract
We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem. Specifically, we show that the hidden subgroup problem over the symmetric group cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. Our results apply to the special case relevant to the Graph Isomorphism problem.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.