{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T03:19:52Z","timestamp":1774408792599,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2021,11,25]],"date-time":"2021-11-25T00:00:00Z","timestamp":1637798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,25]],"date-time":"2021-11-25T00:00:00Z","timestamp":1637798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["W911NF-20-2-0051"],"award-info":[{"award-number":["W911NF-20-2-0051"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["AF-FA9550-19-1-0147"],"award-info":[{"award-number":["AF-FA9550-19-1-0147"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006754","name":"Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF-19-1-0397"],"award-info":[{"award-number":["W911NF-19-1-0397"]}],"id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["OMA-1937008"],"award-info":[{"award-number":["OMA-1937008"]}],"id":[{"id":"10.13039\/100000001","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":[[2021,12]]},"DOI":"10.1007\/s11128-021-03342-3","type":"journal-article","created":{"date-parts":[[2021,11,25]],"date-time":"2021-11-25T07:02:32Z","timestamp":1637823752000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":54,"title":["Empirical performance bounds for quantum approximate optimization"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7594-2735","authenticated-orcid":false,"given":"Phillip C.","family":"Lotshaw","sequence":"first","affiliation":[]},{"given":"Travis S.","family":"Humble","sequence":"additional","affiliation":[]},{"given":"Rebekah","family":"Herrman","sequence":"additional","affiliation":[]},{"given":"James","family":"Ostrowski","sequence":"additional","affiliation":[]},{"given":"George","family":"Siopsis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,25]]},"reference":[{"key":"3342_CR1","unstructured":"Lotshaw, P.C., Humble, T.S.: QAOA dataset (2021). https:\/\/code.ornl.gov\/qci\/qaoa-dataset-version1"},{"issue":"7779","key":"3342_CR2","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boixo, S., Brandao, F.G., Buell, D.A., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505 (2019)","journal-title":"Nature"},{"key":"3342_CR3","doi-asserted-by":"publisher","DOI":"10.1126\/science.abe8770","author":"HS Zhong","year":"2020","unstructured":"Zhong, H.S., Wang, H., Deng, Y.H., Chen, M.C., Peng, L.C., Luo, Y.H., Qin, J., Wu, D., Ding, X., Hu, Y., Hu, P., Yang, X.Y., Zhang, W.J., Li, H., Li, Y., Jiang, X., Gan, L., Yang, G., You, L., Wang, Z., Li, L., Liu, N.L., Lu, C.Y., Pan, J.W.: Quantum computational advantage using photons. Science (2020). https:\/\/doi.org\/10.1126\/science.abe8770","journal-title":"Science"},{"key":"3342_CR4","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)"},{"issue":"2","key":"3342_CR5","doi-asserted-by":"publisher","first-page":"022304","DOI":"10.1103\/PhysRevA.97.022304","volume":"97","author":"Z Wang","year":"2018","unstructured":"Wang, Z., Hadfield, S., Jiang, Z., Rieffel, E.G.: Quantum approximate optimization algorithm for MaxCut: a fermionic view. Phys. Rev. A 97(2), 022304 (2018)","journal-title":"Phys. Rev. A"},{"key":"3342_CR6","unstructured":"Hadfield, S.: Quantum algorithms for scientific computing and approximate optimization. arXiv preprint arXiv:1805.03265. Eq.\u00a05.10, p.\u00a0114 (2018)"},{"key":"3342_CR7","first-page":"021067","volume":"10","author":"L Zhou","year":"2020","unstructured":"Zhou, L., Wang, S.T., Choi, S., Pichler, H., Lukin, M.D.: Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. Phys. Rev. X 10, 021067 (2020)","journal-title":"Phys. Rev. X"},{"key":"3342_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-019-43176-9","volume":"9","author":"GG Guerreschi","year":"2019","unstructured":"Guerreschi, G.G., Matsuura, A.Y.: QAOA for max-cut requires hundreds of qubits for quantum speed-up. Sci. Rep. 9, 1\u20137 (2019)","journal-title":"Sci. Rep."},{"key":"3342_CR9","doi-asserted-by":"crossref","unstructured":"Medvidovi\u0107, M., Carleo, G.: Classical variational simulation of the quantum approximate optimization algorithm. arXiv preprint arXiv:2009:01760v1 (2020)","DOI":"10.1038\/s41534-021-00440-z"},{"key":"3342_CR10","unstructured":"Brand\u00e3o, F.G.S.L., Broughton, M., Farhi, E., Gutmann, S., Neven, H.: For fixed control parameters the quantum approximate optimization algorithm\u2019s objective function value concentrates for typical instances. arXiv preprint arXiv:1812.04170 (2018)"},{"key":"3342_CR11","unstructured":"Wurtz, J., Love, P.: Bounds on MAXCUT QAOA performance for $$p > 1$$. arXiv preprint arXiv:2010.11209 (2020)"},{"key":"3342_CR12","doi-asserted-by":"publisher","unstructured":"Shaydulin, R., Alexeev, Y.: Evaluating quantum approximate optimization algorithm: a case study. In: 2019 Tenth International Green and Sustainable Computing Conference (IGSC), pp. 1\u20136 (2019). https:\/\/doi.org\/10.1109\/IGSC48788.2019.8957201","DOI":"10.1109\/IGSC48788.2019.8957201"},{"key":"3342_CR13","unstructured":"Crooks, G.E.: Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419 (2018)"},{"key":"3342_CR14","unstructured":"Shaydulin, R., Hadfield, S., Hogg, T.,, Safro, I.: Ruslan Shaydulin and Stuart Hadfield and Tad Hogg and Ilya Safro. arXiv preprint arXiv:2012.04713 (2020)"},{"key":"3342_CR15","doi-asserted-by":"crossref","unstructured":"Herrman, R., Ostrowski, J., Humble, T.S., Siopsis, G.: Lower bounds on circuit depth of the quantum approximate optimization algorithm. Quant. Inf. Process. 20(2), 1\u201317 (2021)","DOI":"10.1007\/s11128-021-03001-7"},{"key":"3342_CR16","doi-asserted-by":"publisher","first-page":"090504","DOI":"10.1103\/PhysRevLett.124.090504","volume":"124","author":"V Akshay","year":"2020","unstructured":"Akshay, V., Philathong, H., Morales, M.E.S., Biamonte, J.D.: Reachability deficits in quantum approximate optimization. Phys. Rev. Lett. 124, 090504 (2020)","journal-title":"Phys. Rev. Lett."},{"key":"3342_CR17","unstructured":"Szegedy, M.: What do QAOA energies reveal about graphs? arXiv preprint arXiv:1912.12272v2 (2020)"},{"issue":"41","key":"3342_CR18","doi-asserted-by":"publisher","first-page":"25396","DOI":"10.1073\/pnas.2006373117","volume":"117","author":"G Pagano","year":"2020","unstructured":"Pagano, G., Bapat, A., Becker, P., Collins, K.S., De, A., Hess, P.W., Kaplan, H.B., Kyprianidis, A., Tan, W.L., Baldwin, C., Brady, L.T., Deshpande, A., Liu, F., Jordan, S., Gorshkov, A.V., Monroe, C.: Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator. Proc. Natl. Acad. Sci. 117(41), 25396 (2020). https:\/\/doi.org\/10.1073\/pnas.2006373117","journal-title":"Proc. Natl. Acad. Sci."},{"key":"3342_CR19","doi-asserted-by":"publisher","first-page":"012320","DOI":"10.1103\/PhysRevA.101.012320","volume":"101","author":"Z Wang","year":"2020","unstructured":"Wang, Z., Rubin, N.C., Dominy, J.M., Rieffel, E.G.: $$XY$$-mixers: analytical and numerical results for the quantum alternating operator ansatz. Phys. Rev. A 101, 012320 (2020)","journal-title":"Phys. Rev. A"},{"key":"3342_CR20","unstructured":"Zhu, L., Tang, H.L., Barron, G.S., Mayhall, N.J., Barnes, E., Economou, S.E.: An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. arXiv preprint arXiv:2005.10258 (2020)"},{"key":"3342_CR21","doi-asserted-by":"crossref","unstructured":"Jiang, Z., Rieffel, E.G., Wang, Z.: Near-optimal quantum circuit for Grover\u2019s unstructured search using a transverse field. Phys. Rev. A 95, 062317 (2017)","DOI":"10.1103\/PhysRevA.95.062317"},{"key":"3342_CR22","doi-asserted-by":"crossref","unstructured":"B\u00e4rtschi, A., Eidenbenz, S.: Grover mixers for QAOA: shifting complexity from mixer design to state preparation. arXiv preprint arXiv:2006.00354v2 (2020)","DOI":"10.1109\/QCE49297.2020.00020"},{"key":"3342_CR23","doi-asserted-by":"crossref","unstructured":"Cook, J., Eidenbenz, S., B\u00e4rtschi, A.: The quantum alternating operator Ansatz on maximum $$k$$-vertex cover. arXiv preprint arXiv:1910.13483v2 (2020)","DOI":"10.2172\/1574737"},{"key":"3342_CR24","doi-asserted-by":"publisher","first-page":"023074","DOI":"10.1103\/PhysRevResearch.2.023074","volume":"2","author":"L Li","year":"2020","unstructured":"Li, L., Fan, M., Coram, M., Riley, P., Leichenauer, S.: Quantum optimization with a novel Gibbs objective function and ansatz architecture search. Phys. Rev. Res. 2, 023074 (2020)","journal-title":"Phys. Rev. Res."},{"key":"3342_CR25","unstructured":"Tate, R., Farhadi, M., Herold, C., Mohler, G., Gupta, S.: Bridging classical and quantum with SDP initialized warm-starts for QAOA. arXiv preprint arXiv:2010.14021 (2020)"},{"key":"3342_CR26","doi-asserted-by":"publisher","first-page":"260505","DOI":"10.1103\/PhysRevLett.125.260505","volume":"125","author":"S Bravyi","year":"2020","unstructured":"Bravyi, S., Kliesch, A., Koenig, R., Tang, E.: Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett. 125, 260505 (2020)","journal-title":"Phys. Rev. Lett."},{"key":"3342_CR27","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnel, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? Electronic Colloquium on Computational Complexity, Report No. 101 (2005)"},{"key":"3342_CR28","doi-asserted-by":"crossref","unstructured":"Hastings, M.B.: Classical and quantum bounded depth approximation algorithms. arXiv:1905.07047 (2019)","DOI":"10.26421\/QIC19.13-14-3"},{"key":"3342_CR29","unstructured":"Press, W.H., Flannery, B.P., Teukolsky, S.A.: Numerical recipes in Fortran 77: the art of scientific computing, 2nd edn. Cambridge University Press (1993). https:\/\/people.sc.fsu.edu\/$$\\sim $$inavon\/5420a\/DFP.pdf"},{"key":"3342_CR30","doi-asserted-by":"crossref","unstructured":"Herrman, R., Treffert, L., Ostrowski, J., Lotshaw, P.C., Humble, T.S., Siopsis, G.: Impact of graph structures for QAOA on MaxCut. Quantum Inf. Process. 289:1\u201321 (2021)","DOI":"10.1007\/s11128-021-03232-8"},{"key":"3342_CR31","unstructured":"Farhi, E., Gamarnik, D., Gutmann, S.: The quantum approximate optimization algorithm needs to see the whole graph: worst case examples. arXiv:2005.08747 (2020)"},{"key":"3342_CR32","unstructured":"McKay, B.: Graphs. https:\/\/users.cecs.anu.edu.au\/$$\\sim $$bdm\/data\/graphs.html. Accessed 8 July (2020)"},{"key":"3342_CR33","unstructured":"Belotti, P.: Couenne: a user\u2019s manual. Technical report, Lehigh University, Technical report (2009)"},{"key":"3342_CR34","unstructured":"Yamamoto, N.: On the natural gradient for variational quantum eigensolver. arXiv:1909.05074 (2019)"},{"key":"3342_CR35","doi-asserted-by":"publisher","first-page":"43246","DOI":"10.1103\/PhysRevResearch.2.043246","volume":"2","author":"D Wierichs","year":"2020","unstructured":"Wierichs, D., Gogolin, C., Kastoryano, M.: Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer. Phys. Rev. Res. 2, 43246 (2020)","journal-title":"Phys. Rev. Res."},{"key":"3342_CR36","doi-asserted-by":"publisher","first-page":"269","DOI":"10.22331\/q-2020-05-25-269","volume":"4","author":"J Stokes","year":"2020","unstructured":"Stokes, J., Izaac, J., Killoran, N., Carleo, G.: Quantum natural gradient. Quantum 4, 269 (2020)","journal-title":"Quantum"},{"key":"3342_CR37","doi-asserted-by":"publisher","first-page":"140502","DOI":"10.1103\/PhysRevLett.126.140502","volume":"126","author":"AW Harrow","year":"2021","unstructured":"Harrow, A.W., Napp, J.C.: Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms. Phys. Rev. Lett. 126, 140502 (2021)","journal-title":"Phys. Rev. Lett."},{"issue":"6","key":"3342_CR38","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. Assoc. Comput. Mach. 42(6), 1115 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"3342_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2021.3066275","volume":"2","author":"R Shaydulin","year":"2021","unstructured":"Shaydulin, R., Wild, S.M.: Exploiting symmetry reduces the cost of training QAOA. IEEE Trans. Quantum Eng. 2, 1\u20139 (2021)","journal-title":"IEEE Trans. Quantum Eng."},{"key":"3342_CR40","doi-asserted-by":"crossref","unstructured":"Belotti, P., Lee, J., Liberti, L., Margot, F., W\u00e4chter, A.: Branching and bounds tightening techniques for nonconvex MINLP. Optim. Methods Softw. 24(4-5), 597\u2013634 (2009)","DOI":"10.1080\/10556780903087124"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03342-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03342-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03342-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T07:18:25Z","timestamp":1638429505000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03342-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,25]]},"references-count":40,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["3342"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03342-3","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,25]]},"assertion":[{"value":"9 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"None of the authors has a conflict of interest to declare that is relevant to the content of the paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Data and code from this study are available online [].","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Data and code"}}],"article-number":"403"}}