{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:34:45Z","timestamp":1774593285302,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,10,18]],"date-time":"2008-10-18T00:00:00Z","timestamp":1224288000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1007\/s00453-008-9231-x","type":"journal-article","created":{"date-parts":[[2008,10,17]],"date-time":"2008-10-17T16:20:24Z","timestamp":1224260424000},"page":"490-516","source":"Crossref","is-referenced-by-count":25,"title":["Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem"],"prefix":"10.1007","volume":"55","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","published-online":{"date-parts":[[2008,10,18]]},"reference":[{"key":"9231_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Emerson, J.: Quantum t-designs: t-wise independence in the quantum world. In: Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, pp. 129\u2013140 (2007). Also preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0701126","DOI":"10.1109\/CCC.2007.26"},{"key":"9231_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Kannan, R.: Learning mixtures of arbitrary Gaussians. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 247\u2013257 (2001)","DOI":"10.1145\/380752.380808"},{"key":"9231_CR3","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Kitaev, A., Nisan, N.: Quantum circuits with mixed states. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 20\u201330 (1998)","DOI":"10.1145\/276698.276708"},{"key":"9231_CR4","doi-asserted-by":"crossref","unstructured":"Bacon, D., Childs, A., van Dam, W.: From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 469\u2013478 (2005). Also preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0504083","DOI":"10.1109\/SFCS.2005.38"},{"key":"9231_CR5","unstructured":"Bacon, D., Childs, A., van Dam, W.: Optimal measurements for the dihedral hidden subgroup problem. Chic. J. Theor. Comput. Sci. 2 (2006). Also preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0501044"},{"issue":"5","key":"9231_CR6","doi-asserted-by":"crossref","first-page":"2097","DOI":"10.1063\/1.1459754","volume":"43","author":"H. Barnum","year":"2002","unstructured":"Barnum, H., Knill, E.: Reversing quantum dynamics with near-optimal quantum and classical fidelity. J. Math. Phys. 43(5), 2097\u20132106 (2002). Also preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0004088","journal-title":"J. Math. Phys."},{"key":"9231_CR7","doi-asserted-by":"crossref","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. Adv. Appl. Math. 25, 239\u2013251 (2000). Also preprint at http:\/\/arxiv.org\/abs\/quant-ph\/9807029","journal-title":"Adv. Appl. Math."},{"key":"9231_CR8","unstructured":"Ettinger, M., H\u00f8yer, P., Knill, E.: Hidden subgroup states are almost orthogonal. Preprint at http:\/\/arxiv.org\/abs\/quant-ph\/9901034 (1999)"},{"key":"9231_CR9","volume-title":"Probability Theory and Its Applications","author":"W. Feller","year":"1971","unstructured":"Feller, W.: Probability Theory and Its Applications, vol.\u00a02. Wiley, New York (1971)"},{"issue":"1","key":"9231_CR10","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s00493-004-0009-8","volume":"24","author":"M. Grigni","year":"2004","unstructured":"Grigni, M., Schulman, L., Vazirani, M., Vazirani, U.: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. Combinatorica 24(1), 137\u2013154 (2004)","journal-title":"Combinatorica"},{"key":"9231_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/978-3-540-31856-9_50","volume-title":"Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science","author":"G. Gutoski","year":"2005","unstructured":"Gutoski, G., Watrous, J.: Quantum interactive proofs with competing provers. In: Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 3404, pp. 605\u2013616. Springer, Berlin (2005). Also preprint at http:\/\/arxiv.org\/abs\/cs.CC\/0412102"},{"issue":"4","key":"9231_CR12","doi-asserted-by":"crossref","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 J. Comput. 32(4), 916\u2013934 (2003)","journal-title":"SIAM J. Comput."},{"key":"9231_CR13","doi-asserted-by":"crossref","first-page":"2385","DOI":"10.1080\/09500349414552221","volume":"41","author":"P. Hausladen","year":"1994","unstructured":"Hausladen, P., Wootters, W.: A \u2018pretty good\u2019 measurement for distinguishing quantum states. J. Mod. Opt. 41, 2385\u20132390 (1994)","journal-title":"J. Mod. Opt."},{"key":"9231_CR14","unstructured":"Harrow, A., Winter, A.: How many copies are needed for state discrimination? Preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0606131 (2006)"},{"key":"9231_CR15","unstructured":"Jain, R.: Distinguishing sets of quantum states. Preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0506205 (2005)"},{"key":"9231_CR16","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1137\/040615572","volume":"44","author":"G. Kuperberg","year":"2006","unstructured":"Kuperberg, G.: Numerical cubature using error-correcting codes. SIAM J. Numer. Anal. 44, 897\u2013907 (2006). Also preprint at http:\/\/arxiv.org\/abs\/math\/0402047","journal-title":"SIAM J. Numer. Anal."},{"key":"9231_CR17","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics. Springer, Berlin (2002)"},{"key":"9231_CR18","volume-title":"Random Matrices","author":"M. Mehta","year":"2004","unstructured":"Mehta, M.: Random Matrices. Academic Press, San Diego (2004)"},{"key":"9231_CR19","unstructured":"Moore, C., Russell, A.: For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets. Preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0501177 (2005)"},{"key":"9231_CR20","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 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1113\u20131122 (2004). Journal version in preparation, preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0503095"},{"key":"9231_CR21","doi-asserted-by":"crossref","unstructured":"Moore, C., Russell, A., Schulman, L.: The symmetric group defies strong Fourier sampling. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 479\u2013488 (2005). Also preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0501056","DOI":"10.1109\/SFCS.2005.73"},{"key":"9231_CR22","volume-title":"Quantum Computation and Quantum Information","author":"M. Nielsen","year":"2000","unstructured":"Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"9231_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1399","DOI":"10.1007\/11523468_113","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages and Programming","author":"J. Radhakrishnan","year":"2005","unstructured":"Radhakrishnan, J., R\u00f6tteler, M., Sen, P.: On the power of random bases in Fourier sampling: hidden subgroup problem in the Heisenberg group. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 3580, pp. 1399\u20131411. Springer, Berlin (2005). Also preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0503114"},{"key":"9231_CR24","unstructured":"Sen, P.: Random measurement bases, quantum state distinction and applications to the hidden subgroup problem. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, pp. 274\u2013287 (2006). Also preprint at http:\/\/arxiv.org\/abs\/quant-ph\/0512085"},{"key":"9231_CR25","series-title":"Graduate Texts in Mathematics","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. Graduate Texts in Mathematics. Springer, Berlin (1977)"},{"issue":"3","key":"9231_CR26","doi-asserted-by":"crossref","first-page":"2545","DOI":"10.1007\/BF01121471","volume":"35","author":"I. Shiganov","year":"1986","unstructured":"Shiganov, I.: Refinement of the upper bound of the constant in the central limit theorem. J. Sov. Math. 35(3), 2545\u20132550 (1986)","journal-title":"J. Sov. Math."},{"issue":"5","key":"9231_CR27","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P. Shor","year":"1997","unstructured":"Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"9231_CR28","unstructured":"Tsirelson, B.: Gaussian measures and Gaussian processes. Lecture 3 of course notes available at http:\/\/www.tau.ac.il\/~tsirel\/Courses\/Gaussian\/syllabus.html (2005)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9231-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9231-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9231-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,2]],"date-time":"2025-02-02T02:58:57Z","timestamp":1738465137000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9231-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,18]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["9231"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9231-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,18]]}}}