{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T08:42:24Z","timestamp":1774428144964,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T00:00:00Z","timestamp":1612137600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T00:00:00Z","timestamp":1612137600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/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"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s11128-021-03001-7","type":"journal-article","created":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T02:40:40Z","timestamp":1612924840000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["Lower bounds on circuit depth of the quantum approximate optimization algorithm"],"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":"James","family":"Ostrowski","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,2,9]]},"reference":[{"key":"3001_CR1","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)"},{"key":"3001_CR2","unstructured":"Guerreschi, G.G., Smelyanskiy, M.: Practical optimization for hybrid quantum-classical algorithms. arXiv preprint arXiv:1701.01450 (2017)"},{"key":"3001_CR3","doi-asserted-by":"crossref","unstructured":"Streif, M., Leib, M.: Training the quantum approximate optimization algorithm without access to a quantum processing unit. arXiv preprint arXiv:1908.08862 (2019)","DOI":"10.1088\/2058-9565\/ab8c2b"},{"key":"3001_CR4","doi-asserted-by":"crossref","unstructured":"Shaydulin, R., Safro, I., Larson, J.: Multistart methods for quantum approximate optimization. In: 2019 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1\u20138. IEEE (2019)","DOI":"10.1109\/HPEC.2019.8916288"},{"key":"3001_CR5","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv preprint arXiv:1412.6062 (2014)"},{"key":"3001_CR6","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. arXiv preprint arXiv:1812.01041 (2018)"},{"key":"3001_CR7","unstructured":"Fingerhuth, M., Babej, T., et al.: A quantum alternating operator ansatz with hard and soft constraints for lattice protein folding. arXiv preprint arXiv:1810.13411 (2018)"},{"key":"3001_CR8","doi-asserted-by":"crossref","unstructured":"Cook, J., Eidenbenz, S., B\u00e4rtschi, A.: The quantum alternating operator ansatz on max-k vertex cover. arXiv preprint arXiv:1910.13483 (2019)","DOI":"10.2172\/1574737"},{"key":"3001_CR9","unstructured":"Huang, H.-Y., Bharti, K., Rebentrost, P.: Near-term quantum algorithms for linear systems of equations. arXiv preprint arXiv:1909.07344 (2019)"},{"key":"3001_CR10","doi-asserted-by":"crossref","unstructured":"Saleem, Z.H.: Maximum independent set and quantum alternating operator ansatz. arXiv preprint arXiv:1905.04809 (2019)","DOI":"10.1142\/S0219749920500112"},{"issue":"2","key":"3001_CR11","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":"3001_CR12","unstructured":"Crooks, G.E.: Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419 (2018)"},{"key":"3001_CR13","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":"3001_CR14","unstructured":"Farhi, E., Harrow, A.W.: Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674 (2019)"},{"key":"3001_CR15","doi-asserted-by":"crossref","unstructured":"Wang, Z., Rubin, N.C., Dominy, J.M., Rieffel, E.G.: $$xy$$-mixers: analytical and numerical results for qaoa. arXiv preprint arXiv:1904.09314 (2019)","DOI":"10.1103\/PhysRevA.101.012320"},{"key":"3001_CR16","unstructured":"Xue, C., Chen, Z.-Y., Wu, Y.-C., Guo, G.-P.: Effects of quantum noise on quantum approximate optimization algorithm. arXiv preprint arXiv:1909.02196 (2019)"},{"key":"3001_CR17","doi-asserted-by":"crossref","unstructured":"Wang, S., Fontana, E., Cerezo, M., Sharma, K., Sone, A., Cincio, L., Coles, P.J.: Noise-induced barren plateaus in variational quantum algorithms. arXiv preprint arXiv:2007.14384 (2020)","DOI":"10.1038\/s41467-021-27045-6"},{"key":"3001_CR18","doi-asserted-by":"crossref","unstructured":"Marshall, J., Wudarski, F., Hadfield, S., Hogg, T.: Characterizing local noise in qaoa circuits. arXiv preprint arXiv:2002.11682 (2020)","DOI":"10.1088\/2633-1357\/abb0d7"},{"key":"3001_CR19","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Discret Anal. 3, 25\u201330 (1964)","journal-title":"Discret Anal."},{"key":"3001_CR20","unstructured":"Erd\u0151s, P.: Problems and results in graph theory and combinatorial analysis. In: Proceedings of the 5th British Combinatorial Conference, pp. 169\u2013192 (1975)"},{"issue":"01","key":"3001_CR21","doi-asserted-by":"publisher","first-page":"1250003","DOI":"10.1142\/S1793830912500036","volume":"4","author":"V Paul","year":"2012","unstructured":"Paul, V., Germina, K.A.: On edge coloring of hypergraphs and erd\u00f6s-faber-lov\u00e1sz conjecture. Discrete Math. Algorithms Appl. 4(01), 1250003 (2012)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"3001_CR22","unstructured":"Kahn, J.: Coloring nearly-disjoint hypergraphs with n+ o (n) colors. J. Comb. Theory, Ser. A 59(1), 31\u201339 (1992)"},{"key":"3001_CR23","unstructured":"Pippenger, Nicholas, Spencer, Joel: Asymptotic behavior of the chromatic index for hypergraphs. J. Comb. Theory, Ser. A 51(1), 24\u201342 (1989)"},{"key":"3001_CR24","unstructured":"Alon, N., Kim, J.H.: On the degree, size, and chromatic index of a uniform hypergraph. J. Comb. Theory, Ser. A 77(1), 165\u2013170 (1997)"},{"issue":"17","key":"3001_CR25","doi-asserted-by":"publisher","first-page":"177902","DOI":"10.1103\/PhysRevLett.92.177902","volume":"92","author":"JJ Vartiainen","year":"2004","unstructured":"Vartiainen, J.J., M\u00f6tt\u00f6nen, M., Salomaa, M.M.: Efficient decomposition of quantum gates. Phys. Rev. Lett. 92(17), 177902 (2004)","journal-title":"Phys. Rev. Lett."},{"key":"3001_CR26","unstructured":"Bullock, S.S., Markov, I.L.: Asymptotically optimal circuits for arbitrary n-qubit diagonal computations. arXiv preprint quant-ph\/0303039 (2008)"},{"issue":"1","key":"3001_CR27","doi-asserted-by":"publisher","first-page":"012315","DOI":"10.1103\/PhysRevA.91.012315","volume":"91","author":"Y Cao","year":"2015","unstructured":"Cao, Y., Babbush, R., Biamonte, J., Kais, S.: Hamiltonian gadgets with reduced resource requirements. Phys. Rev. A 91(1), 012315 (2015)","journal-title":"Phys. Rev. A"},{"key":"3001_CR28","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of computer computations, pp. 85\u2013103. Springer (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"2","key":"3001_CR29","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/S0377-2217(99)00265-9","volume":"123","author":"R Andonov","year":"2000","unstructured":"Andonov, R., Poirriez, V., Rajopadhye, S.: Unbounded knapsack problem: dynamic programming revisited. Eur. J. Oper. Res. 123(2), 394\u2013407 (2000)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"3001_CR30","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/BF01580382","volume":"11","author":"AM Frieze","year":"1976","unstructured":"Frieze, A.M.: Shortest path algorithms for knapsack type problems. Math. Program. 11(1), 150\u2013157 (1976)","journal-title":"Math. Program."},{"issue":"7\u20138","key":"3001_CR31","doi-asserted-by":"publisher","first-page":"1659","DOI":"10.1007\/s00521-013-1402-2","volume":"24","author":"A Ouaarab","year":"2014","unstructured":"Ouaarab, A., Ahiod, B., Yang, X.-S.: Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput. Appl. 24(7\u20138), 1659\u20131669 (2014)","journal-title":"Neural Comput. Appl."},{"issue":"10","key":"3001_CR32","doi-asserted-by":"publisher","first-page":"1454","DOI":"10.1016\/j.ins.2008.12.016","volume":"179","author":"TAS Masutti","year":"2009","unstructured":"Masutti, T.A.S., de Castro, L.N.: A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Inf. Sci. 179(10), 1454\u20131468 (2009)","journal-title":"Inf. Sci."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03001-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-021-03001-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03001-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T05:34:17Z","timestamp":1671168857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-021-03001-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["3001"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03001-7","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2]]},"assertion":[{"value":"10 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"59"}}