Lower bounds on circuit depth of the quantum approximate optimization algorithm

Reducibility among Combinatorial Problems

Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511 · see citing works

Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913 · see citing works

Noise-induced barren plateaus in variational quantum algorithms

Wang, S., Fontana, E., Cerezo, M., Sharma, K., Sone, A., Cincio, L., & Coles, P. J. (2021) · Nature Communications · doi:10.1038/s41467-021-27045-6 · Cited by 773 · see citing works

Discrete cuckoo search algorithm for the travelling salesman problem

Ouaarab, A., Ahiod, B., & Yang, X. (2013) · Neural Computing and Applications · doi:10.1007/s00521-013-1402-2 · Cited by 454 · see citing works

Quantum approximate optimization algorithm for MaxCut: A fermionic view

Wang, Z., Hadfield, S., Jiang, Z., & Rieffel, E. G. (2018) · Physical Review A · doi:10.1103/physreva.97.022304 · Cited by 353 · see citing works

QAOA for Max-Cut requires hundreds of qubits for quantum speed-up

Guerreschi, G. G., & Matsuura, A. Y. (2019) · Scientific Reports · doi:10.1038/s41598-019-43176-9 · Cited by 337 · see citing works

Efficient Decomposition of Quantum Gates

Vartiainen, J. J., Möttönen, M., & Salomaa, M. M. (2004) · Physical Review Letters · doi:10.1103/physrevlett.92.177902 · Cited by 239 · see citing works

Asymptotic behavior of the chromatic index for hypergraphs

Pippenger, N. J., & Spencer, J. (1989) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(89)90074-5 · Cited by 205 · see citing works

Dose-response of different dietary leucine levels on growth performance and amino acid metabolism in piglets differing for aminoadipate-semialdehyde synthase genotypes

Bertocchi, M., Bosi, P., Luise, D., Motta, V., Salvarani, C., Ribani, A., Bovo, S., Simongiovanni, A., Matsunaga, K., Takimoto, T., et al. (2019) · Scientific Reports · doi:10.1038/s41598-019-55006-z · Cited by 195 · see citing works

<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>X</mml:mi><mml:mi>Y</mml:mi></mml:mrow></mml:math> mixers: Analytical and numerical results for the quantum alternating operator ansatz

Wang, Z., Rubin, N. C., Dominy, J. M., & Rieffel, E. G. (2020) · Physical Review A · doi:10.1103/physreva.101.012320 · Cited by 190 · see citing works

Unbounded knapsack problem: Dynamic programming revisited

Andonov, R., Poirriez, V., & Rajopadhye, S. V. (2000) · European Journal of Operational Research · doi:10.1016/s0377-2217(99)00265-9 · Cited by 163 · see citing works

A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem

Masutti, T. A. S., & de Castro, L. N. (2008) · Information Sciences · doi:10.1016/j.ins.2008.12.016 · Cited by 141 · see citing works

A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem

Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1412.6062 · Cited by 131 · see citing works

Training the quantum approximate optimization algorithm without access to a quantum processing unit

Streif, M., & Leib, M. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8c2b · Cited by 125 · cited 2× · see citing works

Multistart Methods for Quantum Approximate optimization

Shaydulin, R., Safro, I., & Larson, J. (2019) · 2019 IEEE High Performance Extreme Computing Conference (HPEC) · doi:10.1109/hpec.2019.8916288 · Cited by 110 · see citing works

Coloring nearly-disjoint hypergraphs with n + o(n) colors

Kahn, J. (1992) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(92)90096-d · Cited by 78 · see citing works

A quantum alternating operator ansatz with hard and soft constraints for lattice protein foldingPreprint

Fingerhuth, M., Babej, T., & Ing, C. E. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.13411 · Cited by 70 · see citing works

Characterizing local noise in QAOA circuits

Marshall, J., Wudarski, F., Hadfield, S., & Hogg, T. (2020) · IOP SciNotes · doi:10.1088/2633-1357/abb0d7 · Cited by 61 · see citing works

Hamiltonian gadgets with reduced resource requirements

Cao, Y., Babbush, R., Biamonte, J., & Kais, S. (2015) · Physical Review A · doi:10.1103/physreva.91.012315 · Cited by 35 · see citing works

Max-independent set and the quantum alternating operator ansatz

Saleem, Z. H. (2020) · International Journal of Quantum Information · doi:10.1142/s0219749920500112 · Cited by 28 · see citing works

Shortest path algorithms for knapsack type problems

FRIEZE, A. M. (1976) · Mathematical Programming · doi:10.1007/bf01580382 · Cited by 23 · see citing works

On the Degree, Size, and Chromatic Index of a Uniform Hypergraph

Alon, N., & Kim, J. H. (1997) · Journal of Combinatorial Theory Series A · doi:10.1006/jcta.1996.2728 · Cited by 15 · see citing works

