{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:55:10Z","timestamp":1725512110812},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540792277"},{"type":"electronic","value":"9783540792284"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79228-4_6","type":"book-chapter","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T05:07:56Z","timestamp":1209445676000},"page":"70-81","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of the Hidden Subgroup Problem"],"prefix":"10.1007","author":[{"given":"Stephen","family":"Fenner","sequence":"first","affiliation":[]},{"given":"Yong","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","volume-title":"Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science","author":"V. Arvind","year":"2002","unstructured":"Arvind, V., Kurur, P.P.: Graph Isomorphism is in SPP. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, IEEE, New York (2002)"},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/S0304-3975(00)00159-6","volume":"259","author":"V. Arvind","year":"2001","unstructured":"Arvind, V., Tor\u00e1n, J.: A nonadaptive NC checker for permutation group intersection. Theoretical Computer Science\u00a0259, 597\u2013611 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M. Blum","year":"1995","unstructured":"Blum, M., Kannan, S.: Designing programs that check their work. Journal of the ACM\u00a042(1), 269\u2013291 (1995)","journal-title":"Journal of the ACM"},{"key":"6_CR4","first-page":"395","volume-title":"FOCS 2007: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007)","author":"A.M. Childs","year":"2007","unstructured":"Childs, A.M., Schulman, L.J., Vazirani, U.V.: Quantum algorithms for hidden nonlinear structures. In: FOCS 2007: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 395\u2013404. IEEE Computer Society, Washington (2007)"},{"key":"6_CR5","unstructured":"Childs, A.M., van Dam, W.: Quantum algorithm for a generalized hidden shift problem. In: SODA 2007: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1225\u20131232 (2007)"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1006\/aama.2000.0699","volume":"25","author":"M. Ettinger","year":"2000","unstructured":"Ettinger, M., H\u00f8yer, P.: On quantum algorithms for noncommutative hidden subgroups. Advances in Applied Mathematics\u00a025, 239\u2013251 (2000)","journal-title":"Advances in Applied Mathematics"},{"issue":"1","key":"6_CR7","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.ipl.2004.01.024","volume":"91","author":"M. Ettinger","year":"2004","unstructured":"Ettinger, M., H\u00f8yer, P., Knill, E.: The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters\u00a091(1), 43\u201348 (2004)","journal-title":"Information Processing Letters"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Furst, M.L., Hopcroft, J.E., Luks, E.M.: Polynomial-time algorithms for permutation groups. In: Proceedings of the 21st IEEE Symposium on Foundations of Computer Science, pp. 36\u201341 (1980)","DOI":"10.1109\/SFCS.1980.34"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and orbit coset in quantum computing. In: Proceedings of the 35th ACM Symposium on the Theory of Computing, pp. 1\u20139 (2003)","DOI":"10.1145\/780542.780544"},{"issue":"1","key":"6_CR10","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s00493-004-0009-8","volume":"24","author":"M. Grigni","year":"2004","unstructured":"Grigni, M., Schulman, J., Vazirani, M., Vazirani, U.: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. Combinatorica\u00a024(1), 137\u2013154 (2004)","journal-title":"Combinatorica"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Hallgren, S., Moore, C., R\u00f6tteler, M., Russell, A., Sen, P.: Limitations of quantum coset states for graph isomorphism. In: STOC 2006: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 604\u2013617 (2006)","DOI":"10.1145\/1132516.1132603"},{"issue":"4","key":"6_CR12","doi-asserted-by":"publisher","first-page":"916","DOI":"10.1137\/S009753970139450X","volume":"32","author":"S. Hallgren","year":"2003","unstructured":"Hallgren, S., Russell, A., Ta-Shma, A.: The hidden subgroup problem and quantum computation using group representations. SIAM Journal on Computing\u00a032(4), 916\u2013934 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Jozsa, R.: Quantum factoring, discrete algorithm and the hidden subgroup problem (manuscript, 2000)","DOI":"10.1109\/5992.909000"},{"key":"6_CR14","unstructured":"Kitaev, A.Y.: Quantum measurements and the Abelian Stabilizer problem, quant-ph\/9511026 (1995)"},{"key":"6_CR15","unstructured":"Kempe, J., Shalev, A.: The hidden subgroup problem and permutation group theory. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Vancouver, British Columbia, January 2005, pp. 1118\u20131125 (2005)"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0020-0190(79)90004-8","volume":"8","author":"R. Mathon","year":"1979","unstructured":"Mathon, R.: A note on the graph isomorphism counting problem. Information Processing Letters\u00a08, 131\u2013132 (1979)","journal-title":"Information Processing Letters"},{"key":"6_CR17","unstructured":"Mosca, M.: Quantum Computer Algorithms. PhD thesis, University of Oxford (1999)"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Moore, C., Russell, A., Schulman, L.J.: The symmetric group defies strong fourier sampling. In: FOCS 2005: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 479\u2013490 (2005)","DOI":"10.1109\/SFCS.2005.73"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Moore, C., Russell, A., Sniady, P.: On the impossibility of a quantum sieve algorithm for graph isomorphism. In: STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 536\u2013545 (2007)","DOI":"10.1145\/1250790.1250868"},{"key":"6_CR20","volume-title":"Quantum Computation and Quantum Information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"6_CR21","unstructured":"Quantum pontiff, http:\/\/dabacon.org\/pontiff\/?p=899"},{"issue":"3","key":"6_CR22","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539703440678","volume":"33","author":"O. Regev","year":"2004","unstructured":"Regev, O.: Quantum computation and lattice problems. SIAM Journal on Computing\u00a033(3), 738\u2013760 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR23","unstructured":"Scott, W.R.: Group Theory. Dover Publications, Inc. (1987)"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Sims, C.C.: Computational methods in the study of permutation groups. In: Computational problems in abstract algebra, pp. 169\u2013183 (1970)","DOI":"10.1016\/B978-0-08-012975-4.50020-5"},{"key":"6_CR25","unstructured":"van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. In: Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms, pp. 489\u2013498 (2003)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79228-4_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,9]],"date-time":"2021-09-09T03:03:39Z","timestamp":1631156619000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79228-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540792277","9783540792284"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79228-4_6","relation":{},"subject":[]}}