The Symmetric Group Defies Strong Fourier Sampling

DOI10.1137/050644896zbMath1155.68029OpenAlexW2040938513MaRDI QIDQ3549325

Moore, Cristopher, Leonard J. Schulman, Alexander Russell

Publication date: 22 December 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://resolver.caltech.edu/CaltechAUTHORS:MOOsiamjc08

zbMATH Keywords

quantum computinggraph isomorphismhidden subgroup problemFourier sampling

Mathematics Subject Classification ID

Finite-dimensional groups and algebras motivated by physics and their representations (81R05) Representations of groups, semigroups, etc. (aspects of abstract harmonic analysis) (43A65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Random measurement bases, quantum state distinction and applications to the hidden subgroup problem ⋮ Quantum computation vs. firewalls ⋮ Practical post-quantum signature schemes from isomorphism problems of trilinear forms ⋮ On the Complexity of the Hidden Subgroup Problem ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ Quantum algorithm design: techniques and applications ⋮ Quantum algorithms for algebraic problems ⋮ Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts