{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T00:57:07Z","timestamp":1789088227559,"version":"build-2803163510"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"crossref","award":["HR001120C0046"],"award-info":[{"award-number":["HR001120C0046"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>\n                    We study the Quantum Approximate Optimization Algorithm\u00a0(\n                    <jats:sc>QAOA<\/jats:sc>\n                    ) in the context of the\n                    <jats:sc>Max-Cut<\/jats:sc>\n                    problem. Noisy quantum devices are only able to accurately execute\n                    <jats:sc>QAOA<\/jats:sc>\n                    at low circuit depths, while classically-challenging problem instances may call for a relatively high circuit-depth. This is due to the need to build correlations between reachable pairs of vertices in potentially large graphs [\n                    <jats:xref ref-type=\"bibr\">16<\/jats:xref>\n                    ]. To enhance the solving power of low-depth QAOA, we introduce a classical pre-processing step that initializes\n                    <jats:sc>QAOA<\/jats:sc>\n                    with a biased superposition of possible cuts in the graph, referred to as a\n                    <jats:italic>warm-start<\/jats:italic>\n                    . In particular, we initialize\n                    <jats:sc>QAOA<\/jats:sc>\n                    with a solution to a low-rank semidefinite programming relaxation of the\n                    <jats:sc>Max-Cut<\/jats:sc>\n                    problem. Our experimental results show that this variant of\n                    <jats:sc>QAOA<\/jats:sc>\n                    , called\n                    <jats:sc>QAOA-warm<\/jats:sc>\n                    , is able to outperform standard\n                    <jats:sc>QAOA<\/jats:sc>\n                    on lower circuit depths in solution quality and training time. While this improvement is partly due to the classical warm-start, we find strong evidence of further improvement using QAOA circuit at small depth. We provide experimental evidence of improved performance as well as theoretical properties of the proposed framework.\n                  <\/jats:p>","DOI":"10.1145\/3549554","type":"journal-article","created":{"date-parts":[[2022,7,19]],"date-time":"2022-07-19T08:14:20Z","timestamp":1658218460000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Bridging Classical and Quantum with SDP initialized warm-starts for QAOA"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9170-8906","authenticated-orcid":false,"given":"Reuben","family":"Tate","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, Georgia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4397-8220","authenticated-orcid":false,"given":"Majid","family":"Farhadi","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, Georgia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1373-4145","authenticated-orcid":false,"given":"Creston","family":"Herold","sequence":"additional","affiliation":[{"name":"Georgia Tech Research Institute, Atlanta, Georgia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7330-5962","authenticated-orcid":false,"given":"Greg","family":"Mohler","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, Georgia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9566-3856","authenticated-orcid":false,"given":"Swati","family":"Gupta","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, Georgia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,2,24]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.124.090504"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/3157382.3157407"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574037"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1388"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0564-1"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/3157382.3157407"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21830"},{"key":"e_1_3_3_9_2","unstructured":"Fernando G. S. L. Brandao Michael Broughton Edward Farhi Sam Gutmann and Hartmut Neven. 2018. For fixed control parameters the quantum approximate optimization algorithm\u2019s objective function value concentrates for typical instances. arXiv:1812.04170. Retrieved from https:\/\/arxiv.org\/abs\/1812.04170."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.125.260505"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0352-8"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400382467"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.39"},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","article-title":"Laplacian eigenvalues and the maximum cut problem","volume":"62","author":"Delorme C.","year":"1993","unstructured":"C. Delorme and S. Poljak. 1993. Laplacian eigenvalues and the maximum cut problem. Mathematical Programming 62 (1993), 557\u2013574.","journal-title":"Mathematical Programming"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2017.0798"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-06-17-479"},{"key":"e_1_3_3_17_2","unstructured":"Edward Farhi David Gamarnik and Sam Gutmann. 2020. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv:2004.09002. Retrieved from https:\/\/arxiv.org\/abs\/2004.09002."},{"key":"e_1_3_3_18_2","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A quantum approximate optimization algorithm. arXiv:1411.4028. Retrieved from https:\/\/arxiv.org\/abs\/1411.4028."},{"key":"e_1_3_3_19_2","volume-title":"An Introduction to Probability Theory and Its Applications (3rd. ed.)","author":"Feller William","year":"1971","unstructured":"William Feller. 1971. An Introduction to Probability Theory and Its Applications (3rd. ed.). Vol. 2. Wiley, Hoboken, New Jersey."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/39857"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-010-9329-3"},{"key":"e_1_3_3_22_2","unstructured":"Fred Glover Gary Kochenberger and Yu Du. 2019. Quantum bridge analytics I: A tutorial on formulating and using QUBO models. arXiv:1811.11538. Retrieved from https:\/\/arxiv.org\/abs\/1811.11538."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_3_24_2","volume-title":"Exploring Network Structure, Dynamics, and Function Using NetworkX","author":"Hagberg Aric","year":"2008","unstructured":"Aric Hagberg, Pieter Swart, and Daniel S. Chult. 2008. Exploring Network Structure, Dynamics, and Function Using NetworkX. Technical Report. Los Alamos National Lab.(LANL), Los Alamos, NM."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"issue":"9","key":"e_1_3_3_26_2","first-page":"1","article-title":"Impact of graph structures for QAOA on MaxCut","volume":"20","author":"Herrman Rebekah","year":"2021","unstructured":"Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble, and George Siopsis. 2021. Impact of graph structures for QAOA on MaxCut. Quantum Information Processing 20, 9 (2021), 1\u201321.","journal-title":"Quantum Information Processing"},{"key":"e_1_3_3_27_2","first-page":"85","volume-title":"Reducibility Among Combinatorial Problems","author":"Karp Richard M.","year":"1972","unstructured":"Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. Springer, Boston, MA, 85\u2013103."},{"key":"e_1_3_3_28_2","volume-title":"Minima of Functions of Several Variables with Inequalities as Side Conditions","author":"Karush William","year":"1939","unstructured":"William Karush. 1939. Minima of Functions of Several Variables with Inequalities as Side Conditions. Master\u2019s thesis. University of Chicago."},{"key":"e_1_3_3_29_2","first-page":"767","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing","author":"Khot Subhash","year":"2002","unstructured":"Subhash Khot. 2002. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. 767\u2013775."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_3_31_2","unstructured":"Diederik Kingma and Jimmy Lei Ba. 2017. Adam: A method for stochastic optimization. arXiv:1412.6980. Retrieved from https:\/\/arxiv.org\/abs\/1412.6980."},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1525\/9780520411586-036","volume-title":"Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability","author":"Kuhn Harold W.","year":"1951","unstructured":"Harold W. Kuhn and Albert W. Tucker. 1951. Nonlinear programming. In Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability. University of California, Berkeley, Calif., 481\u2013492."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/QCE49297.2020.00041"},{"key":"e_1_3_3_34_2","unstructured":"Yin Tat Lee and Swati Padmanabhan. 2019. An \\(\\tilde{O}(m\/\\epsilon ^3.5)\\) -cost algorithm for semidefinite programs with diagonal constraints. In Proceedings of Thirty Third Conference on Learning Theory vol. 65. 1476\u20131515."},{"key":"e_1_3_3_35_2","unstructured":"Bas Lodewijks. 2020. Mapping NP-hard and NP-complete optimization problems to quadratic unconstrained binary optimization problems. arXiv:1911.08043. Retrieved from https:\/\/arxiv.org\/abs\/1911.08043."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/3086816"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2020.3007688"},{"key":"e_1_3_3_38_2","unstructured":"Glen Bigan Mbeng Rosario Fazio and Giuseppe E. Santoro. 2019. Quantum annealing: A journey through digitalization control and hybrid quantum variational schemes. arXiv:1906.08948. Retrieved from https:\/\/arxiv.org\/abs\/1906.08948."},{"key":"e_1_3_3_39_2","unstructured":"Song Mei Theodor Misiakiewicz Andrea Montanari and Roberto I. Oliveira. 2017. Solving SDPs for synchronization and MaxCut problems via the grothendieck inequality. In Proceedings of the 2017 Conference on Learning Theory Vol. 65. 1476\u20131515."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.5555\/3219315.3219319"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/0805024"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-8330-5_4"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79"},{"key":"e_1_3_3_46_2","volume-title":"Proceedings of the 2006 NSF Design, Service, and Manufacturing Grantees and Research Conference","author":"Ralphs Ted","year":"2006","unstructured":"Ted Ralphs and Menal G\u00fczelsoy. 2006. Duality and warm starting in integer programming. In Proceedings of the 2006 NSF Design, Service, and Manufacturing Grantees and Research Conference."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-07-01-491"},{"key":"e_1_3_3_48_2","unstructured":"The Sage Developers. 2020. SageMath the Sage Mathematics Software System (Version 9.1). The Sage Developers. https:\/\/www.sagemath.org."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797328847"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.97.022304"},{"issue":"13","key":"e_1_3_3_51_2","article-title":"Optimizing quantum heuristics with meta-learning","volume":"3","author":"Wilson Max","year":"2021","unstructured":"Max Wilson, Rachel Stromswold, Filip Wudarski, Stuart Hadfield, Norm M. Tubman, and Eleanor G. Rieffel. 2021. Optimizing quantum heuristics with meta-learning. Quantum Machine Intelligence 3, 13 (2021).","journal-title":"Quantum Machine Intelligence"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.10.021067"},{"key":"e_1_3_3_53_2","doi-asserted-by":"crossref","unstructured":"Lingua Zhu Ho Lun Tang George S. Barron F. A. Calderon-Vargas Nicholas J. Mayhall Edwin Barnes and Sophia E. Economou. 2022. Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. Phys. Rev. Research 4 033029 (2022).","DOI":"10.1103\/PhysRevResearch.4.033029"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549554","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3549554","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T15:00:11Z","timestamp":1750172411000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549554"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,24]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3549554"],"URL":"https:\/\/doi.org\/10.1145\/3549554","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,24]]},"assertion":[{"value":"2020-11-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}