{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T08:13:15Z","timestamp":1769501595185,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2010,10,1]],"date-time":"2010-10-01T00:00:00Z","timestamp":1285891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-04-R-0009"],"award-info":[{"award-number":["W911NF-04-R-0009"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0093065"],"award-info":[{"award-number":["CCR-0093065"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","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\/100000001","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":["J. ACM"],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p>It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore et al. [2005] that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once.<\/jats:p>\n          <jats:p>\n            We show that entangled quantum measurements on at least \u03a9(\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because in general it seems hard to implement a given highly entangled measurement. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL(\n            <jats:italic>n<\/jats:italic>\n            ,F\n            <jats:sub>\n              <jats:italic>p<\/jats:italic>\n              <jats:sup>\n                <jats:italic>m<\/jats:italic>\n              <\/jats:sup>\n            <\/jats:sub>\n            ) and\n            <jats:italic>G<\/jats:italic>\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            where\n            <jats:italic>G<\/jats:italic>\n            is finite and satisfies a suitable property.\n          <\/jats:p>","DOI":"10.1145\/1857914.1857918","type":"journal-article","created":{"date-parts":[[2010,11,3]],"date-time":"2010-11-03T14:16:37Z","timestamp":1288793797000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Limitations of quantum coset states for graph isomorphism"],"prefix":"10.1145","volume":"57","author":[{"given":"Sean","family":"Hallgren","sequence":"first","affiliation":[{"name":"Pennsylvania State University, University Park, PA"}]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM"}]},{"given":"Martin","family":"R\u00f6tteler","sequence":"additional","affiliation":[{"name":"NEC Laboratories America, Inc., Princeton, NJ"}]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[{"name":"University of Connecticut, Storrs, CT"}]},{"given":"Pranab","family":"Sen","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}]}],"member":"320","published-online":{"date-parts":[[2010,11,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276708"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780546"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Alagic G.","unstructured":"Alagic , G. , Moore , C. , and Russell , A . 2007. Quantum algorithms for Simon's problem over general groups . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07) . ACM, New York, 1217--1224. (Also : ArXiv preprint quant-ph\/0603251.) Alagic, G., Moore, C., and Russell, A. 2007. Quantum algorithms for Simon's problem over general groups. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). ACM, New York, 1217--1224. (Also: ArXiv preprint quant-ph\/0603251.)"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.38"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2006.002"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258548"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_2_1_8_1","volume-title":"Translations of Mathematical Monographs","volume":"181","author":"Berkovich Y. G.","unstructured":"Berkovich , Y. G. , and Zhmud , E. M . 1999. Characters of Finite Groups, Part 2 . Translations of Mathematical Monographs , vol. 181 . American Mathematical Society, New York. Berkovich, Y. G., and Zhmud, E. M. 1999. Characters of Finite Groups, Part 2. Translations of Mathematical Monographs, vol. 181. American Mathematical Society, New York."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of 5th Israeli Symposium on Theory of Computing and Systems. ISTCS, IEEE Computer Society Press","author":"Brassard G.","unstructured":"Brassard , G. , and H\u00f8yer , P . 1997. An exact polynomial--time algorithm for Simon's problem . In Proceedings of 5th Israeli Symposium on Theory of Computing and Systems. ISTCS, IEEE Computer Society Press , Los Alamitos, CA, 12--33. (Also : ArXiv preprint quant--ph\/9704027.) Brassard, G., and H\u00f8yer, P. 1997. An exact polynomial--time algorithm for Simon's problem. In Proceedings of 5th Israeli Symposium on Theory of Computing and Systems. ISTCS, IEEE Computer Society Press, Los Alamitos, CA, 12--33. (Also: ArXiv preprint quant--ph\/9704027.)"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Childs A. and Wocjan P. 2007. On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems. Quant. Inf. Comput. 7 5&amp;6 371--382. (Also: ArXiv preprint quant--ph\/0510185.)   Childs A. and Wocjan P. 2007. On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems. Quant. Inf. Comput. 7 5&amp;6 371--382. (Also: ArXiv preprint quant--ph\/0510185.)","DOI":"10.26421\/QIC7.5-6-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2000.0699"},{"key":"e_1_2_1_12_1","unstructured":"Ettinger M. H\u00f8yer P. and Knill E. 1999a. A quantum observable for the graph isomorphism problem. (ArXiv preprint quant--ph\/9901029.)  Ettinger M. H\u00f8yer P. and Knill E. 1999a. A quantum observable for the graph isomorphism problem. (ArXiv preprint quant--ph\/9901029.)"},{"key":"e_1_2_1_13_1","unstructured":"Ettinger M. H\u00f8yer P. and Knill E. 1999b. Hidden subgroup states are almost orthogonal. (ArXiv preprint quant--ph\/9901034.)  Ettinger M. H\u00f8yer P. and Knill E. 1999b. Hidden subgroup states are almost orthogonal. (ArXiv preprint quant--ph\/9901034.)"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.024"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780544"},{"key":"e_1_2_1_16_1","volume-title":"Representation Theory: A First Course. Graduate Texts in Mathematics","author":"Fulton W.","year":"1991","unstructured":"Fulton , W. , and Harris , J . 1991 . Representation Theory: A First Course. Graduate Texts in Mathematics , vol. 129 . Springer , New York . Fulton, W., and Harris, J. 1991. Representation Theory: A First Course. Graduate Texts in Mathematics, vol. 129. Springer, New York."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1994-1185260-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2011617.2011625"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0009-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132603"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060660"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970139450X"},{"key":"e_1_2_1_25_1","volume-title":"Character Theory of Finite Groups","author":"Isaacs I. M.","unstructured":"Isaacs , I. M. 1976. Character Theory of Finite Groups . Academic Press , New York . Isaacs, I. M. 1976. Character Theory of Finite Groups. Academic Press, New York."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103001996"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS'07)","volume":"4393","author":"Ivanyos G.","unstructured":"Ivanyos , G. , Sanselme , L. , and Santha , M . 2007. An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups . In Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS'07) . Lecture Notes in Computer Science , vol. 4393 . Springer-Verlag, Berlin, Germany, 586--597. (Also: ArXiv preprint quant--ph\/0701235.) Ivanyos, G., Sanselme, L., and Santha, M. 2007. An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups. In Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS'07). Lecture Notes in Computer Science, vol. 4393. Springer-Verlag, Berlin, Germany, 586--597. (Also: ArXiv preprint quant--ph\/0701235.)"},{"key":"e_1_2_1_28_1","unstructured":"James G. and Kerber A. 1981. The Representation Theory of the Symmetric Group. Addison-Wesley Reading.  James G. and Kerber A. 1981. The Representation Theory of the Symmetric Group. Addison-Wesley Reading."},{"key":"e_1_2_1_29_1","unstructured":"Kitaev A. Y. 1995. Quantum measurements and the abelian stabilizer problem. (ArXiv preprint quant--ph\/9511026.)  Kitaev A. Y. 1995. Quantum measurements and the abelian stabilizer problem. (ArXiv preprint quant--ph\/9511026.)"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"K\u00f6bler J. Sch\u00f6ning U. and Tor\u00e1n J. 1993. The Graph Isomorphism Problem. Birkh\u00e4user Boston.  K\u00f6bler J. Sch\u00f6ning U. and Tor\u00e1n J. 1993. The Graph Isomorphism Problem. Birkh\u00e4user Boston.","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436345"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.1992.10504252"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447177"},{"key":"e_1_2_1_34_1","unstructured":"Moore C. and Russell A. 2005a. Explicit multiregister measurements for hidden subgroup problems. (ArXiv preprint quant--ph\/0504067.)  Moore C. and Russell A. 2005a. Explicit multiregister measurements for hidden subgroup problems. (ArXiv preprint quant--ph\/0504067.)"},{"key":"e_1_2_1_35_1","unstructured":"Moore C. and Russell A. 2005b. The symmetric group defies strong Fourier sampling: Part II. (ArXiv preprint quant--ph\/0501066.)  Moore C. and Russell A. 2005b. The symmetric group defies strong Fourier sampling: Part II. (ArXiv preprint quant--ph\/0501066.)"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.73"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250868"},{"key":"e_1_2_1_38_1","unstructured":"Moore C. Russell A. and Vazirani U. 2007c. A classical one-way function to confound quantum adversaries. (ArXiv preprint quant--ph\/0701115.)  Moore C. Russell A. and Vazirani U. 2007c. A classical one-way function to confound quantum adversaries. (ArXiv preprint quant--ph\/0701115.)"},{"key":"e_1_2_1_39_1","volume-title":"Quantum Computing and Quantum Communications. Lecture Notes in Computer Science","volume":"1509","author":"Mosca M.","unstructured":"Mosca , M. , and Ekert , A . 1998. The hidden subgroup problem and eigenvalue estimation on a quantum computer . In Quantum Computing and Quantum Communications. Lecture Notes in Computer Science , vol. 1509 . Springer-Verlag, Berlin, Germany, 174--188. Mosca, M., and Ekert, A. 1998. The hidden subgroup problem and eigenvalue estimation on a quantum computer. In Quantum Computing and Quantum Communications. Lecture Notes in Computer Science, vol. 1509. Springer-Verlag, Berlin, Germany, 174--188."},{"key":"e_1_2_1_40_1","unstructured":"Nielsen M. and Chuang I. 2000. Quantum Computation and Quantum Information. Cambridge University Press Cambridge UK.   Nielsen M. and Chuang I. 2000. Quantum Computation and Quantum Information. Cambridge University Press Cambridge UK."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9231-x"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039490"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703440678"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002220050083"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060661"},{"key":"e_1_2_1_46_1","volume-title":"Linear Representations of Finite Groups","author":"Serre J. P.","unstructured":"Serre , J. P. 1977. Linear Representations of Finite Groups . Springer , New York . Serre, J. P. 1977. Linear Representations of Finite Groups. Springer, New York."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365701"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1857914.1857918","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1857914.1857918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:09:10Z","timestamp":1750248550000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1857914.1857918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":48,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.1145\/1857914.1857918"],"URL":"https:\/\/doi.org\/10.1145\/1857914.1857918","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10]]},"assertion":[{"value":"2008-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}