The hidden subgroup problem and permutation group theory

ABSTRACT

We employ concepts and tools from the theory of finite permutation groups in order to analyse the Hidden Subgroup Problem via Quantum Fourier Sampling (QFS) for the symmetric group. We show that under very general conditions both the weak and the random-strong form (strong form with random choices of basis) of QFS fail to provide any advantage over classical exhaustive search. In particular we give a complete characterisation of polynomial size subgroups, and of primitive subgroups, that can be distinguished from the identity subgroup with the above methods. Furthermore, assuming a plausible group theoretic conjecture for which we give supporting evidence, we show that weak and random-strong QFS for the symmetric group have no advantage whatsoever over classical search.

REFERENCES

• 1: {Bab81} L. Babai. On the order of uniprimitive permutation groups. Annals of Math., 113:553--568, 1981.
• 2: {Bab82} L. Babai. On the order of doubly transitive permutation groups. Invent. Math., 65:473--484, 1982.
• 3: Robert Beals, Quantum computation of Fourier transforms over symmetric groups, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.48-53, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258548]
• 4: {Cam81} P. J. Cameron. Finite permutation groups and finite simple groups. Bull. London Math. Soc., 13(1):1--22, 1981.
• 5: {DM96} J. D. Dixon and B. Mortimer. Permutation groups, volume 163 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1996.
• 6: {EH99} M. Ettinger and P. Hoyer. On quantum algorithms for noncommutative hidden subgroups. In Proc. 16th STACS, pages 478--487, 1999. Final version in Adv. in Appl. Math.
• 7: {EHK99} M. Ettinger, P. Hoyer, and E. Knill. Hidden subgroup states are almost orthogonal. Technical report, lanl-arXive quant-ph/9901034, 1999.
• 8: Katalin Friedl , Gábor Ivanyos , Frédéric Magniez , Miklos Santha , Pranab Sen, Hidden translation and orbit coset in quantum computing, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780544]
• 9: Michelangelo Grigni , Leonard Schulman , Monica Vazirani , Umesh Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.68-74, July 2001, Hersonissos, Greece [doi>10.1145/380752.380769]
• 10: Sean Hallgren , Alexander Russell , Amnon Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.627-635, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335392]
• 11: Gábor Ivanyos , Frédéric Magniez , Miklos Santha, Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.263-270, July 2001, Crete Island, Greece [doi>10.1145/378580.378679]
• 12: {IMS03} G. Ivanyos, F. Magniez, and M. Santha. Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. International Journal of Foundations of Computer Science, 2003. Journal version of {IMS01}. To appear.
• 13: {Jor73} C. Jordan. Sur la limite de transitivite des groupes non alternés. Bull. Soc. Math. France, 1:40--71, 1873.
• 14: {Jor75} C. Jordan. Sur la limite de degré des groupes primitifs qui contiennent une substitution donnée. J. reine angew Math., 79:248--258, 1875.
• 15: {Joz00} R. Jozsa. Quantum factoring, discrete logarithms and the hidden subgroup problem. arXiv preprint lanl quant-ph/0012084, prepared for IEEE Computing in Science and Engineering, 2000.
• 16: {Kit95} A. Kitaev. Quantum measurements and the abelian stabilizer problem. arXive preprint lanl quant-ph/9511026, 1995.
• 17: {Kup03} G. Kuperberg. A subexponential-time algorithm for the dihedral hidden subgroup problem. Technical report, lanl-arXive quant-ph/0302112, 2003.
• 18: {LS01} M. Liebeck and A. Shalev. Diameters of finite simple groups: sharp bounds and applications. Ann. of Math. (2), 154(2):383--406, 2001.
• 19: Cristopher Moore , Daniel Rockmore , Alexander Russell, Generic quantum Fourier transforms, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 20: Cristopher Moore , Daniel Rockmore , Alexander Russell , Leonard J. Schulman, The power of basis selection in fourier sampling: hidden subgroup problems in affine groups, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 21: {NC00} M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, UK, 2000.
• 22: Markus Püschel , Martin Rötteler , Thomas Beth, Fast Quantum Fourier Transforms for a Class of Non-Abelian Groups, Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.148-159, November 15-19, 1999
• 23: {RB98} M. Rötteler and T. Beth. Polynomial-time solution to the hidden subgroup problem for a class of non-Abelian groups. Technical report, Quantum Physics e-Print archive, 1998. http://xxx.lanl.gov/abs/quant-ph/9812070.
• 24: Oded Regev, Quantum Computation and Lattice Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.520-529, November 16-19, 2002
• 25: {Reg04} O. Regev. A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space, 2004. quant-ph/0406151.
• 26: {Sag01} Bruce E. Sagan. The symmetric group, volume 203 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2001. Representations, combinatorial algorithms, and symmetric functions.
• 27: {Sho94} P. W. Shor. Algorithms for quantum computation: Discrete log and factoring. In Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, pages 124--134, Los Alamitos, CA, 1994. IEEE Computer Society.