{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:58Z","timestamp":1781077558012,"version":"3.54.1"},"reference-count":40,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T00:00:00Z","timestamp":1731888000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"e European Union\u2019s Horizon 2020","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>A surprising &amp;apos;converse to the polynomial method&amp;apos; of Aaronson et al. (CCC&amp;apos;16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorithm up to a universal multiplicative factor related to the famous Grothendieck constant. Here we show that such a result does not generalize to quartic polynomials and 2-query algorithms, even when we allow for additive approximations. We also show that the additive approximation implied by their result is tight for bounded bilinear forms, which gives a new characterization of the Grothendieck constant in terms of 1-query quantum algorithms. Along the way we provide reformulations of the completely bounded norm of a form, and its dual norm.<\/jats:p>","DOI":"10.22331\/q-2024-11-18-1526","type":"journal-article","created":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T16:36:21Z","timestamp":1731947781000},"page":"1526","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Grothendieck inequalities characterize converses to the polynomial method"],"prefix":"10.22331","volume":"8","author":[{"given":"Jop","family":"Bri\u00ebt","sequence":"first","affiliation":[{"name":"CWI & QuSoft, Science Park 123, 1098 XG Amsterdam, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francisco","family":"Escudero Guti\u00e9rrez","sequence":"additional","affiliation":[{"name":"CWI & QuSoft, Science Park 123, 1098 XG Amsterdam, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sander","family":"Gribling","sequence":"additional","affiliation":[{"name":"Tilburg University, Warandelaan 2, 5037 AB Tilburg, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2024,11,18]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Scott Aaronson, Andris Ambainis, J\u0101nis Iraids, Martins Kokainis, and Juris Smotrovs. Polynomials, quantum query complexity, and Grothendieck&apos;s inequality. In 31st Conference on Computational Complexity, CCC 2016, pages 25:1\u201325:19, 2016. arXiv:1511.08682. URL: https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2016.25.","DOI":"10.4230\/LIPIcs.CCC.2016.25"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4), 2021. URL: https:\/\/doi.org\/10.1145\/3488559.","DOI":"10.1145\/3488559"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Andris Ambainis and Aleksandrs Belovs. An exponential separation between quantum query complexity and the polynomial degree. In Proceedings of the Conference on Proceedings of the 38th Computational Complexity Conference, CCC &apos;23, Dagstuhl, DEU, 2023. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. URL: https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2023.24.","DOI":"10.4230\/LIPIcs.CCC.2023.24"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. STOC &apos;16, New York, NY, USA, 2016. Association for Computing Machinery. URL: https:\/\/doi.org\/10.1145\/2897518.2897644.","DOI":"10.1145\/2897518.2897644"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Srinivasan Arunachalam, Jop Bri\u00ebt, and Carlos Palazuelos. Quantum query algorithms are completely bounded forms. SIAM J. Comput, 48(3):903\u2013925, 2019. Preliminary version in ITCS&apos;18. URL: https:\/\/doi.org\/10.1137\/18M117563X.","DOI":"10.1137\/18M117563X"},{"key":"5","doi-asserted-by":"publisher","unstructured":"A. Ambainis. Polynomial degree vs. quantum query complexity. J. Comput. System Sci., 72(2):220\u2013238, 2006. Earlier version in FOCS&apos;03. quant-ph\/0305028. URL: https:\/\/doi.org\/10.1016\/j.jcss.2005.06.006.","DOI":"10.1016\/j.jcss.2005.06.006"},{"key":"6","doi-asserted-by":"publisher","unstructured":"A. Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210\u2013239, 2007. Earlier version in FOCS&apos;04. arXiv:quant-ph\/0311001. URL: https:\/\/doi.org\/10.1137\/S0097539705447311.","DOI":"10.1137\/S0097539705447311"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Andris Ambainis. Understanding quantum algorithms via query complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018), pages 3265\u20133285, 2018. doi:10.1142\/9789813272880_0181.","DOI":"10.1142\/9789813272880_0181"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Tom Bannink, Jop Bri\u00ebt, Harry Buhrman, Farrokh Labib, and Troy Lee. Bounding Quantum-Classical Separations for Classes of Nonlocal Games. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1\u201312:11, Dagstuhl, Germany, 2019. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. Available at arXiv: 1811.11068. URL: http:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.12.","DOI":"10.4230\/LIPIcs.STACS.2019.12"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778\u2013797, 2001. URL: https:\/\/doi.org\/10.1145\/502090.502097.","DOI":"10.1145\/502090.502097"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Jop Bri\u00ebt and Francisco Escudero Guti\u00e9rrez. On Converses to the Polynomial Method. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), volume 232 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1\u20136:10. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2022. URL: http:\/\/doi.org\/10.4230\/LIPIcs.TQC.2022.6.","DOI":"10.4230\/LIPIcs.TQC.2022.6"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Henri Fr\u00e9d\u00e9ric Bohnenblust and Einar Hille. On the absolute convergence of dirichlet series. Annals of Mathematics, pages 600\u2013622, 1931. URL: https:\/\/doi.org\/10.2307\/1968255.","DOI":"10.2307\/1968255"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. Theory of Computing, 16(10):1\u201371, 2020. URL: https:\/\/doi.org\/10.4086\/toc.2020.v016a010.","DOI":"10.4086\/toc.2020.v016a010"},{"key":"13","doi-asserted-by":"publisher","unstructured":"S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013. URL: https:\/\/doi.org\/10.1093\/acprof:oso\/9780199535255.001.0001.","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"14","doi-asserted-by":"publisher","unstructured":"M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor. The Grothendieck constant is strictly smaller than Krivine&apos;s bound. Forum Math. Pi, 1:453\u2013462, 2013. Preliminary version in FOCS&apos;11. arXiv:1103.6161. URL: https:\/\/doi.org\/10.1017\/fmp.2013.4.","DOI":"10.1017\/fmp.2013.4"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Jop Bri\u00ebt and Carlos Palazuelos. Failure of the trilinear operator space Grothendieck inequality. Discrete Analysis, 2019. Paper No. 8. URL: https:\/\/doi.org\/10.19086\/da.8805.","DOI":"10.19086\/da.8805"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. In 37th Computational Complexity Conference (CCC 2022), volume 234, pages 28:1\u201328:21, 2022. URL: http:\/\/doi.org\/10.4230\/LIPIcs.CCC.2022.28.","DOI":"10.4230\/LIPIcs.CCC.2022.28"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. URL: http:\/\/doi.org\/10.1017\/CBO9780511804441.","DOI":"10.1017\/CBO9780511804441"},{"key":"18","unstructured":"A. Davie. Lower bound for $K_G$. Unpublished, 1984."},{"key":"19","doi-asserted-by":"publisher","unstructured":"Francisco Escudero Guti\u00e9rrez. Influences of fourier completely bounded polynomials and classical simulation of quantum algorithms. Chicago Journal of Theoretical Computer Science, 2024. URL: https:\/\/doi.org\/10.48550\/arXiv.2304.06713.","DOI":"10.48550\/arXiv.2304.06713"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Sander Gribling and Monique Laurent. Semidefinite programming formulations for the completely bounded norm of a tensor. 2019. URL: https:\/\/doi.org\/10.48550\/arXiv.1901.04921.","DOI":"10.48550\/arXiv.1901.04921"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Ben Green. Montr\u00e9al notes on quadratic Fourier analysis. In Additive combinatorics, volume 43 of CRM Proc. Lecture Notes, pages 69\u2013102. Amer. Math. Soc., Providence, RI, 2007. URL: https:\/\/doi.org\/10.1090\/crmp\/043\/06.","DOI":"10.1090\/crmp\/043\/06"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Alexandre Grothendieck. R\u00e9sum\u00e9 de la th\u00e9orie m\u00e9trique des produits tensoriels topologiques. Soc. de Matem\u00e1tica de S\u00e3o Paulo, 1953. URL: http:\/\/doi.org\/10.5802\/aif.46.","DOI":"10.5802\/aif.46"},{"key":"23","doi-asserted-by":"publisher","unstructured":"L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212\u2013219. ACM, 1996. URL: https:\/\/doi.org\/10.1145\/237814.237866.","DOI":"10.1145\/237814.237866"},{"key":"24","unstructured":"Lawrence A Harris. Bounds on the derivatives of holomorphic functions of vectors. In Proc. Colloq. Analysis, Rio de Janeiro, volume 145, page 163, 1972."},{"key":"25","doi-asserted-by":"publisher","unstructured":"Godfrey Harold Hardy, Edward Maitland Wright, et al. An introduction to the theory of numbers. Oxford university press, 1979. URL: https:\/\/doi.org\/10.1126\/science.90.2329.158.b.","DOI":"10.1126\/science.90.2329.158.b"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Daniel M Kane and Raghu Meka. A PRG for Lipschitz functions of polynomials with applications to sparsest cut. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 1\u201310, 2013. URL: https:\/\/doi.org\/10.1145\/2488608.2488610.","DOI":"10.1145\/2488608.2488610"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Subhash Khot and Assaf Naor. Linear equations modulo 2 and the l1 diameter of convex bodies. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS&apos;07), pages 318\u2013328. IEEE, 2007. URL: https:\/\/doi.org\/10.1109\/FOCS.2007.20.","DOI":"10.1109\/FOCS.2007.20"},{"key":"28","unstructured":"Shachar Lovett. An elementary proof of anti-concentration of polynomials in gaussian variables. In Electron. Colloquium Comput. Complex., volume 17, page 182, 2010."},{"key":"29","doi-asserted-by":"publisher","unstructured":"Mohammad Sal Moslehian, GA Mu\u00f1oz-Fern\u00e1ndez, AM Peralta, and JB Seoane-Sep\u00falveda. Similarities and differences between real and complex banach spaces: an overview and recent developments. Revista de la Real Academia de Ciencias Exactas, F\u00edsicas y Naturales. Serie A. Matem\u00e1ticas, 116(2):1\u201380, 2022. URL: https:\/\/doi.org\/10.1007\/s13398-022-01222-8.","DOI":"10.1007\/s13398-022-01222-8"},{"key":"30","doi-asserted-by":"crossref","unstructured":"Hukukane Nikaid\u00f4. On von Neumann\u2019s minimax theorem. Pacific Journal of Mathematics, 4:65\u201372, 1954.","DOI":"10.2140\/pjm.1954.4.65"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Ryan O&apos;Donnell. Analysis of boolean functions. Cambridge University Press, 2014. URL: https:\/\/doi.org\/10.1017\/CBO9781139814782.","DOI":"10.1017\/CBO9781139814782"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Ryan O&apos;Donnell and Yu Zhao. Polynomial bounds for decoupling, with applications. arXiv preprint arXiv:1512.01603, 2015. URL: https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2016.24.","DOI":"10.4230\/LIPIcs.CCC.2016.24"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Vern Paulsen. Completely Bounded Maps and Operator Algebras. 02 2003. URL: https:\/\/doi.org\/10.1017\/CBO9780511546631.","DOI":"10.1017\/CBO9780511546631"},{"key":"34","unstructured":"J. Reeds. A new lower bound on the real Grothendieck constant. Manuscript (http:\/\/www.dtc.umn.edu\/ reedsj\/bound2.dvi), 1991."},{"key":"35","doi-asserted-by":"publisher","unstructured":"P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal of Computing, 26(5):1484\u20131509, 1997. Earlier version in FOCS&apos;94. URL: https:\/\/doi.org\/10.1137\/S0097539795293172.","DOI":"10.1137\/S0097539795293172"},{"key":"36","unstructured":"Terence Tao. Topics in Random Matrix Theory. Graduate studies in mathematics. American Mathematical Society, 2012."},{"key":"37","doi-asserted-by":"publisher","unstructured":"B. S. Tsirelson. Quantum generalizations of Bell&apos;s inequality. Letters in Mathematical Physics, 1980. URL: https:\/\/doi.org\/10.1007\/BF00417500.","DOI":"10.1007\/BF00417500"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Terence Tao and Joni Ter\u00e4v\u00e4inen. Quantitative bounds for Gowers uniformity of the M\u00f6bius and von Mangoldt functions. Journal of the European Mathematical Society, 2023. doi:10.4171\/jems\/1404.","DOI":"10.4171\/jems\/1404"},{"key":"39","doi-asserted-by":"publisher","unstructured":"N. Th. Varopoulos. On an inequality of von Neumann and an application of the metric theory of tensor products to operators theory. J. Functional Analysis, 16:83\u2013100, 1974. URL: http:\/\/doi.org\/10.1016\/0022-1236(74)90071-8.","DOI":"10.1016\/0022-1236(74)90071-8"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-11-18-1526\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T16:37:33Z","timestamp":1731947853000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-11-18-1526\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,18]]},"references-count":40,"URL":"https:\/\/doi.org\/10.22331\/q-2024-11-18-1526","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,18]]},"article-number":"1526"}}