{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,17]],"date-time":"2022-09-17T17:28:50Z","timestamp":1663435730515},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-04-R-0009"]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0093065","CCR-0220070EIA-0218563CCF-0524613EIA-0523456EIA-0523431"]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCR-0220070EIA-0218563CCF-0524613EIA-0523456EIA-0523431"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,10]]},"abstract":"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>We show that entangled quantum measurements on at least \u03a9(n<\/jats:italic>logn<\/jats:italic>) 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>,Fp<\/jats:italic>m<\/jats:italic><\/jats:sup><\/jats:sub>) andG<\/jats:italic>n<\/jats:italic><\/jats:sup>whereG<\/jats:italic>is finite and satisfies a suitable property.<\/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","source":"Crossref","is-referenced-by-count":11,"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","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."},{"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."},{"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."},{"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&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&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"},{"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."},{"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."},{"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."},{"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","doi-asserted-by":"crossref","volume-title":"Linear Representations of Finite Groups","author":"Serre J. P.","DOI":"10.1007\/978-1-4684-9458-7"},{"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\/pdf\/10.1145\/1857914.1857918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,13]],"date-time":"2021-11-13T01:21:36Z","timestamp":1636766496000},"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":"http:\/\/dx.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":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2010,10]]}}}