{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:14:56Z","timestamp":1777490096278,"version":"3.51.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004815","name":"Isaac Newton Trust","doi-asserted-by":"publisher","award":["RG74916"],"award-info":[{"award-number":["RG74916"]}],"id":[{"id":"10.13039\/501100004815","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of sum-of-squares relaxations. Exploiting the <jats:italic>polynomial kernel technique<\/jats:italic>, we obtain a quadratic improvement of the known convergence rate by Reznick and Doherty\u00a0and\u00a0Wehner. Specifically, we show that the rate of convergence is no worse than <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(d^2\/\\ell ^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>\u2113<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in the regime <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell = \\Omega (d)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u2113<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the level of the hierarchy and <jats:italic>d<\/jats:italic> the dimension, solving a problem left open in the recent paper by de Klerk and Laurent (<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/arxiv.org\/abs\/1904.08828\">arXiv:1904.08828<\/jats:ext-link> ). Importantly, our analysis also works for matrix-valued polynomials on the sphere which has applications in quantum information for the Best Separable State problem. By exploiting the duality relation between sums of squares and the Doherty\u2013Parrilo\u2013Spedalieri hierarchy in quantum information theory, we show that our result generalizes to nonquadratic polynomials the convergence rates of Navascu\u00e9s, Owari and Plenio.<\/jats:p>","DOI":"10.1007\/s10107-020-01537-7","type":"journal-article","created":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T15:04:54Z","timestamp":1594047894000},"page":"331-360","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":47,"title":["The sum-of-squares hierarchy on the sphere and applications in quantum information theory"],"prefix":"10.1007","volume":"190","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9232-6846","authenticated-orcid":false,"given":"Kun","family":"Fang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6026-4102","authenticated-orcid":false,"given":"Hamza","family":"Fawzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,6]]},"reference":[{"issue":"248","key":"1537_CR1","doi-asserted-by":"publisher","first-page":"1937","DOI":"10.1090\/S0025-5718-04-01642-4","volume":"73","author":"I Area","year":"2004","unstructured":"Area, I., Dimitrov, D., Godoy, E., Ronveaux, A.: Zeros of Gegenbauer and Hermite polynomials and connection coefficients. Math. Comput. 73(248), 1937\u20131951 (2004)","journal-title":"Math. Comput."},{"key":"1537_CR2","volume-title":"A course in convexity","author":"A Barvinok","year":"2002","unstructured":"Barvinok, A.: A course in convexity, vol. 54. American Mathematical Society, Providence (2002)"},{"issue":"3","key":"1537_CR3","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1137\/0502047","volume":"2","author":"JV Baxley","year":"1971","unstructured":"Baxley, J.V.: Extreme eigenvalues of Toeplitz matrices associated with certain orthogonal polynomials. SIAM J. Math. Anal. 2(3), 470\u2013482 (1971)","journal-title":"SIAM J. Math. Anal."},{"key":"1537_CR4","doi-asserted-by":"crossref","unstructured":"Barak, B., Brandao, F.G., Harrow, A.W., Kelner, J., Steurer, D., Zhou, Y.: Hypercontractivity, sum-of-squares proofs, and their applications. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 307\u2013326. ACM (2012)","DOI":"10.1145\/2213977.2214006"},{"key":"1537_CR5","doi-asserted-by":"crossref","unstructured":"Brand\u00e3o, F.G., Christandl, M., Yard, J.: A quasipolynomial-time algorithm for the quantum separability problem. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 343\u2013352 (2011)","DOI":"10.1145\/1993636.1993683"},{"key":"1537_CR6","doi-asserted-by":"crossref","unstructured":"Bhattiprolu, V., Ghosh, M., Guruswami, V., Lee, E., Tulsiani, M.: Weak decoupling, polynomial folds and approximate optimization over the sphere. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1008\u20131019. IEEE (2017)","DOI":"10.1109\/FOCS.2017.97"},{"issue":"2","key":"1537_CR7","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/s00220-017-2880-3","volume":"353","author":"FG Brandao","year":"2017","unstructured":"Brandao, F.G., Harrow, A.W.: Quantum de finetti theorems under local measurements with applications. Commun. Math. Phys. 353(2), 469\u2013506 (2017)","journal-title":"Commun. Math. Phys."},{"key":"1537_CR8","doi-asserted-by":"crossref","unstructured":"Barak, B., Kothari, P.K., Steurer, D.: Quantum entanglement, sum of squares, and the log rank conjecture. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 975\u2013988. ACM (2017)","DOI":"10.1145\/3055399.3055488"},{"issue":"3","key":"1537_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s00454-004-1090-x","volume":"32","author":"G Blekherman","year":"2004","unstructured":"Blekherman, G.: Convexity properties of the cone of nonnegative polynomials. Discrete Comput. Geom. 32(3), 345\u2013371 (2004)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"1537_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1090\/S0002-9939-1961-0122827-1","volume":"12","author":"L Brickman","year":"1961","unstructured":"Brickman, L.: On the field of values of a matrix. Proc. Am. Math. Soc. 12(1), 61\u201366 (1961)","journal-title":"Proc. Am. Math. Soc."},{"issue":"2","key":"1537_CR11","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s00220-007-0189-3","volume":"273","author":"M Christandl","year":"2007","unstructured":"Christandl, M., K\u00f6nig, R., Mitchison, G., Renner, R.: One-and-a-half quantum de Finetti theorems. Commun. Math. Phys. 273(2), 473\u2013498 (2007)","journal-title":"Commun. Math. Phys."},{"issue":"9","key":"1537_CR12","doi-asserted-by":"publisher","first-page":"1200","DOI":"10.1016\/j.jat.2012.05.014","volume":"164","author":"K Driver","year":"2012","unstructured":"Driver, K., Jordaan, K.: Bounds for extreme zeros of some classical orthogonal polynomials. J. Approx. Theory 164(9), 1200\u20131204 (2012)","journal-title":"J. Approx. Theory"},{"issue":"2","key":"1537_CR13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s10100-007-0052-9","volume":"16","author":"E De Klerk","year":"2008","unstructured":"De Klerk, E.: The complexity of optimizing over a simplex, hypercube or sphere: a short survey. Central Eur. J. Oper. Res. 16(2), 111\u2013125 (2008)","journal-title":"Central Eur. J. Oper. Res."},{"key":"1537_CR14","doi-asserted-by":"crossref","unstructured":"de Klerk, E., Laurent, M.: Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere. arXiv:1904.08828 (2019)","DOI":"10.1007\/s10107-019-01465-1"},{"key":"1537_CR15","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/10997703_7","volume-title":"Positive Polynomials in Control","author":"E de Klerk","year":"2005","unstructured":"de Klerk, E., Laurent, M., Parrilo, P.: On the equivalence of algebraic approaches to the minimization of forms on the simplex. In: Henrion, D., Garulli, A. (eds.) Positive Polynomials in Control, pp. 121\u2013132. Springer, Berlin (2005)"},{"key":"1537_CR16","first-page":"1","volume-title":"Emerging Applications of Algebraic Geometry","author":"JP D\u2019Angelo","year":"2009","unstructured":"D\u2019Angelo, J.P., Putinar, M.: Polynomial optimization on odd-dimensional spheres. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, pp. 1\u201315. Springer, Berlin (2009)"},{"issue":"18","key":"1537_CR17","doi-asserted-by":"publisher","first-page":"187904","DOI":"10.1103\/PhysRevLett.88.187904","volume":"88","author":"AC Doherty","year":"2002","unstructured":"Doherty, A.C., Parrilo, P.A., Spedalieri, F.M.: Distinguishing separable and entangled states. Phys. Rev. Lett. 88(18), 187904 (2002)","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"1537_CR18","doi-asserted-by":"publisher","first-page":"022308","DOI":"10.1103\/PhysRevA.69.022308","volume":"69","author":"AC Doherty","year":"2004","unstructured":"Doherty, A.C., Parrilo, P.A., Spedalieri, F.M.: Complete family of separability criteria. Phys. Rev. A 69(2), 022308 (2004)","journal-title":"Phys. Rev. A"},{"key":"1537_CR19","unstructured":"Doherty, A.C., Wehner, S.: Convergence of SDP hierarchies for polynomial optimization on the hypersphere. arXiv:1210.5048, (2012)"},{"key":"1537_CR20","doi-asserted-by":"crossref","unstructured":"Gurvits, L.: Classical deterministic complexity of Edmonds\u2019 problem and quantum entanglement. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 10\u201319. ACM (2003)","DOI":"10.1145\/780542.780545"},{"key":"1537_CR21","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/3-540-44678-8_5","volume-title":"Quantum Information","author":"M Horodecki","year":"2001","unstructured":"Horodecki, M., Horodecki, P., Horodecki, R.: Mixed-state entanglement and quantum communication. In: Alber, G., Beth, T., Horodecki, M., Horodecki, P., Horodecki, R., R\u00f6tteler, M., Weinfurter, H., Werner, R., Zeilinger, A. (eds.) Quantum Information, pp. 151\u2013195. Springer, Berlin (2001)"},{"issue":"1","key":"1537_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2432622.2432625","volume":"60","author":"AW Harrow","year":"2013","unstructured":"Harrow, A.W., Montanaro, A.: Testing product states, quantum merlin-arthur games and tensor optimization. J. ACM (JACM) 60(1), 1\u201343 (2013)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"1537_CR23","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1215\/S0012-7094-38-00429-6","volume":"4","author":"H-Y Hsu","year":"1938","unstructured":"Hsu, H.-Y.: Certain integrals and infinite series involving ultra-spherical polynomials and Bessel functions. Duke Math. J. 4(2), 374\u2013383 (1938)","journal-title":"Duke Math. J."},{"issue":"1","key":"1537_CR24","doi-asserted-by":"publisher","first-page":"012105","DOI":"10.1063\/1.3049751","volume":"50","author":"R Koenig","year":"2009","unstructured":"Koenig, R., Mitchison, G.: A most compendious and facile quantum de Finetti theorem. J. Math. Phys. 50(1), 012105 (2009)","journal-title":"J. Math. Phys."},{"issue":"3","key":"1537_CR25","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"issue":"14","key":"1537_CR26","first-page":"2481","volume":"47","author":"M Lewenstein","year":"2000","unstructured":"Lewenstein, M., Bru\u00df, D., Cirac, J.I., Kraus, B., Ku\u015b, M., Samsonowicz, J., Sanpera, A., Tarrach, R.: Separability and distillability in composite quantum systems-a primer. J. Modern Opt. 47(14), 2481\u20132499 (2000)","journal-title":"J. Modern Opt."},{"key":"1537_CR27","unstructured":"Nesterov, Y.: Random walk in a simplex and quadratic optimization over convex polytopes. Technical report, CORE (2003)"},{"issue":"5","key":"1537_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1103\/PhysRevA.80.052306","volume":"80","author":"M Navascues","year":"2009","unstructured":"Navascues, M., Owari, M., Plenio, M.B.: The power of symmetric extensions for entanglement detection. Phys. Rev. A Atomic Mol. Opt. Phys. 80(5), 1\u201316 (2009)","journal-title":"Phys. Rev. A Atomic Mol. Opt. Phys."},{"key":"1537_CR29","unstructured":"NIST Digital Library of Mathematical Functions. In: Olver, F.W.J., Olde Daalhuis, A.B., Lozier, D.W., Schneider, B.I., Boisvert, R.F., Clark, C.W., Miller, B.R., Saunders, B.V. (eds) http:\/\/dlmf.nist.gov\/, Release 1.0.22 of 2019-03-15"},{"issue":"3","key":"1537_CR30","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/0022-247X(65)90013-2","volume":"12","author":"SV Parter","year":"1965","unstructured":"Parter, S.V.: Remarks on the extreme eigenvalues of Toeplitz forms associated with orthogonal polynomials. J. Math. Anal. Appl. 12(3), 456\u2013470 (1965)","journal-title":"J. Math. Anal. Appl."},{"key":"1537_CR31","unstructured":"Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology (2000)"},{"key":"1537_CR32","unstructured":"Parrilo, P.A.: Approximation quality of SOS relaxations (2013). Talk at ICCOPT 2013"},{"issue":"3","key":"1537_CR33","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/S003614450444614X","volume":"49","author":"I P\u00f3lik","year":"2007","unstructured":"P\u00f3lik, I., Terlaky, T.: A survey of the s-lemma. SIAM Rev. 49(3), 371\u2013418 (2007)","journal-title":"SIAM Rev."},{"issue":"1","key":"1537_CR34","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02572604","volume":"220","author":"B Reznick","year":"1995","unstructured":"Reznick, B.: Uniform denominators in Hilbert\u2019s seventeenth problem. Mathematische Zeitschrift 220(1), 75\u201397 (1995)","journal-title":"Mathematische Zeitschrift"},{"issue":"2","key":"1537_CR35","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0034-4877(76)90038-0","volume":"10","author":"SL Woronowicz","year":"1976","unstructured":"Woronowicz, S.L.: Positive maps of low dimensional matrix algebras. Rep. Math. Phys. 10(2), 165\u2013183 (1976)","journal-title":"Rep. Math. Phys."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01537-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01537-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01537-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T02:51:05Z","timestamp":1633834265000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01537-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1537"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01537-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"27 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}