{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:09:02Z","timestamp":1725559742261},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540275800"},{"type":"electronic","value":"9783540316916"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11523468_113","type":"book-chapter","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T18:58:59Z","timestamp":1279479539000},"page":"1399-1411","source":"Crossref","is-referenced-by-count":11,"title":["On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group"],"prefix":"10.1007","author":[{"given":"Jaikumar","family":"Radhakrishnan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"R\u00f6tteler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranab","family":"Sen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"113_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The probabilistic method. John Wiley and Sons, Chichester (2000)"},{"key":"113_CR2","unstructured":"Bacon, D., Childs, A., van Dam, W.: From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. ArXiv preprint quant\u2013ph\/0504083 (2005)"},{"key":"113_CR3","volume-title":"Representation Theory of Finite Groups and Algebras","author":"W.C. Curtis","year":"1962","unstructured":"Curtis, W.C., Reiner, I.: Representation Theory of Finite Groups and Algebras. Wiley and Sons, Chichester (1962)"},{"issue":"1","key":"113_CR4","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); See also ArXiv preprint quant\u2013ph\/0401083","journal-title":"Information Processing Letters"},{"key":"113_CR5","doi-asserted-by":"crossref","unstructured":"Emerson, J.: Random quantum circuits and pseudo-random operators: theory and applications. ArXiv preprint quant\u2013ph\/0410087 (2004)","DOI":"10.1063\/1.1834400"},{"key":"113_CR6","doi-asserted-by":"publisher","first-page":"2098","DOI":"10.1126\/science.1090790","volume":"302","author":"J. Emerson","year":"2003","unstructured":"Emerson, J., Weinstein, Y., Saraceno, M., Lloyd, S., Cory, D.: Pseudo-Random unitary operators for quantum information processing. Science\u00a0302, 2098\u20132100 (2003)","journal-title":"Science"},{"key":"113_CR7","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 Symposium on Theory of Computing (STOC), pp. 1\u20139 (2003)","DOI":"10.1145\/780542.780544"},{"issue":"3","key":"113_CR8","doi-asserted-by":"crossref","first-page":"229","DOI":"10.26421\/QIC4.3-8","volume":"4","author":"D. Gavinsky","year":"2004","unstructured":"Gavinsky, D.: Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups. Quantum Information and Computation\u00a04(3), 229\u2013235 (2004)","journal-title":"Quantum Information and Computation"},{"key":"113_CR9","doi-asserted-by":"crossref","unstructured":"Grigni, M., Schulman, L., Vazirani, M., Vazirani, U.: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. Combinatorica, 137\u2013154 (2004)","DOI":"10.1007\/s00493-004-0009-8"},{"issue":"4","key":"113_CR10","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":"113_CR11","doi-asserted-by":"crossref","unstructured":"Ivanyos, G., Magniez, F., Santha, M.: Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. International Journal of Foundations of Computer Science, 723\u2013740 (2003)","DOI":"10.1142\/S0129054103001996"},{"key":"113_CR12","unstructured":"Ip, L.: Shor\u2019s algorithm is optimal (2003) (unpublished manuscript)"},{"key":"113_CR13","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. ArXiv preprint quant\u2013ph\/0302112 (2003)"},{"key":"113_CR14","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139172769","volume-title":"Introduction to finite fields and their applications","author":"R. Lidl","year":"1994","unstructured":"Lidl, R., Niederreiter, H.: Introduction to finite fields and their applications, 2nd edn. Cambridge University Press, Cambridge (1994)","edition":"2"},{"key":"113_CR15","volume-title":"Graduate Texts in Mathematics","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. In: Graduate Texts in Mathematics. Springer, Heidelberg (2002)"},{"key":"113_CR16","unstructured":"Moore, C., Russell, A.: For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets. ArXiv preprint quant\u2013ph\/0501177 (2005)"},{"key":"#cr-split#-113_CR17.1","unstructured":"Moore, C., Rockmore, D., Russell, A., Schulman, L.: The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 1113\u20131122 (2004);"},{"key":"#cr-split#-113_CR17.2","unstructured":"ArXiv preprint quant\u2013ph\/0503095"},{"key":"113_CR18","unstructured":"Moore, C., Russell, A., Schulman, L.: The symmetric group defies strong Fourier sampling: Part I. ArXiv preprint quant\u2013ph\/0501056 (2005)"},{"key":"113_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9458-7","volume-title":"Linear Representations of Finite Groups","author":"J.P. Serre","year":"1977","unstructured":"Serre, J.P.: Linear Representations of Finite Groups. Springer, Heidelberg (1977)"},{"issue":"2","key":"113_CR20","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0003-4916(89)90322-9","volume":"191","author":"W. Wootters","year":"1989","unstructured":"Wootters, W., Fields, B.: Optimal state-determination by mutually unbiased measurements. Ann. Physics\u00a0191(2), 363\u2013381 (1989)","journal-title":"Ann. Physics"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11523468_113.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,31]],"date-time":"2021-10-31T18:55:31Z","timestamp":1635706531000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11523468_113"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540275800","9783540316916"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11523468_113","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}