{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T04:07:25Z","timestamp":1773979645481,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"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\/100000183","name":"Army Research Office","doi-asserted-by":"crossref","award":["W911NF-19-1-0397"],"award-info":[{"award-number":["W911NF-19-1-0397"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"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"}]},{"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,9]]},"DOI":"10.1007\/s11128-021-03232-8","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T07:04:12Z","timestamp":1630479852000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Impact of graph structures for QAOA on MaxCut"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6944-4206","authenticated-orcid":false,"given":"Rebekah","family":"Herrman","sequence":"first","affiliation":[]},{"given":"Lorna","family":"Treffert","sequence":"additional","affiliation":[]},{"given":"James","family":"Ostrowski","sequence":"additional","affiliation":[]},{"given":"Phillip C.","family":"Lotshaw","sequence":"additional","affiliation":[]},{"given":"Travis S.","family":"Humble","sequence":"additional","affiliation":[]},{"given":"George","family":"Siopsis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,1]]},"reference":[{"issue":"6412","key":"3232_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1126\/science.aar3106","volume":"362","author":"S Bravyi","year":"2018","unstructured":"Bravyi, S., Gosset, D., K\u00f6nig, R.: Quantum advantage with shallow circuits. Science 362(6412), 308\u2013311 (2018)","journal-title":"Science"},{"issue":"1","key":"3232_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41534-016-0002-2","volume":"3","author":"D Riste","year":"2017","unstructured":"Riste, D., da Silva, M.P., Ryan, C.A., Cross, A.W., C\u00f3rcoles, A.D., Smolin, J.A., Gambetta, J.M., Chow, J.M., Johnson, B.R.: Demonstration of quantum advantage in machine learning. Quant. Inf. 3(1), 1\u20135 (2017)","journal-title":"Quant. Inf."},{"key":"3232_CR3","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, (2014)"},{"key":"3232_CR4","unstructured":"Farhi, E., Gamarnik, D., Gutmann, S.: The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples. arXiv preprint arXiv:2005.08747, (2020)"},{"key":"3232_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G., et al.: Integer programming. Springer, Berlin (2014)"},{"issue":"6","key":"3232_CR6","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1080\/1055678021000090033","volume":"17","author":"P Festa","year":"2002","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C., Ribeiro, C.C.: Randomized heuristics for the MAX-CUT problem. Optim. Methods Softw. 17(6), 1033\u20131058 (2002)","journal-title":"Optim. Methods Softw."},{"key":"3232_CR7","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Williamson, D.P: 879-approximation algorithms for max cut and max 2sat. In Proceedings of the twenty-sixth annual ACM symposium on theory of computing, pages 422\u2013431, (1994)","DOI":"10.1145\/195058.195216"},{"key":"3232_CR8","unstructured":"Brand\u00e3o, F. G. S.\u00a0L., 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":"3232_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":"3232_CR10","unstructured":"Zhou, L., Wang, S.-T., Choi, S., Pichler, H., Lukin, M.\u00a0D.: Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. arXiv preprint arXiv:1812.01041, (2018)"},{"key":"3232_CR11","doi-asserted-by":"crossref","unstructured":"Akshay, V., Philathong, H., Zacharov, I., Biamonte, J.: Reachability deficits implicit in google\u2019s quantum approximate optimization of graph problems. arXiv preprint arXiv:2007.09148, (2020)","DOI":"10.1103\/PhysRevLett.124.090504"},{"key":"3232_CR12","unstructured":"Farhi, E., Gamarnik, D., Gutmann, S.: The quantum approximate optimization algorithm needs to see the whole graph: a typical case. arXiv preprint arXiv:2004.09002, (2020)"},{"key":"3232_CR13","unstructured":"Ozaeta, A., van Dam, W., McMahon, P.\u00a0L.: Expectation values from the single-layer quantum approximate optimization algorithm on ising problems. arXiv preprint arXiv:2012.03421, (2020)"},{"key":"3232_CR14","doi-asserted-by":"crossref","unstructured":"Lotshaw, P.\u00a0C., Humble, T.\u00a0S., Herrman, R., Ostrowski, J., Siopsis, G.: Empirical performance bounds for quantum approximate optimization. arXiv preprint arXiv:2102.06813, (2021)","DOI":"10.1007\/s11128-021-03342-3"},{"key":"3232_CR15","unstructured":"Belotti, P.: Couenne: a user\u2019s manual. Technical report, Technical report, Lehigh University, (2009)"},{"key":"3232_CR16","unstructured":"Press, W.\u00a0H., Flannery, B.\u00a0P., Teukolsky, S.\u00a0A.: Numerical recipes in Fortran 77: the art of scientific computing. Cambridge University Press, second edition, (1993). https:\/\/people.sc.fsu.edu\/~inavon\/5420a\/DFP.pdf"},{"key":"3232_CR17","unstructured":"Lotshaw, P.\u00a0C., Humble, T.\u00a0S.: QAOA dataset. Found at https:\/\/code.ornl.gov\/qci\/qaoa-dataset-version1"},{"key":"3232_CR18","unstructured":"McKay, B.: Graphs [data set]. Found at http:\/\/users.cecs.anu.edu.au\/~bdm\/data\/graphs.html"},{"key":"3232_CR19","unstructured":"Shaydulin, R., Hadfield, S., Hogg, T., Safro, I.: Classical symmetries and QAOA. arXiv preprint arXiv:2012.04713, (2020)"},{"key":"3232_CR20","unstructured":"Wurtz, J., Love, P.\u00a0J: Bounds on MAXCUT QAOA performance for p$${>}$$ 1. arXiv preprint arXiv:2010.11209, (2020)"},{"issue":"59","key":"3232_CR21","first-page":"1","volume":"20","author":"R Herrman","year":"2021","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(59), 1 (2021)","journal-title":"Quant. Inf. Process."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03232-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03232-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03232-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,8]],"date-time":"2023-11-08T03:46:21Z","timestamp":1699415181000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03232-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":21,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["3232"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03232-8","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"31 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"289"}}