ON EDGE COLORING OF HYPERGRAPHS AND ERDÖS–FABER–LOVÁSZ CONJECTURE

Paul, V., & Germina, K. A. (2012) · Discrete Mathematics Algorithms and Applications · doi:10.1142/s1793830912500036 · Cited by 10 · see citing works

The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover

Eidenbenz, S., Cook, J., & Baertschi, A. (2019) · doi:10.2172/1574737 · Cited by 9 · see citing works

A review on Quantum Approximate Optimization Algorithm and its variants

Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 444 · see citing works

Warm-starting quantum optimization

Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269 · see citing works

Multi-angle quantum approximate optimization algorithm

Herrman, R., Lotshaw, P. C., Ostrowski, J., Humble, T. S., & Siopsis, G. (2022) · Scientific Reports · doi:10.1038/s41598-022-10555-8 · Cited by 117 · see citing works

Empirical performance bounds for quantum approximate optimization

Lotshaw, P. C., Humble, T. S., Herrman, R., Ostrowski, J., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03342-3 · Cited by 59 · see citing works

A study of the performance of classical minimizers in the Quantum Approximate Optimization Algorithm

Fernández-Pendás, M., Combarro, E. F., Vallecorsa, S., Ranilla, J., & Rúa, I. F. (2022) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2021.113388 · Cited by 52 · see citing works

Quantum variational optimization: The role of entanglement and problem hardness

Díez-Valle, P., Porras, D., & García-Ripoll, J. J. (2021) · Physical Review A · doi:10.1103/physreva.104.062426 · Cited by 47 · see citing works

Impact of graph structures for QAOA on MaxCut

Herrman, R., Treffert, L., Ostrowski, J., Lotshaw, P. C., Humble, T. S., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03232-8 · Cited by 39 · see citing works

An expressive ansatz for low-depth quantum approximate optimisation

Vijendran, V., Das, A., Koh, D. E., Assad, S. M., & Lam, P. K. (2024) · Quantum Science and Technology · doi:10.1088/2058-9565/ad200a · Cited by 41 · see citing works

Scaling quantum approximate optimization on near-term hardware

Lotshaw, P. C., Nguyen, T., Santana, A., McCaskey, A., Herrman, R., Ostrowski, J., Siopsis, G., & Humble, T. S. (2022) · Scientific Reports · doi:10.1038/s41598-022-14767-w · Cited by 37 · see citing works

Approaches to Constrained Quantum Approximate Optimization

Saleem, Z. H., Tomesh, T., Tariq, B., & Suchara, M. (2023) · SN Computer Science · doi:10.1007/s42979-022-01638-4 · Cited by 25 · see citing works

Calibrating the role of entanglement in variational quantum circuits

Nakhl, A. C., Quella, T., & Usman, M. (2024) · Physical Review A · doi:10.1103/physreva.109.032413 · Cited by 22 · see citing works

Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study

Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works

Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer

Chalupnik, M., Melo, H., Alexeev, Y., & Galda, A. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00028 · Cited by 21 · see citing works

Domain-Specific Quantum Architecture Optimization

Lin, W.-H., Tan, D. B., Niu, M. Y., Kimko, J., & Cong, J. (2022) · IEEE Journal on Emerging and Selected Topics in Circuits and Systems · doi:10.1109/jetcas.2022.3202870 · Cited by 17 · see citing works

Solving MaxCut with quantum imaginary time evolution

Alam, R., Siopsis, G., Herrman, R., Ostrowski, J., Lotshaw, P. C., & Humble, T. S. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-04045-7 · Cited by 13 · see citing works

Performance analysis of multi-angle QAOA for $$p > 1$$

Gaidai, I., & Herrman, R. (2024) · Scientific Reports · doi:10.1038/s41598-024-69643-6 · Cited by 13 · see citing works

Automatic depth optimization for a quantum approximate optimization algorithm

Pan, Y., Tong, Y., & Yang, Y. (2022) · Physical Review A · doi:10.1103/physreva.105.032433 · Cited by 11 · see citing works

Characterization of variational quantum algorithms using free fermions

Matos, G., Self, C. N., Papić, Z., Meichanetzidis, K., & Dreyer, H. (2023) · Quantum · doi:10.22331/q-2023-03-30-966 · Cited by 10 · see citing works

Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

Ponce, M., Herrman, R., Lotshaw, P. C., Powers, S., Siopsis, G., Humble, T. S., & Ostrowski, J. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04675-z · Cited by 10 · see citing works

Modeling noise in global Mølmer-Sørensen interactions applied to quantum approximate optimization

Lotshaw, P. C., Battles, K. D., Gard, B., Buchs, G., Humble, T. S., & Herold, C. D. (2023) · Physical Review A · doi:10.1103/physreva.107.062406 · Cited by 6 · see citing works

