{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T14:52:10Z","timestamp":1782485530965,"version":"3.54.5"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T00:00:00Z","timestamp":1774051200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T00:00:00Z","timestamp":1774051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018693","name":"HORIZON EUROPE Framework Programme","doi-asserted-by":"publisher","award":["EP\/X032051\/1"],"award-info":[{"award-number":["EP\/X032051\/1"]}],"id":[{"id":"10.13039\/100018693","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011820","name":"Saudi Arabian Cultural Mission","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100011820","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2026,7]]},"DOI":"10.1007\/s11590-026-02289-7","type":"journal-article","created":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T04:10:50Z","timestamp":1774066250000},"page":"1265-1278","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Convergence of the sum-of-squares hierarchy for quadratic optimization over roots-of-unity"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-3735-0579","authenticated-orcid":false,"given":"Ahmad","family":"Al-Sulami","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hamza","family":"Fawzi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9881-2618","authenticated-orcid":false,"given":"Shengding","family":"Sun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,21]]},"reference":[{"key":"2289_CR1","first-page":"181","volume":"20","author":"S Poljak","year":"1995","unstructured":"Poljak, S., Tuza, Z.: Maximum cuts and large bipartite subgraphs. DIMACS Ser. 20, 181\u2013244 (1995)","journal-title":"DIMACS Ser."},{"key":"2289_CR2","doi-asserted-by":"crossref","unstructured":"Ding, C.H., He, X., Zha, H., Gu, M., Simon, H.D.: A min-max cut algorithm for graph partitioning and data clustering. In: Proceedings 2001 IEEE International Conference on Data Mining, pp. 107\u2013114. IEEE (2001)","DOI":"10.1109\/ICDM.2001.989507"},{"issue":"3","key":"2289_CR3","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F Barahona","year":"1988","unstructured":"Barahona, F., Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493\u2013513 (1988)","journal-title":"Oper. Res."},{"issue":"6312","key":"2289_CR4","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1126\/science.aah5178","volume":"354","author":"PL McMahon","year":"2016","unstructured":"McMahon, P.L., Marandi, A., Haribara, Y., Hamerly, R., Langrock, C., Tamate, S., Inagaki, T., Takesue, H., Utsunomiya, S., Aihara, K., et al.: A fully programmable 100-spin coherent ising machine with all-to-all connections. Science 354(6312), 614\u2013617 (2016)","journal-title":"Science"},{"key":"2289_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3459606","volume":"26","author":"M J\u00fcnger","year":"2021","unstructured":"J\u00fcnger, M., Lobe, E., Mutzel, P., Reinelt, G., Rendl, F., Rinaldi, G., Stollenwerk, T.: Quantum annealing versus digital computing: an experimental comparison. J. Exp. Algorithm 26, 1\u201330 (2021)","journal-title":"J. Exp. Algorithm"},{"issue":"3","key":"2289_CR6","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1287\/ijoc.2017.0798","volume":"30","author":"I Dunning","year":"2018","unstructured":"Dunning, I., Gupta, S., Silberholz, J.: What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO. INFORMS J. Comput. 30(3), 608\u2013624 (2018)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"2289_CR7","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10589-021-00310-6","volume":"80","author":"T Hrga","year":"2021","unstructured":"Hrga, T., Povh, J.: MADAM: a parallel exact solver for Max-Cut based on semidefinite programming and ADMM. Comput. Optim. Appl. 80(2), 347\u2013375 (2021)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"2289_CR8","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s12532-023-00236-6","volume":"15","author":"D Rehfeldt","year":"2023","unstructured":"Rehfeldt, D., Koch, T., Shinano, Y.: Faster exact solution of sparse Max-Cut and QUBO problems. Math. Program. Comput. 15(3), 445\u2013470 (2023)","journal-title":"Math. Program. Comput."},{"issue":"3","key":"2289_CR9","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1137\/04061341X","volume":"16","author":"S Zhang","year":"2006","unstructured":"Zhang, S., Huang, Y.: Complex quadratic optimization and semidefinite programming. SIAM J. Optim. 16(3), 871\u2013890 (2006)","journal-title":"SIAM J. Optim."},{"key":"2289_CR10","doi-asserted-by":"publisher","first-page":"2697","DOI":"10.1007\/s11425-010-3087-7","volume":"53","author":"Y Huang","year":"2010","unstructured":"Huang, Y., Zhang, S.: Approximation algorithms for indefinite complex quadratic maximization problems. Sci China Math 53, 2697\u20132708 (2010)","journal-title":"Sci China Math"},{"issue":"1","key":"2289_CR11","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s10107-006-0064-6","volume":"110","author":"AM-C So","year":"2007","unstructured":"So, A.M.-C., Zhang, J., Ye, Y.: On approximating complex quadratic optimization problems via semidefinite programming relaxations. Math. Program. 110(1), 93\u2013110 (2007)","journal-title":"Math. Program."},{"key":"2289_CR12","doi-asserted-by":"crossref","unstructured":"So, A.M.-C.: Probabilistic analysis of the semidefinite relaxation detector in digital communications. In: Proceedings of 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010) (2008)","DOI":"10.1137\/1.9781611973075.57"},{"key":"2289_CR13","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s10107-016-1059-6","volume":"163","author":"AS Bandeira","year":"2017","unstructured":"Bandeira, A.S., Boumal, N., Singer, A.: Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Math. Program. 163, 145\u2013167 (2017)","journal-title":"Math. Program."},{"key":"2289_CR14","unstructured":"Jiang, R., Liu, Y.-F., Bao, C., Jiang, B.: Tightness and equivalence of semidefinite relaxations for MIMO detection (2021). arXiv preprint arXiv:2102.04586"},{"issue":"1","key":"2289_CR15","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1137\/17M115075X","volume":"29","author":"C Lu","year":"2019","unstructured":"Lu, C., Liu, Y.-F., Zhang, W.-Q., Zhang, S.: Tightness of a new and enhanced semidefinite relaxation for MIMO detection. SIAM J. Optim. 29(1), 719\u2013742 (2019)","journal-title":"SIAM J. Optim."},{"issue":"11","key":"2289_CR16","doi-asserted-by":"publisher","first-page":"3869","DOI":"10.1109\/TIT.2007.907472","volume":"53","author":"A Mobasher","year":"2007","unstructured":"Mobasher, A., Taherzadeh, M., Sotirov, R., Khandani, A.K.: A near-maximum-likelihood decoding algorithm for MIMO systems based on semidefinite programming. IEEE Trans. Inf. Theory 53(11), 3869\u20133886 (2007)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2289_CR17","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s10107-013-0738-9","volume":"149","author":"I Waldspurger","year":"2015","unstructured":"Waldspurger, I., d\u2019Aspremont, A., Mallat, S.: Phase recovery, Max-Cut and complex semidefinite programming. Math. Program. 149, 47\u201381 (2015)","journal-title":"Math. Program."},{"issue":"5","key":"2289_CR18","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1109\/TSP.2013.2296883","volume":"62","author":"M Soltanalian","year":"2014","unstructured":"Soltanalian, M., Stoica, P.: Designing unimodular codes via quadratic optimization. IEEE Trans. Signal Process. 62(5), 1221\u20131234 (2014)","journal-title":"IEEE Trans. Signal Process."},{"key":"2289_CR19","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1109\/OJSP.2020.3020221","volume":"1","author":"C Lu","year":"2020","unstructured":"Lu, C., Liu, Y.-F., Zhou, J.: An enhanced SDR based global algorithm for nonconvex complex quadratic programs with signal processing applications. IEEE Open J. Signal Process. 1, 120\u2013134 (2020)","journal-title":"IEEE Open J. Signal Process."},{"key":"2289_CR20","doi-asserted-by":"crossref","unstructured":"Wu, F.-Y.: The Potts model. Rev. Mod. Phys. (1982)","DOI":"10.1103\/RevModPhys.54.235"},{"key":"2289_CR21","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s10107-015-0977-z","volume":"160","author":"H Fawzi","year":"2016","unstructured":"Fawzi, H., Saunderson, J., Parrilo, P.A.: Sparse sums of squares on finite abelian groups and improved semidefinite lifts. Math. Program. 160, 149\u2013191 (2016)","journal-title":"Math. Program."},{"issue":"1","key":"2289_CR22","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1137\/16M105544X","volume":"27","author":"S Sakaue","year":"2017","unstructured":"Sakaue, S., Takeda, A., Kim, S., Ito, N.: Exact semidefinite programming relaxations with truncated moment matrix for binary polynomial optimization problems. SIAM J. Optim. 27(1), 565\u2013582 (2017)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"2289_CR23","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"2289_CR24","doi-asserted-by":"publisher","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. Society for Industrial and Applied Mathematics, Philadelphia (2012). https:\/\/doi.org\/10.1137\/1.9781611972290","DOI":"10.1137\/1.9781611972290"},{"issue":"3","key":"2289_CR25","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1023\/B:JOCO.0000038911.67280.3f","volume":"8","author":"E Klerk","year":"2004","unstructured":"Klerk, E., Pasechnik, D.V., Warners, J.P.: On approximate graph colouring and max-k-cut algorithms based on the $$\\theta $$-function. J. Comb. Optim. 8(3), 267\u2013294 (2004)","journal-title":"J. Comb. Optim."},{"key":"2289_CR26","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Williamson, D.: Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programming. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, pp. 443\u2013452 (2001)","DOI":"10.1145\/380752.380838"},{"key":"2289_CR27","first-page":"1","volume":"6","author":"L Sinjorgo","year":"2024","unstructured":"Sinjorgo, L., Sotirov, R., Anjos, M.F.: Cuts and semidefinite liftings for the complex cut polytope. Math. Program. 6, 1\u201350 (2024)","journal-title":"Math. Program."},{"key":"2289_CR28","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Semidefinite relaxations for Max-Cut. In: The Sharpest Cut: The Impact of Manfred Padberg and His Work, pp. 257\u2013290. SIAM (2004)","DOI":"10.1137\/1.9780898718805.ch16"},{"issue":"2","key":"2289_CR29","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/s10107-021-01745-9","volume":"197","author":"L Slot","year":"2023","unstructured":"Slot, L., Laurent, M.: Sum of squares hierarchies for binary polynomial optimization. Math. Program. 197(2), 621\u2013660 (2023)","journal-title":"Math. Program."},{"key":"2289_CR30","doi-asserted-by":"crossref","unstructured":"Naftalevich, A., Schreiber, M.: Trigonometric polynomials and sums of squares. In: Number Theory: A Seminar Held at the Graduate School and University Center of the City University of New York 1983\u201384, pp. 225\u2013238. Springer (2006)","DOI":"10.1007\/BFb0074607"},{"issue":"3","key":"2289_CR31","doi-asserted-by":"publisher","first-page":"2137","DOI":"10.1137\/22M1540818","volume":"33","author":"F Bach","year":"2023","unstructured":"Bach, F., Rudi, A.: Exponential convergence of sum of squares hierarchies for trigonometric polynomials. SIAM J. Optim. 33(3), 2137\u20132159 (2023)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2289_CR32","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."},{"key":"2289_CR33","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 293\u2013303. Springer (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"issue":"4","key":"2289_CR34","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1287\/moor.28.4.871.20508","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res. 28(4), 871\u2013883 (2003a)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"2289_CR35","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver, and Lasserre relaxations for 0\u20131 programming. Math. Oper. Res. 28(3), 470\u2013496 (2003b)","journal-title":"Math. Oper. Res."},{"key":"2289_CR36","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0024-3795(88)90240-6","volume":"107","author":"J Agler","year":"1988","unstructured":"Agler, J., Helton, W., McCullough, S., Rodman, L.: Positive semidefinite matrices with a given sparsity pattern. Linear Algebra Appl. 107, 101\u2013149 (1988)","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"2289_CR37","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1137\/05064504X","volume":"17","author":"JB Lasserre","year":"2006","unstructured":"Lasserre, J.B.: Convergent SDP relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17(3), 822\u2013843 (2006)","journal-title":"SIAM J. Optim."},{"key":"2289_CR38","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"2012","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2. Springer, Berlin (2012)"},{"issue":"3","key":"2289_CR39","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/15M103114X","volume":"26","author":"E Klerk","year":"2016","unstructured":"Klerk, E., Vallentin, F.: On the turing model complexity of interior point methods for semidefinite programming. SIAM J. Optim. 26(3), 1944\u20131961 (2016)","journal-title":"SIAM J. Optim."},{"key":"2289_CR40","unstructured":"O\u2019Donnell, R.: Sos is not obviously automatizable, even approximately. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), pp. 59\u20131 (2017). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik"},{"key":"2289_CR41","unstructured":"Raghavendra, P., Weitz, B.: On the bit complexity of sum-of-squares proofs. arXiv preprint arXiv:1702.05139 (2017)"},{"key":"2289_CR42","doi-asserted-by":"crossref","unstructured":"Gribling, S., Polak, S., Slot, L.: A note on the computational complexity of the moment-sos hierarchy for polynomial optimization. In: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, pp. 280\u2013288 (2023)","DOI":"10.1145\/3597066.3597075"},{"issue":"2","key":"2289_CR43","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1137\/15M1034386","volume":"28","author":"C Josz","year":"2018","unstructured":"Josz, C., Molzahn, D.K.: Lasserre hierarchy for large scale polynomial optimization in real and complex variables. SIAM J. Optim. 28(2), 1017\u20131048 (2018)","journal-title":"SIAM J. Optim."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-026-02289-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-026-02289-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-026-02289-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T14:42:38Z","timestamp":1782484958000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-026-02289-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,21]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["2289"],"URL":"https:\/\/doi.org\/10.1007\/s11590-026-02289-7","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,21]]},"assertion":[{"value":"29 September 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}