{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,19]],"date-time":"2026-08-19T19:56:04Z","timestamp":1787169364228,"version":"build-2736575974"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,6,2]],"date-time":"2020-06-02T00:00:00Z","timestamp":1591056000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,2]],"date-time":"2020-06-02T00:00:00Z","timestamp":1591056000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001656","name":"Helmholtz-Gemeinschaft","doi-asserted-by":"publisher","award":["ZT-0013"],"award-info":[{"award-number":["ZT-0013"]}],"id":[{"id":"10.13039\/501100001656","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["820363"],"award-info":[{"award-number":["820363"]}],"id":[{"id":"10.13039\/501100000780","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":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The performance of the quantum approximate optimization algorithm is evaluated by using three different measures: the probability of finding the ground state, the energy expectation value, and a ratio closely related to the approximation ratio. The set of problem instances studied consists of weighted MaxCut problems and 2-satisfiability problems. The Ising model representations of the latter possess unique ground states and highly degenerate first excited states. The quantum approximate optimization algorithm is executed on quantum computer simulators and on the IBM Q Experience. Additionally, data obtained from the D-Wave 2000Q quantum annealer are used for comparison, and it is found that the D-Wave machine outperforms the quantum approximate optimization algorithm executed on a simulator. The overall performance of the quantum approximate optimization algorithm is found to strongly depend on the problem instance.<\/jats:p>","DOI":"10.1007\/s11128-020-02692-8","type":"journal-article","created":{"date-parts":[[2020,6,2]],"date-time":"2020-06-02T08:04:34Z","timestamp":1591085074000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":128,"title":["Benchmarking the quantum approximate optimization algorithm"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2351-3162","authenticated-orcid":false,"given":"Madita","family":"Willsch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dennis","family":"Willsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fengping","family":"Jin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hans","family":"De Raedt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kristel","family":"Michielsen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,6,2]]},"reference":[{"key":"2692_CR1","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm (2014). arXiv:1411.4028"},{"key":"2692_CR2","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF01343193","volume":"51","author":"M Born","year":"1928","unstructured":"Born, M., Fock, V.: Beweis des Adiabatensatzes. Z. Phys. 51, 165 (1928)","journal-title":"Z. Phys."},{"key":"2692_CR3","unstructured":"Streif, M., Leib, M.: Comparison of QAOA with quantum and simulated annealing (2019). arXiv:1901.01903"},{"key":"2692_CR4","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484 (1997)","journal-title":"SIAM J. Comput."},{"key":"2692_CR5","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","unstructured":"Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018)","journal-title":"Quantum"},{"key":"2692_CR6","unstructured":"Otterbach, J.\u00a0S., Manenti, R., Alidoust, N., Bestwick, A., Block, M., Bloom, B., Caldwell, S., Didier, N., Fried, E.\u00a0S., Hong, S., Karalekas, P., Osborn, C.B., Papageorge, A., Peterson, E.C., Prawiroatmodjo, G., Rubin, G., Ryan, C.A., Scarabelli, D., Scheer, M., Sete, E.A., Sivarajah, P., Smith, R.S., Staley, A., Tezak, N., Zeng, W.J., Hudson, A., Johnson, B.R., Reagor, M., da Silva, M.P., Rigetti, C.: Unsupervised machine learning on a hybrid quantum computer (2017). arXiv:1712.05771"},{"key":"2692_CR7","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1038\/s41566-018-0236-y","volume":"12","author":"X Qiang","year":"2018","unstructured":"Qiang, X., Zhou, X., Wang, J., Wilkes, C.M., Loke, T., O\u2019Gara, S., Kling, L., Marshall, G.D., Santagati, R., Ralph, T.C., Wang, J.B., O\u2019Brien, J.L., Thompson, M.G., Matthews, J.C.F.: Large-scale silicon quantum photonics implementing arbitrary two-qubit processing. Nat. Photon. 12, 534 (2018)","journal-title":"Nat. Photon."},{"key":"2692_CR8","unstructured":"Farhi, E., Harrow, A.W.: Quantum supremacy through the quantum approximate optimization algorithm (2016). arXiv:1602.07674"},{"key":"2692_CR9","volume-title":"Computers and Intractability","author":"GR Garey","year":"2000","unstructured":"Garey, G.R., Johnson, D.: Computers and Intractability. W.H. Freeaman, San Fransico (2000)"},{"key":"2692_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TASC.2014.2318294","volume":"24","author":"PI Bunyk","year":"2014","unstructured":"Bunyk, P.I., Hoskinson, E.M., Johnson, M.W., Tolkacheva, E., Altomare, F., Berkley, A.J., Harris, R., Hilton, J.P., Lanting, T., Przybysz, A.J., Whittaker, J.: Architectural considerations in the design of a superconducting quantum annealing processor. IEEE Trans. Appl. Supercond. 24, 1 (2014)","journal-title":"IEEE Trans. Appl. Supercond."},{"key":"2692_CR11","doi-asserted-by":"publisher","first-page":"56","DOI":"10.3389\/fphy.2014.00056","volume":"2","author":"Z Bian","year":"2014","unstructured":"Bian, Z., Chudak, F., Israel, R., Lackey, B., Macready, W.G., Roy, A.: Discrete optimization using quantum annealing on sparse Ising models. Front. Phys. 2, 56 (2014)","journal-title":"Front. Phys."},{"key":"2692_CR12","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s11128-015-1150-6","volume":"15","author":"T Boothby","year":"2016","unstructured":"Boothby, T., King, A.D., Roy, A.: Fast clique minor generation in Chimera qubit connectivity graphs. Quantum Inf. Process. 15, 495 (2016)","journal-title":"Quantum Inf. Process."},{"key":"2692_CR13","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0009-2614(94)00117-0","volume":"219","author":"A Finnila","year":"1994","unstructured":"Finnila, A., Gomez, M., Sebenik, C., Stenson, C., Doll, J.: Quantum annealing: a new method for minimizing multidimensional functions. Chem. Phys. Lett. 219, 343 (1994)","journal-title":"Chem. Phys. Lett."},{"key":"2692_CR14","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355 (1998)","journal-title":"Phys. Rev. E"},{"key":"2692_CR15","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution (2000). arXiv:quant-ph\/0001106"},{"key":"2692_CR16","doi-asserted-by":"publisher","first-page":"012322","DOI":"10.1103\/PhysRevA.65.012322","volume":"65","author":"AM Childs","year":"2001","unstructured":"Childs, A.M., Farhi, E., Preskill, J.: Robustness of adiabatic quantum computation. Phys. Rev. A 65, 012322 (2001)","journal-title":"Phys. Rev. A"},{"key":"2692_CR17","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1063\/1.526596","volume":"26","author":"M Suzuki","year":"1985","unstructured":"Suzuki, M.: Decomposition formulas of exponential operators and Lie exponentials with some applications to quantum mechanics and statistical physics. J. Math. Phys. 26, 601 (1985)","journal-title":"J. Math. Phys."},{"key":"2692_CR18","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1090\/S0002-9939-1959-0108732-6","volume":"10","author":"HF Trotter","year":"1959","unstructured":"Trotter, H.F.: On the product of semi-groups of operators. Proc. Am. Math. Soc. 10, 545 (1959)","journal-title":"Proc. Am. Math. Soc."},{"key":"2692_CR19","doi-asserted-by":"publisher","first-page":"015002","DOI":"10.1103\/RevModPhys.90.015002","volume":"90","author":"T Albash","year":"2018","unstructured":"Albash, T., Lidar, D.: Adiabatic quantum computation. Rev. Mod. Phys. 90, 015002 (2018)","journal-title":"Rev. Mod. Phys."},{"key":"2692_CR20","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1038\/s41534-017-0022-6","volume":"3","author":"N Chancellor","year":"2017","unstructured":"Chancellor, N., Zohren, S., Warburton, P.A.: Circuit design for multi-body interactions in superconducting quantum annealing systems with applications to a scalable architecture. NPJ Quantum Inf. 3, 21 (2017)","journal-title":"NPJ Quantum Inf."},{"key":"2692_CR21","doi-asserted-by":"publisher","first-page":"34","DOI":"10.3390\/a12020034","volume":"12","author":"S Hadfield","year":"2019","unstructured":"Hadfield, S., Wang, Z., O\u2019Gorman, B., Rieffel, E.G., Venturelli, D., Biswas, R.: From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms 12, 34 (2019)","journal-title":"Algorithms"},{"key":"2692_CR22","doi-asserted-by":"publisher","first-page":"4213","DOI":"10.1038\/ncomms5213","volume":"5","author":"A Peruzzo","year":"2014","unstructured":"Peruzzo, A., McClean, J., Shadbolt, P., Yung, M., Zhou, X., Love, P.J., Aspuru-Guzik, A., O\u2019Brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014)","journal-title":"Nat. Commun."},{"key":"2692_CR23","first-page":"031007","volume":"6","author":"PJJ O\u2019Malley","year":"2016","unstructured":"O\u2019Malley, P.J.J., Babbush, R., Kivlichan, I.D., Romero, J., McClean, J.R., Barends, R., Kelly, J., Roushan, P., Tranter, A., Ding, N., Campbell, B., Chen, Y., Chen, Z., Chiaro, B., Dunsworth, A., Fowler, A.G., Jeffrey, E., Lucero, E., Megrant, A., Mutus, J.Y., Neeley, M., Neill, C., Quintana, C., Sank, D., Vainsencher, A., Wenner, J., White, T.C., Coveney, P.V., Love, P.J., Neven, H., Aspuru-Guzik, A., Martinis, J.M.: Scalable quantum simulation of molecular energies. Phys. Rev. X 6, 031007 (2016)","journal-title":"Phys. Rev. X"},{"key":"2692_CR24","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1038\/nature23879","volume":"549","author":"A Kandala","year":"2017","unstructured":"Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J.M., Gambetta, J.M.: Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature 549, 242 (2017)","journal-title":"Nature"},{"key":"2692_CR25","first-page":"021027","volume":"7","author":"Z Yang","year":"2017","unstructured":"Yang, Z., Rahmani, A., Shabani, A., Neven, H., Chamon, C.: Optimizing variational quantum algorithms using Pontryagin\u2019s minimum principle. Phys. Rev. X 7, 021027 (2017)","journal-title":"Phys. Rev. X"},{"key":"2692_CR26","doi-asserted-by":"crossref","unstructured":"Hsu, T., Jin, F., Seidel, C., Neukart, F., De Raedt, H., Michielsen, K.: Quantum annealing with anneal path control: application to 2-SAT problems with known energy landscapes (2018). arXiv:1810.00194","DOI":"10.4208\/cicp.OA-2018-0257"},{"key":"2692_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"key":"2692_CR28","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, 1115 (1995)","journal-title":"J. ACM"},{"key":"2692_CR29","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, 022304 (2018)","journal-title":"Phys. Rev. A"},{"key":"2692_CR30","unstructured":"Aleksandrowicz, G., Alexander, T., Barkoutsos, P., Bello, L., Ben-Haim, Y., Bucher, D., Cabrera-Hern\u00e1dez, F.J., Carballo-Franquis, J., Chen, A., Chen, C.-F., Chow, J.M., C\u00f3rcoles-Gonzales, A.D., Cross, A.J., Cross, A., Cruz-Benito, J., Culver, C., Gonz\u00e1lez, S.D. L.P., Torre, E.D.L., Ding, D., Dumitrescu, E., Duran, I., Eendebak, P., Everitt, M., Sertage, I.F., Frisch, A., Fuhrer, A., Gambetta, J., Gago, B.G., Gomez-Mosquera, J., Greenberg, D., Hamamura, I., Havlicek, V., Hellmers, J., Herok, \u0141., Horii, H., Hu, S., Imamichi, T., Itoko, T., Javadi-Abhari, A., Kanazawa, N., Karazeev, A., Krsulich, K., Liu, P., Luh, Y., Maeng, Y., Marques, M., Mart\u00edn-Fern\u00e1ndez, F.J., McClure, D.T., McKay, D., Meesala, S., Mezzacapo, A., Moll, N., Rodr\u00edguez, D.\u00a0M., Nannicini, G., Nation, P., Ollitrault, P., O\u2019Riordan, L.J., Paik, H., P\u00e9rez, J., Phan, A., Pistoia, M., Prutyanov, V., Reuter, M., Rice, J., Davila, A.R., Rudy, R.H.P., Ryu, M., Sathaye, N., Schnabel, C., Schoute, E., Setia, K., Shi, Y., Silva, A., Siraichi, Y., Sivarajah, S., Smolin, J.A., Soeken, M., Takahashi, H., Tavernelli, I., Taylor, C., Taylour, P., Trabing, K., Treinish, M., Turner, W., Vogt-Lee, D., Vuillot, C., Wildstrom, J.A., Wilson, J., Winston, E., Wood, C., Wood, S., W\u00f6rner, S., Akhalwaya, I.Y., Zoufal, C.: Qiskit: an open-source framework for quantum computing (2019)"},{"key":"2692_CR31","unstructured":"IBM: IBM Q experience. https:\/\/www.research.ibm.com\/ibm-q\/ (2016)"},{"key":"2692_CR32","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.cpc.2018.11.005","volume":"237","author":"H De Raedt","year":"2019","unstructured":"De Raedt, H., Jin, F., Willsch, D., Willsch, M., Yoshioka, N., Ito, N., Yuan, S., Michielsen, K.: Massively parallel quantum computer simulator, eleven years later. Comput. Phys. Commun. 237, 47 (2019)","journal-title":"Comput. Phys. Commun."},{"key":"2692_CR33","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1093\/comjnl\/7.4.308","volume":"7","author":"JA Nelder","year":"1965","unstructured":"Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7, 308 (1965)","journal-title":"Comput. J."},{"key":"2692_CR34","volume-title":"Numerical Recipes, 3rd Edition: The Art of Scientific Computing","author":"WH Press","year":"2007","unstructured":"Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes, 3rd Edition: The Art of Scientific Computing. Cambridge University Press, New York (2007)"},{"key":"2692_CR35","doi-asserted-by":"publisher","first-page":"6903","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, 6903 (2019)","journal-title":"Sci. Rep."},{"key":"2692_CR36","unstructured":"Crooks, G.E.: Performance of the quantum approximate optimization algorithm on the maximum cut problem (2018). arXiv:1811.08419v1"},{"key":"2692_CR37","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 (2018). arXiv:1812.01041v1"},{"key":"2692_CR38","doi-asserted-by":"publisher","first-page":"3575","DOI":"10.1103\/PhysRevA.28.3575","volume":"28","author":"H De Raedt","year":"1983","unstructured":"De Raedt, H., De Raedt, B.: Applications of the generalized Trotter formula. Phys. Rev. A 28, 3575 (1983)","journal-title":"Phys. Rev. A"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02692-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-020-02692-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02692-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T20:06:04Z","timestamp":1622577964000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-020-02692-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,2]]},"references-count":38,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["2692"],"URL":"https:\/\/doi.org\/10.1007\/s11128-020-02692-8","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,2]]},"assertion":[{"value":"11 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"197"}}