The travelling salesperson problem and the challenges of near-term quantum advantage

Smith‐Miles, K., Hoos, H. H., Wang, H., Bäck, T., & Osborne, T. J. (2025) · Quantum Science and Technology · doi:10.1088/2058-9565/add61d · Cited by 6 · see citing works

Single entanglement connection architecture between multi-layer bipartite hardware efficient ansatz

Zhang, S., Qin, Z., Yang, Z., Li, R., Du, C., & Xiao, Z. (2024) · New Journal of Physics · doi:10.1088/1367-2630/ad64fb · Cited by 6 · see citing works

Enhancing quantum approximate optimization with CNN-CVaR integration

Cai, P., Shen, K., Yang, T., Hu, Y., Lv, B., Fan, L., Liu, Z., Hu, Q., Chen, S., Zhu, Y., et al. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04655-3 · Cited by 5 · see citing works

Quantum information processing with superconducting circuits: A perspective

Wendin, G. P. (2023) · Elsevier eBooks · doi:10.1016/b978-0-323-90800-9.00226-2 · Cited by 11 · see citing works

A universal quantum algorithm for weighted maximum cut and Ising problems

Meli, N. K., Mannel, F., & Lellmann, J. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-04025-x · Cited by 4 · see citing works

Recompiling QAOA Circuits on Various Rotational Directions

Jang, E., Ha, D., Choi, S., Kim, Y., Kwon, J., Lee, Y., Ahn, S., Kim, H. J., & Ro, W. W. (2024) · International Conference on Parallel Architectures and Compilation Techniques (PACT) · doi:10.1145/3656019.3676899 · Cited by 4 · see citing works

Towards Robust Benchmarking of Quantum Optimization Algorithms

Bucher, D., Kraus, N., Blenninger, J., Lachner, M., Stein, J., & Linnhoff–Popien, C. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.11030870 · Cited by 4 · see citing works

Efficient depth selection for the implementation of noisy quantum approximate optimization algorithm

Pan, Y., Tong, Y., Xue, S., & Zhang, G. (2022) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2022.10.027 · Cited by 4 · see citing works

Edge coloring lattice graphs

Kattemölle, J. (2025) · Journal of Mathematical Physics · doi:10.1063/5.0243007 · Cited by 3 · see citing works

Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems

Herrman, R., Treffert, L., Ostrowski, J., Lotshaw, P. C., Humble, T. S., & Siopsis, G. (2021) · Algorithms · doi:10.3390/a14100294 · Cited by 1 · see citing works

It’s Quick to be Square: Fast Quadratisation for Quantum Toolchains

Schmidbauer, L., Lobe, E., Schaefer, I., & Mauerer, W. (2026) · ACM Transactions on Quantum Computing · doi:10.1145/3800943 · Cited by 2 · see citing works

Improve the Quantum Approximate Optimization Algorithm with Genetic Algorithm

Phuc, N. H. H., Ta, A. S., & Nguyễn, V. H. (2023) · International Symposium on Information and Communication Technology · doi:10.1145/3628797.3628818

Quantum Circuit Optimization by Graph Coloring

Lee, H., Jeong, K. C., & Kim, P. (2026) · Quantum · doi:10.22331/q-2026-02-06-1996

Design of quantum approximation optimization algorithm for the maximum cut problem

Wang, Y.-J., Huiming, X., Zhuoyan, X., Zengbin, W., & Sha, S. H. I. (2025) · Acta Physica Sinica · doi:10.7498/aps.74.20241223

Quantum imaginary time evolution and the unit-disk maximum independent set problem

Penas, V. A., Losada, M., & Lamberti, P. W. (2025) · Physical Review A · doi:10.1103/physreva.111.042403

Depth Optimized Ansatz Circuit in QAOA for Max-CutPreprint

Majumdar, R., Bhoumik, D., Madan, D., Vinayagamurthy, D., Raghunathan, S., & Sur‐Kolay, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.04637 · Cited by 3 · see citing works

Quantum Approximate Optimization Algorithm for MaxCut: A Qiskit-Based Implementation and Analysis

Salti, M. S. A., & Asif, H. M. (2026) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-032-32862-5_1

An expressive ansatz for low-depth quantum approximate optimisation

Vijendran, V., Das, A., Koh, D. E., Assad, S. M., & Lam, P. K. (2024) · Quantum Science and Technology · doi:10.1088/2058-9565/ad200a · Cited by 41 · see citing works

A Depth-Independent Linear Chain Ansatz for Large-Scale Quantum Approximate OptimizationPreprint

Wang, Z., Mandell, J., Xu, Y., & Shi, J. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2509.17296

QAOA Circuit Depth Does Not Improve Fault Tree Analysis on NISQ Hardware: An Empirical Scaling StudyPreprint

Peters, D. (2026) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.18228000