{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T00:45:13Z","timestamp":1769561113058,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T00:00:00Z","timestamp":1550620800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["Finance Code 001"],"award-info":[{"award-number":["Finance Code 001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","award":["E-26\/203.235\/2016"],"award-info":[{"award-number":["E-26\/203.235\/2016"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s11128-019-2208-7","type":"journal-article","created":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T05:25:36Z","timestamp":1550640336000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fourier 1-norm and quantum speed-up"],"prefix":"10.1007","volume":"18","author":[{"given":"Sebasti\u00e1n Alberto","family":"Grillo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9712-1930","authenticated-orcid":false,"given":"Franklin","family":"de Lima Marquezino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,2,20]]},"reference":[{"key":"2208_CR1","unstructured":"Aaronson, S.: Limitations of quantum advice and one-way communication. In: Proceedings of 19th IEEE Annual Conference on Computational Complexity, pp. 320\u2013332. IEEE (2004)"},{"key":"2208_CR2","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: BQP and the polynomial hierarchy. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 141\u2013150. ACM (2010)","DOI":"10.1145\/1806689.1806711"},{"issue":"6","key":"2208_CR3","doi-asserted-by":"publisher","first-page":"133","DOI":"10.4086\/toc.2014.v010a006","volume":"10","author":"S Aaronson","year":"2014","unstructured":"Aaronson, S., Ambainis, A.: The need for structure in quantum speedups. Theory Comput. 10(6), 133\u2013166 (2014)","journal-title":"Theory Comput."},{"key":"2208_CR4","doi-asserted-by":"publisher","unstructured":"Aaronson, S., Ambainis, A., Iraids, J., Kokainis, M., Smotrovs, J.: Polynomials, quantum query complexity, and Grothendieck\u2019s inequality. In: Proceedings of the 31st Conference on Computational Complexity, CCC\u201916, pp. 25:1\u201325:19. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Germany (2016). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2016.25","DOI":"10.4230\/LIPIcs.CCC.2016.25"},{"key":"2208_CR5","doi-asserted-by":"publisher","unstructured":"Abbott, A.A., Calude, C.S.: Understanding the quantum computational speed-up via de-quantisation. In: Cooper, S.B., Panangaden, P., Kashefi, E. (eds.) Proceedings Sixth Workshop on Developments in Computational Models: Causality, Computation, and Physics, Edinburgh, Scotland, 9\u201310th July 2010, Electronic Proceedings in Theoretical Computer Science, vol.\u00a026, pp. 1\u201312. Open Publishing Association (2010). https:\/\/doi.org\/10.4204\/EPTCS.26.1","DOI":"10.4204\/EPTCS.26.1"},{"issue":"1","key":"2208_CR6","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210\u2013239 (2007)","journal-title":"SIAM J. Comput."},{"issue":"5\u20136","key":"2208_CR7","first-page":"435","volume":"15","author":"A Ambainis","year":"2015","unstructured":"Ambainis, A., Gruska, J., Zheng, S.: Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Inf. Comput. 15(5\u20136), 435\u2013452 (2015)","journal-title":"Quantum Inf. Comput."},{"issue":"2","key":"2208_CR8","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D Angluin","year":"1979","unstructured":"Angluin, D., Valiant, L.G.: Fast probabilistic algorithms for hamiltonian circuits and matchings. J. Comput. Syst. Sci. 18(2), 155\u2013193 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"2208_CR9","doi-asserted-by":"publisher","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum query complexity and semi-definite programming. In: Proceedings of the 18th IEEE Annual Conference on Computational Complexity, pp. 179\u2013193 (2003). https:\/\/doi.org\/10.1109\/CCC.2003.1214419","DOI":"10.1109\/CCC.2003.1214419"},{"issue":"4","key":"2208_CR10","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., De Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48(4), 778\u2013797 (2001)","journal-title":"J. ACM"},{"issue":"3","key":"2208_CR11","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1103\/RevModPhys.38.447","volume":"38","author":"JS Bell","year":"1966","unstructured":"Bell, J.S.: On the problem of hidden variables in quantum mechanics. Rev. Mod. Phys. 38(3), 447 (1966)","journal-title":"Rev. Mod. Phys."},{"issue":"1","key":"2208_CR12","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H Buhrman","year":"2002","unstructured":"Buhrman, H., De Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21\u201343 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"2208_CR13","doi-asserted-by":"publisher","first-page":"050502","DOI":"10.1103\/PhysRevLett.100.050502","volume":"100","author":"A Datta","year":"2008","unstructured":"Datta, A., Shaji, A., Caves, C.M.: Quantum discord and the power of one qubit. Phys. Rev. Lett. 100(5), 050502 (2008)","journal-title":"Phys. Rev. Lett."},{"issue":"4","key":"2208_CR14","doi-asserted-by":"publisher","first-page":"042310","DOI":"10.1103\/PhysRevA.75.042310","volume":"75","author":"A Datta","year":"2007","unstructured":"Datta, A., Vidal, G.: Role of entanglement and correlations in mixed-state quantum computation. Phys. Rev. A 75(4), 042310 (2007)","journal-title":"Phys. Rev. A"},{"key":"2208_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.gs.2008.001","volume":"1","author":"R Wolf De","year":"2008","unstructured":"De Wolf, R.: A brief introduction to fourier analysis on the Boolean cube. Theory Comput. Grad. Surv. 1, 1\u201320 (2008)","journal-title":"Theory Comput. Grad. Surv."},{"key":"2208_CR16","doi-asserted-by":"crossref","unstructured":"Deutsch, D.: Quantum theory, the Church\u2013Turing principle and the universal quantum computer. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 400, pp. 97\u2013117. The Royal Society (1985)","DOI":"10.1098\/rspa.1985.0070"},{"key":"2208_CR17","doi-asserted-by":"crossref","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 439, pp. 553\u2013558. The Royal Society (1992)","DOI":"10.1098\/rspa.1992.0167"},{"key":"2208_CR18","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2018.03.017","volume":"736","author":"S Grillo","year":"2018","unstructured":"Grillo, S., Marquezino, F.: Quantum query as a state decomposition. Theor. Comput. Sci. 736, 62\u201375 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.03.017","journal-title":"Theor. Comput. Sci."},{"issue":"7505","key":"2208_CR19","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1038\/nature13460","volume":"510","author":"M Howard","year":"2014","unstructured":"Howard, M., Wallman, J., Veitch, V., Emerson, J.: Contextuality supplies the \u2019magic\u2019 for quantum computation. Nature 510(7505), 351\u2013355 (2014)","journal-title":"Nature"},{"key":"2208_CR20","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1093\/oso\/9780198500599.003.0027","volume-title":"The Geometric Universe: Science, Geometry, and the Work of Roger Penrose","author":"R Jozsa","year":"1998","unstructured":"Jozsa, R.: Entanglement and quantum computation. In: Huggett, S.A., Mason, L.J., Tod, K.P., Tsou, S.T., Woodhouse, N.M.J. (eds.) The Geometric Universe: Science, Geometry, and the Work of Roger Penrose, vol. 27, pp. 369\u2013379. Oxford University Press, Oxford (1998)"},{"key":"2208_CR21","doi-asserted-by":"crossref","unstructured":"Jozsa, R., Linden, N.: On the role of entanglement in quantum-computational speed-up. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 459, pp. 2011\u20132032. The Royal Society (2003)","DOI":"10.1098\/rspa.2002.1097"},{"issue":"25","key":"2208_CR22","doi-asserted-by":"publisher","first-page":"5672","DOI":"10.1103\/PhysRevLett.81.5672","volume":"81","author":"E Knill","year":"1998","unstructured":"Knill, E., Laflamme, R.: Power of one bit of quantum information. Phys. Rev. Lett. 81(25), 5672 (1998)","journal-title":"Phys. Rev. Lett."},{"key":"2208_CR23","doi-asserted-by":"publisher","unstructured":"Kochen, S., Specker, E.P.: The problem of hidden variables in quantum mechanics. In: Hooker, C.A. (eds.) The Logico-Algebraic Approach to Quantum Mechanics, vol. 5a, pp. 293\u2013328. Springer, Dordrecht (1975). https:\/\/doi.org\/10.1007\/978-94-010-1795-4_17","DOI":"10.1007\/978-94-010-1795-4_17"},{"issue":"12","key":"2208_CR24","doi-asserted-by":"publisher","first-page":"122206","DOI":"10.1063\/1.4769269","volume":"53","author":"A Montanaro","year":"2012","unstructured":"Montanaro, A.: Some applications of hypercontractive inequalities in quantum information theory. J. Math. Phys. 53(12), 122206 (2012)","journal-title":"J. Math. Phys."},{"key":"2208_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)"},{"issue":"3","key":"2208_CR26","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/2493252.2493256","volume":"5","author":"M Ozols","year":"2013","unstructured":"Ozols, M., Roetteler, M., Roland, J.: Quantum rejection sampling. ACM Trans. Comput. Theory 5(3), 11 (2013)","journal-title":"ACM Trans. Comput. Theory"},{"key":"2208_CR27","doi-asserted-by":"crossref","unstructured":"Reichardt, B.W., Spalek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 103\u2013112. ACM (2008)","DOI":"10.1145\/1374376.1374394"},{"key":"2208_CR28","doi-asserted-by":"crossref","unstructured":"R\u00f6tteler, M.: Quantum algorithms for highly non-linear Boolean functions. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 448\u2013457. SIAM (2010)","DOI":"10.1137\/1.9781611973075.37"},{"issue":"14","key":"2208_CR29","doi-asserted-by":"publisher","first-page":"147902","DOI":"10.1103\/PhysRevLett.91.147902","volume":"91","author":"G Vidal","year":"2003","unstructured":"Vidal, G.: Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett. 91(14), 147902 (2003)","journal-title":"Phys. Rev. Lett."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-019-2208-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-019-2208-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-019-2208-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,14]],"date-time":"2024-07-14T22:54:10Z","timestamp":1720997650000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-019-2208-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,20]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["2208"],"URL":"https:\/\/doi.org\/10.1007\/s11128-019-2208-7","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,20]]},"assertion":[{"value":"27 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"99"}}