{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T17:28:11Z","timestamp":1767374891613,"version":"3.37.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2010,6]]},"DOI":"10.1007\/s11128-009-0129-6","type":"journal-article","created":{"date-parts":[[2009,9,21]],"date-time":"2009-09-21T22:31:13Z","timestamp":1253572273000},"page":"321-341","source":"Crossref","is-referenced-by-count":11,"title":["The geometry of quantum learning"],"prefix":"10.1007","volume":"9","author":[{"given":"Markus","family":"Hunziker","sequence":"first","affiliation":[]},{"given":"David A.","family":"Meyer","sequence":"additional","affiliation":[]},{"given":"Jihun","family":"Park","sequence":"additional","affiliation":[]},{"given":"James","family":"Pommersheim","sequence":"additional","affiliation":[]},{"given":"Mitch","family":"Rothstein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,9,23]]},"reference":[{"key":"129_CR1","first-page":"124","volume-title":"Proceedings of the 35th Symposium on Foundations of Computer Science, Santa Fe, NM, 20\u201322 November 1994","author":"P.W. Shor","year":"1994","unstructured":"Shor P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Goldwasser, S. (eds) Proceedings of the 35th Symposium on Foundations of Computer Science, Santa Fe, NM, 20\u201322 November 1994, pp. 124\u2013134. IEEE, Los Alamitos, CA (1994)"},{"key":"129_CR2","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, quant-ph\/9508027. SIAM J. Comput. 26, 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"129_CR3","unstructured":"Coppersmith, D.: An approximate Fourier transform useful in quantum factoring. IBM T. J. Watson Research Report RC 19642 (1994)"},{"key":"129_CR4","unstructured":"H\u00f8yer, P.: Efficient quantum transforms, quant-ph\/9702028 (preprint 1997)"},{"key":"129_CR5","first-page":"703","volume-title":"Wavelet Applications in Signal and Image Processing VII, Denver, CO, 19\u201323 July 1999, SPIE Proceedings, vol. 3813","author":"A. Klappenecker","year":"1999","unstructured":"Klappenecker A.: Wavelets and wavelet packets on quantum computers, quant-ph\/9909014. In: Unser, M.A., Aldroubi, A., Laine, A.F. (eds) Wavelet Applications in Signal and Image Processing VII, Denver, CO, 19\u201323 July 1999, SPIE Proceedings, vol. 3813, pp. 703\u2013713. SPIE, Bellingham, WA (1999)"},{"key":"129_CR6","first-page":"464","volume-title":"Proceedings of the 2nd International Symposium on Image and Signal Processing and Analysis, Pula, Croatia, 19\u201321 June 2001","author":"A. Klappenecker","year":"2001","unstructured":"Klappenecker A., R\u00f6tteler M.: Discrete cosine transforms on quantum computers, quant-ph\/0111038. In: Loncaric, S., Babic, H. (eds) Proceedings of the 2nd International Symposium on Image and Signal Processing and Analysis, Pula, Croatia, 19\u201321 June 2001, pp. 464\u2013468. IEEE, Los Alamitos, CA (2001)"},{"key":"129_CR7","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s102080010020","volume":"2","author":"M.H. Freedman","year":"2002","unstructured":"Freedman M.H.: Poly-locality in quantum computing, quant-ph\/0001077. Found. Comput. Math. 2, 145\u2013154 (2002)","journal-title":"Found. Comput. Math."},{"key":"129_CR8","doi-asserted-by":"crossref","unstructured":"Grover L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, 22\u201324 May 1996, pp. 212\u2013219. ACM, New York (1996)","DOI":"10.1145\/237814.237866"},{"key":"129_CR9","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"L.K. Grover","year":"1997","unstructured":"Grover L.K.: Quantum mechanics helps in searching for a needle in a haystack, quant-ph\/9706033. Phys. Rev. Lett. 79, 325\u2013328 (1997)","journal-title":"Phys. Rev. Lett."},{"key":"129_CR10","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P.: An exact quantum polynomial-time algorithm for Simon\u2019s problem, quant-ph\/9704027. In: Proceedings of 5th Israeli Symposium on Theory of Computing and Systems, Ramat-Gan, Israel 17\u201319 June 1997, pp. 12\u201323. IEEE, Los Alamitos, CA (1997)","DOI":"10.1109\/ISTCS.1997.595153"},{"key":"129_CR11","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A framework for fast quantum mechanical algorithms, quant-ph\/ 9711043. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, 23\u201326 May 1998, pp. 53\u201362. ACM, New York (1998)","DOI":"10.1145\/276698.276712"},{"key":"129_CR12","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Tapp, A.: Quantum counting, quant-ph\/9805082. In: Proceedings of the 25th International Colloquium on Automata, Languages, and Programming, \u00c5lborg, Denmark, 13\u201317 July 1998. Lecture Notes in Computer Science, vol. 1443, pp. 820\u2013831. Springer-Verlag, Berlin (1998)","DOI":"10.1007\/BFb0055105"},{"key":"129_CR13","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., and Tapp, A.: Quantum amplitude amplification and estimation, quant-ph\/0005055. In: Lomonaco, S.J. Jr., Brandt, H.E. (eds.) Quantum Computation and Information, Contemporary Mathematics, vol. 305, pp. 53\u201374. AMS, Providence, RI (2002)","DOI":"10.1090\/conm\/305\/05215"},{"key":"129_CR14","doi-asserted-by":"crossref","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. In: Proceedings of the 25th ACM Symposium on Theory of Computing, San Diego, CA, 16\u201318 May 1993, pp. 11\u201320. ACM Press, New York (1993)","DOI":"10.1145\/167088.167097"},{"key":"129_CR15","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein E., Vazirani U.: Quantum complexity theory. SIAM J. Comput. 26, 1411\u20131473 (1997)","journal-title":"SIAM J. Comput."},{"key":"129_CR16","volume-title":"Machine Learning","author":"T.M. Mitchell","year":"1997","unstructured":"Mitchell T.M.: Machine Learning. McGraw-Hill, San Francisco (1997)"},{"key":"129_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-01-00923-5","volume":"39","author":"F.S. Cucker","year":"2002","unstructured":"Cucker F.S., Smale S.: On the mathematical foundations of learning. Bull. Amer. Math. Soc. 39, 1\u201349 (2002)","journal-title":"Bull. Amer. Math. Soc."},{"key":"129_CR18","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Computational learning theory: survey and selected bibliography. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 4\u20136 May 1992, pp. 351\u2013369. ACM, New York (1992)","DOI":"10.1145\/129712.129746"},{"key":"129_CR19","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin D.: Queries and concept learning. Mach. Learn. 2, 319\u2013342 (1988)","journal-title":"Mach. Learn."},{"key":"129_CR20","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"129_CR21","doi-asserted-by":"crossref","first-page":"2014","DOI":"10.1103\/PhysRevLett.85.2014","volume":"85","author":"D.A. Meyer","year":"2000","unstructured":"Meyer D.A.: Sophisticated quantum search without entanglement, quant-ph\/0007070. Phys. Rev. Lett. 85, 2014\u20132017 (2000)","journal-title":"Phys. Rev. Lett."},{"key":"129_CR22","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1098\/rspa.1998.0164","volume":"454","author":"R. Cleve","year":"1998","unstructured":"Cleve R., Ekert A., Macchiavello C., Mosca M.: Quantum algorithms revisited, quant-ph\/9708016. Proc. Roy. Soc. Lond. A. 454, 339\u2013354 (1998)","journal-title":"Proc. Roy. Soc. Lond. A."},{"key":"129_CR23","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1080\/14786446708639914","volume":"34","author":"J.J. Sylvester","year":"1867","unstructured":"Sylvester J.J.: Thoughts on inverse orthogonal matrices, simultaneous sign-successions, and tesselated pavements in two or more colours, with applications to Newton\u2019s rule, ornamental tile-work, and the theory of numbers. Philos. Mag. ser. IV. 34, 461\u2013475 (1867)","journal-title":"Philos. Mag. ser. IV."},{"key":"129_CR24","first-page":"240","volume":"17","author":"M.J. Hadamard","year":"1893","unstructured":"Hadamard M.J.: R\u00e9solution d\u2019une question relative aux d\u00e9terminants. Bull. Sci. Math. 17, 240\u2013246 (1893)","journal-title":"Bull. Sci. Math."},{"key":"129_CR25","unstructured":"van Dam, W.: Quantum algorithms for weighing matrices and quadratic residues, quant-ph\/0008059. Algorithmica OF1-OF16 (2002)"},{"key":"129_CR26","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C.H. Bennett","year":"1997","unstructured":"Bennett C.H., Bernstein E., Brassard G., Vazirani U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 1510\u20131523 (1997)","journal-title":"SIAM J. Comput."},{"key":"129_CR27","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/S0019-9958(67)90302-6","volume":"10","author":"C.W. Helstrom","year":"1967","unstructured":"Helstrom C.W.: Detection theory and quantum mechanics. Inf. Control. 10, 254\u2013291 (1967)","journal-title":"Inf. Control."},{"key":"129_CR28","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0047-259X(73)90028-6","volume":"3","author":"A.S. Kholevo","year":"1973","unstructured":"Kholevo A.S.: Quantum statistical decision theory. J. Multivar. Anal. 3, 337\u2013394 (1973)","journal-title":"J. Multivar. Anal."},{"key":"129_CR29","unstructured":"von Neumann, J.: Mathematische Grundlagen der Quantenmechanik (Translated by Beyer, R.T. as Mathematical Foundations of Quantum Mechanics. Princeton University Press, Princeton 1955). Springer-Verlag, Berlin (1932)"},{"key":"129_CR30","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1080\/17442507508833114","volume":"1","author":"V.P. Belavkin","year":"1975","unstructured":"Belavkin V.P.: Optimal multiple quantum statistical hypothesis testing. Stochastics. 1, 315\u2013345 (1975)","journal-title":"Stochastics."},{"key":"129_CR31","unstructured":"Kennedy R.S.: On the optimal receiver for the M-ary pure state problem. MIT Res. Lab. Electron. Quart. Prog. Rep. 110 (15 July 1973) 142\u2013146; see also [32], Appendix to Chap. IV"},{"key":"129_CR32","volume-title":"Quantum Detection and Estimation Theory","author":"C.W. Helstrom","year":"1976","unstructured":"Helstrom C.W.: Quantum Detection and Estimation Theory. Academic, New York (1976)"},{"key":"129_CR33","doi-asserted-by":"crossref","first-page":"1770","DOI":"10.1109\/PROC.1970.8004","volume":"58","author":"H.P. Yuen","year":"1970","unstructured":"Yuen H.P., Kennedy R.S.: On optimal quantum receivers for digital signal detection. Proc. IEEE 58, 1770\u20131773 (1970)","journal-title":"Proc. IEEE"},{"key":"129_CR34","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge, p. 432, Theorem 7.4.9 (1985)"},{"key":"129_CR35","doi-asserted-by":"crossref","first-page":"858","DOI":"10.1109\/18.915636","volume":"47","author":"Y.C. Eldar","year":"2001","unstructured":"Eldar Y.C., Forney G.D. Jr: On quantum detection and the square-root measurement, quant-ph\/0001532. IEEE Trans. Inf. Theory. 47, 858\u2013872 (2001)","journal-title":"IEEE Trans. Inf. Theory."},{"key":"129_CR36","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, 2097\u20132106 (2002)","journal-title":"J. Math. Phys."},{"key":"129_CR37","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M. Boyer","year":"1998","unstructured":"Boyer M., Brassard G., H\u00f8yer P., Tapp A.: Tight bounds on quantum searching, quant-ph\/ 9605034. Fortsch. Phys. 46, 493\u2013506 (1998)","journal-title":"Fortsch. Phys."},{"key":"129_CR38","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1137\/S0097539795293123","volume":"28","author":"N.H. Bshouty","year":"1999","unstructured":"Bshouty N.H., Jackson J.C.: Learning DNF over the uniform distribution using a quantum example oracle. SIAM J. Comput. 28, 1136\u20131153 (1999)","journal-title":"SIAM J. Comput."},{"key":"129_CR39","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant L.G.: A theory of the learnable. Commun. ACM. 27, 1134\u20131142 (1984)","journal-title":"Commun. ACM."},{"key":"129_CR40","doi-asserted-by":"crossref","unstructured":"Servedio, R.A., Gortler S.J.: Quantum versus classical learnability. In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, IL, 18\u201321 June 2001, pp. 138\u2013148. IEEE, Los Alamitos, CA (2001)","DOI":"10.1109\/CCC.2001.933881"},{"key":"129_CR41","first-page":"105","volume-title":"Proceedings of STACS 2004, Lecture Notes in Computer Science, vol. 2996","author":"A. Ambainis","year":"2004","unstructured":"Ambainis A., Iwama K., Kawachi A., Masuda H., Putra R.H., Yamashita S.: Quantum identification of Boolean oracles. In: Diekert, V., Habib, M. (eds) Proceedings of STACS 2004, Lecture Notes in Computer Science, vol. 2996, pp. 105\u2013116. Springer, Berlin (2004)"},{"key":"129_CR42","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s11128-005-0001-2","volume":"4","author":"A. Atici","year":"2005","unstructured":"Atici A., Servedio R.: Improved bounds on quantum learning algorithms. Quant. Inf. Proc. 4, 355\u2013386 (2005)","journal-title":"Quant. Inf. Proc."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-009-0129-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T08:25:05Z","timestamp":1739348705000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-009-0129-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,23]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["129"],"URL":"https:\/\/doi.org\/10.1007\/s11128-009-0129-6","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2009,9,23]]}}}