{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T18:43:12Z","timestamp":1791484992843,"version":"4.3.4"},"reference-count":26,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T00:00:00Z","timestamp":1633910400000},"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":"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":"United States Army Research Office","doi-asserted-by":"publisher","award":["W911NF-19-1-0397"],"award-info":[{"award-number":["W911NF-19-1-0397"]}],"id":[{"id":"10.13039\/100000183","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":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We develop a global variable substitution method that reduces n-variable monomials in combinatorial optimization problems to equivalent instances with monomials in fewer variables. We apply this technique to 3-SAT and analyze the optimal quantum unitary circuit depth needed to solve the reduced problem using the quantum approximate optimization algorithm. For benchmark 3-SAT problems, we find that the upper bound of the unitary circuit depth is smaller when the problem is formulated as a product and uses the substitution method to decompose gates than when the problem is written in the linear formulation, which requires no decomposition.<\/jats:p>","DOI":"10.3390\/a14100294","type":"journal-article","created":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T09:16:42Z","timestamp":1633943802000},"page":"294","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6944-4206","authenticated-orcid":false,"given":"Rebekah","family":"Herrman","sequence":"first","affiliation":[{"name":"Department of Industrial and Systems Engineering, University of Tennessee at Knoxville, Knoxville, TN 37996, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lorna","family":"Treffert","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, University of Tennessee at Knoxville, Knoxville, TN 37996, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Ostrowski","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, University of Tennessee at Knoxville, Knoxville, TN 37996, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7594-2735","authenticated-orcid":false,"given":"Phillip C.","family":"Lotshaw","sequence":"additional","affiliation":[{"name":"Quantum Computing Institute, Oak Ridge National Laboratory, Oak Ridge, TN 37830, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9449-0498","authenticated-orcid":false,"given":"Travis S.","family":"Humble","sequence":"additional","affiliation":[{"name":"Quantum Computing Institute, Oak Ridge National Laboratory, Oak Ridge, TN 37830, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George","family":"Siopsis","sequence":"additional","affiliation":[{"name":"Department of Physics and Astronomy, University of Tennessee at Knoxville, Knoxville, TN 37996-1200, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,10,11]]},"reference":[{"key":"ref_1","unstructured":"Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv."},{"key":"ref_2","unstructured":"Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Lotshaw, P.C., Humble, T.S., Herrman, R., Ostrowski, J., and Siopsis, G. (2021). Empirical Performance Bounds for Quantum Approximate Optimization. arXiv.","DOI":"10.1007\/s11128-021-03342-3"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11128-021-03232-8","article-title":"Impact of Graph Structures for QAOA on MaxCut","volume":"20","author":"Herrman","year":"2021","journal-title":"Quantum Inf. Process."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2050011","DOI":"10.1142\/S0219749920500112","article-title":"Max-independent set and the quantum alternating operator ansatz","volume":"18","author":"Saleem","year":"2020","journal-title":"Int. J. Quantum Inform."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"022304","DOI":"10.1103\/PhysRevA.97.022304","article-title":"Quantum approximate optimization algorithm for MaxCut: A fermionic view","volume":"97","author":"Wang","year":"2018","journal-title":"Phys. Rev. A"},{"key":"ref_7","unstructured":"Crooks, G.E. (2018). Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"6903","DOI":"10.1038\/s41598-019-43176-9","article-title":"QAOA for Max-Cut requires hundreds of qubits for quantum speed-up","volume":"9","author":"Guerreschi","year":"2019","journal-title":"Sci. Rep."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Cook, J., Eidenbenz, S., and B\u00e4rtschi, A. (2020). The quantum alternating operator ansatz on max-k vertex cover. Bull. Am. Phys. Soc., l65.","DOI":"10.1109\/QCE49297.2020.00021"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"104703","DOI":"10.1063\/1.5006525","article-title":"Hardware for dynamic quantum computing","volume":"88","author":"Ryan","year":"2017","journal-title":"Rev. Sci. Instrum."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"3305","DOI":"10.1073\/pnas.1618020114","article-title":"Experimental comparison of two quantum computing architectures","volume":"114","author":"Linke","year":"2017","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Liu, X., Angone, A., Shaydulin, R., Safro, I., Alexeev, Y., and Cincio, L. (2021). Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers. arXiv.","DOI":"10.1109\/TQE.2021.3140190"},{"key":"ref_13","unstructured":"Guerreschi, G.G. (2021). Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms. arXiv."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/s11128-021-03001-7","article-title":"Lower bounds on circuit depth of the quantum approximate optimization algorithm","volume":"20","author":"Herrman","year":"2021","journal-title":"Quantum Inf. Process."},{"key":"ref_15","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing","year":"1964","journal-title":"Discret. Anal."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","article-title":"A simplified NP-complete satisfiability problem","volume":"8","author":"Tovey","year":"1984","journal-title":"Discret. Appl. Math."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Marques-Silva, J. (2008, January 28\u201330). Practical applications of boolean satisfiability. Proceedings of the 2008 9th International Workshop on Discrete Event Systems, Gothenburg, Sweden.","DOI":"10.1109\/WODES.2008.4605925"},{"key":"ref_18","unstructured":"Hill, A.D., Hodson, M.J., Didier, N., and Reagor, M.J. (2021). Realization of arbitrary doubly-controlled quantum phase gates. arXiv."},{"key":"ref_19","first-page":"283","article-title":"SATLIB: An online resource for research on SAT","volume":"2000","author":"Hoos","year":"2000","journal-title":"Sat"},{"key":"ref_20","unstructured":"Farhi, E., and Harrow, A.W. (2019). Quantum supremacy through the quantum approximate optimization algorithm. arXiv."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"030302","DOI":"10.1088\/0256-307X\/38\/3\/030302","article-title":"Effects of quantum noise on quantum approximate optimization algorithm","volume":"38","author":"Xue","year":"2021","journal-title":"Chin. Phys. Lett."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Wang, S., Fontana, E., Cerezo, M., Sharma, K., Sone, A., Cincio, L., and Coles, P.J. (2020). Noise-Induced Barren Plateaus in Variational Quantum Algorithms. arXiv.","DOI":"10.1038\/s41467-021-27045-6"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"025208","DOI":"10.1088\/2633-1357\/abb0d7","article-title":"Characterizing local noise in QAOA circuits","volume":"1","author":"Marshall","year":"2020","journal-title":"IOP SciNotes"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, Springer.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref_25","unstructured":"Rockafellar, R.T. (2015). Convex Analysis, Princeton University Press."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0377-2217(96)00161-0","article-title":"Computational experience with approximation algorithms for the set covering problem","volume":"101","author":"Grossman","year":"1997","journal-title":"Eur. J. Oper. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/10\/294\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:11:35Z","timestamp":1760166695000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/10\/294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,11]]},"references-count":26,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2021,10]]}},"alternative-id":["a14100294"],"URL":"https:\/\/doi.org\/10.3390\/a14100294","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,11]]}}}