{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T02:03:39Z","timestamp":1760061819056,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0093065","CCR-0220070EIA-0218563CCF-0524613EIA-0523456EIA-0523431"],"award-info":[{"award-number":["CCR-0093065","CCR-0220070EIA-0218563CCF-0524613EIA-0523456EIA-0523431"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["47976-PH-QC"],"award-info":[{"award-number":["47976-PH-QC"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCR-0220070EIA-0218563CCF-0524613EIA-0523456EIA-0523431"],"award-info":[{"award-number":["CCR-0220070EIA-0218563CCF-0524613EIA-0523456EIA-0523431"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>\n            Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding \u201chidden shifts\u201d of Z\n            <jats:sub>2<\/jats:sub>\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group\n            <jats:italic>G<\/jats:italic>\n            , this is the problem of recovering an involution\n            <jats:italic>m<\/jats:italic>\n            = (\n            <jats:italic>m<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\u2026,\n            <jats:italic>\n              m\n              <jats:sub>n<\/jats:sub>\n            <\/jats:italic>\n            ) \u2208\n            <jats:italic>\n              G\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            from an oracle\n            <jats:italic>f<\/jats:italic>\n            with the property that\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            \u22c5\n            <jats:italic>y<\/jats:italic>\n            ) =\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            ) \u21d4\n            <jats:italic>y<\/jats:italic>\n            \u2208 {1,\n            <jats:italic>m<\/jats:italic>\n            }. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form\n            <jats:italic>\n              G\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            , where\n            <jats:italic>G<\/jats:italic>\n            is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two.\n          <\/jats:p>\n          <jats:p>\n            Although groups of the form\n            <jats:italic>\n              G\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            have a simple product structure, they share important representation--theoretic properties with the symmetric groups\n            <jats:italic>\n              S\n              <jats:sub>n<\/jats:sub>\n            <\/jats:italic>\n            , where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called \u201cstandard method\u201d requires highly entangled measurements on the tensor product of many coset states.\n          <\/jats:p>\n          <jats:p>\n            In this article, we provide quantum algorithms with time complexity 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\u221a\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            that recover hidden involutions\n            <jats:italic>m<\/jats:italic>\n            = (\n            <jats:italic>m<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\u2026\n            <jats:italic>\n              m\n              <jats:sub>n<\/jats:sub>\n            <\/jats:italic>\n            ) \u2208\n            <jats:italic>\n              G\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            where, as in Simon's problem, each\n            <jats:italic>\n              m\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            is either the identity or the conjugate of a known element\n            <jats:italic>m<\/jats:italic>\n            which satisfies \u03ba(\n            <jats:italic>m<\/jats:italic>\n            ) = \u2212\u03ba(1) for some \u03ba \u2208\n            <jats:italic>\u011c<\/jats:italic>\n            . Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the \u201cmissing harmonic\u201d approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.\n          <\/jats:p>","DOI":"10.1145\/1644015.1644034","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T13:16:40Z","timestamp":1282655800000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Quantum algorithms for Simon's problem over nonabelian groups"],"prefix":"10.1145","volume":"6","author":[{"given":"Gorjan","family":"Alagic","sequence":"first","affiliation":[{"name":"University of Waterloo, Ont., Canada"}]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM"}]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[{"name":"University of Connecticut, Storrs, CT"}]}],"member":"320","published-online":{"date-parts":[[2009,12,28]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Alagic G. Moore C. and Russell A. 2005. Strong Fourier sampling fails over Gn. Tech. Rep. quant-ph\/0511054 arXiv.org.  Alagic G. Moore C. and Russell A. 2005. Strong Fourier sampling fails over G n . Tech. Rep. quant-ph\/0511054 arXiv.org."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.38"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780544"},{"volume-title":"Representation Theory: A First Course. Number 129 in Graduate Texts in Mathematics","year":"1991","author":"Fulton W.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132603"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335392"},{"key":"e_1_2_1_7_1","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding W.","year":"1963","journal-title":"J. Amer. Stat. Soc."},{"volume-title":"Proceedings of EQIS.","author":"Inui Y.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103001996"},{"volume":"47","volume-title":"Classical and Quantum Computation. Graduate Studies in Mathematics","author":"Kitaev A.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436345"},{"volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Moore C.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Moore C.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"Moore C. and Russell A. 2005. Explicit multiregister measurements for hidden subgroup problems; or fourier sampling strikes back. Tech. Rep. quant-ph\/0504067 arXiv.org.  Moore C. and Russell A. 2005. Explicit multiregister measurements for hidden subgroup problems; or fourier sampling strikes back. Tech. Rep. quant-ph\/0504067 arXiv.org."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.73"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652155"},{"key":"e_1_2_1_17_1","unstructured":"R\u00f6tteler M. and Beth T. 1998. Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups. Tech. Rep. quant-ph\/9812070 arXiv.org.  R\u00f6tteler M. and Beth T. 1998. Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups. Tech. Rep. quant-ph\/9812070 arXiv.org."},{"volume-title":"The Symmetric Group. Number 203 in Graduate Texts in Mathematics","author":"Sagan B.","key":"e_1_2_1_18_1"},{"volume-title":"Linear Representations of Finite Groups. Number 42 in Graduate Texts in Mathematics","author":"Serre J.-P.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298637"},{"volume-title":"Introduction to Coding Theory. Number 86 in Graduate Texts in Mathematics","author":"van Lint J. H.","key":"e_1_2_1_22_1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644034","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1644015.1644034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:53Z","timestamp":1750250453000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1644015.1644034"],"URL":"https:\/\/doi.org\/10.1145\/1644015.1644034","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2007-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}