{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T09:29:33Z","timestamp":1759742973447,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_8","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"86-97","source":"Crossref","is-referenced-by-count":6,"title":["Limitations on Quantum Dimensionality Reduction"],"prefix":"10.1007","author":[{"given":"Aram W.","family":"Harrow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashley","family":"Montanaro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony J.","family":"Short","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2005.v001a001","volume":"1","author":"S. Aaronson","year":"2004","unstructured":"Aaronson, S.: Limitations of quantum advice and one-way communication. Theory of Computing\u00a01, 1\u201328 (2004), quant-ph\/0402095","journal-title":"Theory of Computing"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Emerson, J.: Quantum t-designs: t-wise independence in the quantum world. In: Proc. 22nd Annual IEEE Conf. Computational Complexity, pp. 129\u2013140 (2007), quant-ph\/0701126","DOI":"10.1109\/CCC.2007.26"},{"key":"8_CR3","unstructured":"Aubrun, G., Szarek, S., Werner, E.: Hastings\u2019 additivity counterexample via Dvoretzky\u2019s theorem (2010), arXiv:1003.4925"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"22102","DOI":"10.1063\/1.3271044","volume":"51","author":"G. Aubrun","year":"2010","unstructured":"Aubrun, G., Szarek, S., Werner, E.: Non-additivity of Renyi entropy and Dvoretzky\u2019s theorem. J. Math. Phys.\u00a051, 022102 (2010), arXiv:0910.1189","journal-title":"J. Math. Phys."},{"issue":"2","key":"8_CR5","doi-asserted-by":"publisher","first-page":"27901","DOI":"10.1103\/PhysRevLett.91.027901","volume":"91","author":"S. Bartlett","year":"2003","unstructured":"Bartlett, S., Rudolph, T., Spekkens, R.: Classical and quantum communication without a shared reference frame. Phys. Rev. Lett.\u00a091(2), 027901 (2003), quant-ph\/0302111","journal-title":"Phys. Rev. Lett."},{"issue":"5","key":"8_CR6","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1145\/1089023.1089026","volume":"52","author":"B. Brinkman","year":"2005","unstructured":"Brinkman, B., Charikar, M.: On the impossibility of dimension reduction in \u21131. J. ACM\u00a052(5), 766\u2013788 (2005)","journal-title":"J. ACM"},{"issue":"16","key":"8_CR7","doi-asserted-by":"publisher","first-page":"167902","DOI":"10.1103\/PhysRevLett.87.167902","volume":"87","author":"H. Buhrman","year":"2001","unstructured":"Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett.\u00a087(16), 167902 (2001), quant-ph\/0102001","journal-title":"Phys. Rev. Lett."},{"key":"8_CR8","unstructured":"Charikar, M., Sahai, A.: Dimension reduction in the \u21131 norm. In: Proc. 43rd Annual Symp. Foundations of Computer Science, pp. 551\u2013560 (2002)"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Cleve, R., H\u00f8yer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. In: Proc. 19th Annual IEEE Conf. Computational Complexity, pp. 236\u2013249 (2004), quant-ph\/0404076","DOI":"10.1109\/CCC.2004.1313847"},{"key":"8_CR10","unstructured":"Fawzi, O., Hayden, P., Sen, P.: From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking (2010), arXiv:1010.3007"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Gavinsky, D., Kempe, J., de Wolf, R.: Strengths and weaknesses of quantum fingerprinting. In: Proc. 21st Annual IEEE Conf. Computational Complexity, pp. 288\u2013298 (2006), quant-ph\/0603173","DOI":"10.1109\/CCC.2006.39"},{"key":"8_CR12","unstructured":"Harrow, A.W., Montanaro, A., Short, A.J.: Limitations on quantum dimensionality reduction (2010), arXiv:1012.2262"},{"key":"8_CR13","unstructured":"Hayden, P., Winter, A.: The fidelity alternative and quantum measurement simulation (2010), arXiv:1003.4994"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: Proc. 42nd Annual Symp. Foundations of Computer Science, pp. 10\u201333 (2001)","DOI":"10.1109\/SFCS.2001.959878"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proc. 30th Annual ACM Symp. Theory of Computing, pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W. Johnson","year":"1984","unstructured":"Johnson, W., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"key":"8_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. In: Proc. 30th Annual ACM Symp. Theory of Computing, pp. 614\u2013623 (1998)","DOI":"10.1145\/276698.276877"},{"issue":"3","key":"8_CR19","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1007\/s00220-009-0890-5","volume":"291","author":"W. Matthews","year":"2009","unstructured":"Matthews, W., Wehner, S., Winter, A.: Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding. Comm. Math. Phys.\u00a0291(3), 813\u2013843 (2009), arXiv:0810.2327","journal-title":"Comm. Math. Phys."},{"key":"8_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":"8_CR21","unstructured":"Sen, P.: Random measurement bases, quantum state distinction and applications to the hidden subgroup problem. In: Proc. 21st Annual IEEE Conf. Computational Complexity, p. 287 (2006), quant-ph\/0512085"},{"key":"8_CR22","unstructured":"Watrous, J.: Theory of quantum information lecture notes (2008), http:\/\/www.cs.uwaterloo.ca\/~watrous\/quant-info\/"},{"key":"8_CR23","unstructured":"Winter, A.: Quantum and classical message identification via quantum channels. In: Hirota, O. (ed.) Festschrift \u201cA S Holevo 60\u201d, pp. 171\u2013188 (2004), quant-ph\/0401060"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T11:29:38Z","timestamp":1741260578000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}