QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
Open accessAbstract
Computational quantum technologies are entering a new phase in which noisy intermediate-scale quantum computers are available, but are still too small to benefit from active error correction. Even with a finite coherence budget to invest in quantum information processing, noisy devices with about 50 qubits are expected to experimentally demonstrate quantum supremacy in the next few years. Defined in terms of artificial tasks, current proposals for quantum supremacy, even if successful, will not help to provide solutions to practical problems. Instead, we believe that future users of quantum computers are interested in actual applications and that noisy quantum devices may still provide value by approximately solving hard combinatorial problems via hybrid classical-quantum algorithms. To lower bound the size of quantum computers with practical utility, we perform realistic simulations of the Quantum Approximate Optimization Algorithm and conclude that quantum speedup will not be attainable, at least for a representative combinatorial problem, until several hundreds of qubits are available.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Several quantum machine learning algorithms based on parameterized quantum circuits have demonstrated superior performance and computational abilities compared to conventional algorithms.
“Several QML algorithms based on PQC have been proposed [21–27], demonstrating superior performance and computational abilities compared to conventional algorithms [28–31].”
From Medical image diagnosis based on adaptive Hybrid Quantum CNN (2023) · cites this paper as [24]
The Results section (“Comparison and performance crossover,” page unavailable) says the classical solver is much faster for the tested small instances. The Discussion estimates that QAOA might achieve a speedup only at a crossover involving several hundred to a few thousand qubits. The paper therefore does not demonstrate superior performance by PQC-based QML algorithms, as the cited clause claims. (LLM, conf=0.86)
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measuredGuerreschi and Matsuura found the point of quantum supremacy for QAOA to be in the order of several hundred to thousand qubits.
“With such peculiarities in mind, one should also view the results of Guerreschi and Matsuura, who found the point of quantum supremacy for QAOA to be in the order of several hundred to thousand of qubits [56] and further raised scaling issues [60].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [56]
The Discussion estimates a crossover between several hundred and a few thousand qubits for QAOA on Max-Cut instances from random 3-regular graphs. But the paper calls this a potential quantum speedup, not a point of quantum supremacy, and the Results (‘Comparison and performance crossover’) caution that the extrapolation may be unreliable. (LLM, conf=0.88)
Experimental — accuracy not yet measuredNoisy computation leads to scaling issues for QAOA.
“Noisy computation leads to scaling issues for QAOA [56, 60].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [56]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Braun, W. J., & Murdoch, D. J. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108993456.011 · Cited by 14,099 · see citing works
Nocedal, J., & Wright, S. J. (1999) · Springer eBooks · doi:10.1007/b98874 · Cited by 9,563 · see citing works
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830 · see citing works
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · cited 1× · see citing works
“Since quantum algorithms have a computational cost that is either polynomially [4] or exponentially lower [5] than their classical counterparts, for larger problem instances quantum algorithms provide an increasing advantage over classical approaches.”
BackgroundPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904 · see citing works
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · see citing works
Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets
Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M., & Gambetta, J. M. (2017) · Nature · doi:10.1038/nature23879 · Cited by 2,982 · see citing works
Superconducting Circuits for Quantum Information: An Outlook
Devoret, M., & Schoelkopf, R. J. (2013) · Science · doi:10.1126/science.1231930 · Cited by 2,122 · see citing works
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789 · see citing works
Superconducting quantum circuits at the surface code threshold for fault tolerance
Barends, R., Kelly, J., Megrant, A., Veitia, A., Sank, D., Jeffrey, E., White, T. C., Mutus, J., Fowler, A. G., Campbell, B., et al. (2014) · Nature · doi:10.1038/nature13171 · Cited by 1,733 · see citing works
Characterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175 · see citing works
Scalable Quantum Simulation of Molecular Energies
O’Malley, P. J. J., Babbush, R., Kivlichan, I. D., Romero, J., McClean, J. R., Barends, R., Kelly, J., Roushan, P., Tranter, A., Ding, N., et al. (2016) · Physical Review X · doi:10.1103/physrevx.6.031007 · Cited by 1,059 · see citing works
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
Evidence for quantum annealing with more than one hundred qubits
Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M. (2014) · Nature Physics · doi:10.1038/nphys2900 · Cited by 810 · see citing works
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772 · see citing works
Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz
Romero, J., Babbush, R., McClean, J. R., Hempel, C., Love, P. J., & Aspuru-Guzik, A. (2019) · Quantum Science and Technology · doi:10.1088/2058-9565/aad3e4 · Cited by 726 · see citing works
A blueprint for demonstrating quantum supremacy with superconducting qubits
Neill, C., Roushan, P., Kechedzhi, K., Boixo, S., Isakov, S. V., Smelyanskiy, V., Megrant, A., Chiaro, B., Dunsworth, A., Arya, K., et al. (2018) · Science · doi:10.1126/science.aao4309 · Cited by 451 · 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
Quantum Supremacy through the Quantum Approximate Optimization Algorithm
Farhi, E., & Harrow, A. W. (2016) · arXiv · doi:10.48550/arxiv.1602.07674 · Cited by 331 · see citing works
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308 · see citing works
Unsupervised Machine Learning on a Hybrid Quantum Computer
Otterbach, J. S., Manenti, R., Alidoust, N., Bestwick, A., Block, M., Bloom, B., Caldwell, S., Didier, N., Fried, E. S., Hong, S., et al. (2017) · arXiv · doi:10.48550/arxiv.1712.05771 · Cited by 263 · see citing works
qHiPSTER: The Quantum High Performance Software Testing EnvironmentPreprint
Smelyanskiy, M., Sawaya, N. P. D., & Aspuru‐Guzik, A. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1601.07195 · Cited by 173 · see citing works
Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
Crooks, G. E. (2018) · arXiv · doi:10.48550/arxiv.1811.08419 · Cited by 158 · see citing works
Compiling quantum circuits to realistic hardware architectures using temporal planners
Venturelli, D., Do, M., Rieffel, E. G., & Frank, J. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/aaa331 · Cited by 137 · see citing works
Practical optimization for hybrid quantum-classical algorithms
Guerreschi, G. G., & Smelyanskiy, M. (2017) · arXiv · doi:10.48550/arxiv.1701.01450 · Cited by 99 · see citing works
Self-citationQuantum Algorithms for Fixed Qubit Architectures
Farhi, E., Goldstone, J., Gutmann, S., & Neven, H. (2017) · arXiv · doi:10.48550/arxiv.1703.06199 · Cited by 93 · see citing works
0-1 Quadratic programming approach for optimum solutions of two scheduling problems
Alidaee, B., Kochenberger, G. A., & Ahmadian, A. (1994) · International Journal of Systems Science · doi:10.1080/00207729408928968 · Cited by 89 · see citing works
Improved Exact Solver for the Weighted MAX-SAT Problem
Kügel, A. (2018) · EPiC series in computing · doi:10.29007/38lm · Cited by 88 · see citing works
Two-step approach to scheduling quantum circuits
Guerreschi, G. G., & Park, J. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aacf0b · Cited by 80 · see citing works
Self-citationRestless Tuneup of High-Fidelity Qubit Gates
Rol, M. A., Bultink, C. C., O’Brien, T. E., de Jong, S. R., Theis, L. S., Fu, X., Luthi, F., Vermeulen, R. F. L., de Sterke, J. C., Bruno, A., et al. (2017) · Physical Review Applied · doi:10.1103/physrevapplied.7.041001 · Cited by 79 · see citing works
Hollingsworth, J. K. (2012) · Cited by 77 · see citing works
Neven, H., Rose, G., & Macready, W. G. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0804.4457 · Cited by 67 · see citing works
Max 2-SAT with up to 108 qubits
Santra, S., Quiroz, G., Steeg, G. V., & Lidar, D. A. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/4/045006 · Cited by 60 · see citing works
Applications of cut polyhedra — I
Deza, M. M., & Laurent, M. (1994) · Journal of Computational and Applied Mathematics · doi:10.1016/0377-0427(94)90020-5 · Cited by 58 · see citing works
Halperin, E., Livnat, D., & Zwick, U. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.06.001 · Cited by 53 · see citing works
Error Sensitivity to Environmental Noise in Quantum Circuits for Chemical State Preparation
Sawaya, N. P. D., Smelyanskiy, M., McClean, J. R., & Aspuru‐Guzik, A. (2016) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.6b00220 · Cited by 34 · see citing works
Noise gates for decoherent quantum circuits
Bassi, A., & Deckert, D.-A. (2008) · Physical Review A · doi:10.1103/physreva.77.032323 · Cited by 18 · see citing works
Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
Bazgan, C., & Tuza, Ź. (2007) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2007.02.002 · Cited by 8 · see citing works
Flagged first, then by citations
4 of the 42 references couldn’t be matched to a known paper.
Research works printed but not linked: 1
- [34]Mack, C. A. Learning and Intelligent Optimization. Springer-Verlag Berlin Heidelberg (2011).
Cited by
Sorted by citations
Parameterized quantum circuits as machine learning models
Benedetti, M., Lloyd, E., Sack, S., & Fiorentini, M. (2019) · Quantum Science and Technology · doi:10.1088/2058-9565/ab4eb5 · Cited by 1,324 · 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
Quantum Computing for Finance: State-of-the-Art and Future Prospects
Egger, D. J., Gambella, C., Marecek, J., McFaddin, S., Mevissen, M., Raymond, R., Simonetto, A., Woerner, S., & Yndurain, E. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3030314 · Cited by 422 · see citing works
Zhu, L., Tang, H. L., Barron, G. S., Calderon-Vargas, F. A., Mayhall, N. J., Barnes, E., & Economou, S. E. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.033029 · Cited by 245 · see citing works
Combinatorial optimization with physics-inspired graph neural networks
Schuetz, M. J. A., Brubaker, J. K., & Katzgraber, H. G. (2022) · Nature Machine Intelligence · doi:10.1038/s42256-022-00468-6 · Cited by 207 · see citing works
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
Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
Azad, U., Behera, B. K., Ahmed, E. A., Panigrahi, P. K., & Farouk, A. (2023) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2022.3172241 · Cited by 149 · see citing works
Ajagekar, A., & You, F. (2022) · Renewable and Sustainable Energy Reviews · doi:10.1016/j.rser.2022.112493 · Cited by 155 · see citing works
Quantum annealing initialization of the quantum approximate optimization algorithm
Sack, S. H., & Serbyn, M. (2021) · Quantum · doi:10.22331/q-2021-07-01-491 · Cited by 145 · see citing works
Benchmarking Quantum Computers and the Impact of Quantum Noise
Resch, S., & Karpuzcu, U. R. (2021) · ACM Computing Surveys · doi:10.1145/3464420 · Cited by 137 · see citing works
Intel Quantum Simulator: a cloud-ready high-performance simulator of quantum circuits
Guerreschi, G. G., Hogaboam, J., Baruffa, F., & Sawaya, N. P. D. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8505 · Cited by 129 · see citing works
Self-citationBenchmarking the quantum approximate optimization algorithm
Willsch, M., Willsch, D., Jin, F., De Raedt, H., & Michielsen, K. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02692-8 · Cited by 128 · see citing works
A Tutorial on Quantum Approximate Optimization Algorithm (QAOA): Fundamentals and Applications
Choi, J., & Kim, J. (2019) · International Conference on Information and Communication Technology Convergence (ICTC) · doi:10.1109/ictc46691.2019.8939749 · Cited by 123 · 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
Benchmarking the quantum approximate optimization algorithm
Willsch, M., Willsch, D., Jin, F., Raedt, H. A. D., & Michielsen, K. F. L. (2020) · RWTH Publications (RWTH Aachen) · Cited by 109 · see citing works
Benchmarking the performance of portfolio optimization with QAOA
Brandhofer, S., Braun, D., Dehn, V., Hellstern, G., Hüls, M., Ji, Y., Polian, I., Bhatia, A. S., & Wellens, T. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03766-5 · Cited by 106 · see citing works
Parameter concentrations in quantum approximate optimization
Akshay, V., Rabinovich, D., Campos, E., & Biamonte, J. (2021) · Physical Review A · doi:10.1103/physreva.104.l010401 · Cited by 103 · see citing works
Beyond quantum supremacy: the hunt for useful quantum computers
Brooks, M. (2019) · Nature · doi:10.1038/d41586-019-02936-3 · Cited by 103 · see citing works
Huang, H.-L., Xu, X., Guo, C., Tian, G., Wei, S.-J., Sun, X., Bao, W., & Long, G. (2023) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-022-2057-y · Cited by 101 · see citing works
Medical image diagnosis based on adaptive Hybrid Quantum CNN
Ajlouni, N., Özyavaş, A., Takaoğlu, M., Takaoğlu, F., & Ajlouni, F. (2023) · BMC Medical Imaging · doi:10.1186/s12880-023-01084-5 · Cited by 97 · 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
Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
Khairy, S., Shaydulin, R., Cincio, L., Alexeev, Y., & Balaprakash, P. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i03.5616 · Cited by 117 · see citing works
Biology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87 · see citing works
Self-citationQuantum Distributed Unit Commitment: An Application in Microgrids
Nikmehr, N., Zhang, P., & Bragin, M. A. (2022) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2022.3141794 · Cited by 88 · see citing works
Classical variational simulation of the Quantum Approximate Optimization Algorithm
Medvidović, M., & Carleo, G. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00440-z · Cited by 79 · see citing works
Nishi, H., Kosugi, T., & Matsushita, Y. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00409-y · Cited by 78 · see citing works
QAOA-in-QAOA: Solving Large-Scale MaxCut Problems on Small Quantum Machines
Zhou, Z.-F., Du, Y., Tian, X., & Tao, D. (2023) · Physical Review Applied · doi:10.1103/physrevapplied.19.024027 · Cited by 77 · see citing works
Efficient evaluation of quantum observables using entangled measurements
Hamamura, I., & Imamichi, T. (2020) · npj Quantum Information · doi:10.1038/s41534-020-0284-2 · Cited by 77 · see citing works
Optimizing quantum heuristics with meta-learning
Wilson, M., Stromswold, R., Wudarski, F., Hadfield, S., Tubman, N. M., & Rieffel, E. G. (2021) · Quantum Machine Intelligence · doi:10.1007/s42484-020-00022-w · Cited by 79 · see citing works
Hybrid quantum-classical-quantum convolutional neural networks
Long, C., Huang, M., Ye, X., Futamura, Y., & Sakurai, T. (2025) · Scientific Reports · doi:10.1038/s41598-025-13417-1 · Cited by 78 · see citing works
Classical symmetries and the Quantum Approximate Optimization Algorithm
Shaydulin, R., Hadfield, S., Hogg, T., & Safro, I. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03298-4 · Cited by 73 · 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
Network Community Detection on Small Quantum Computers
Shaydulin, R., Ushijima‐Mwesigwa, H., Safro, I., Mniszewski, S. M., & Alexeev, Y. (2019) · Advanced Quantum Technologies · doi:10.1002/qute.201900029 · Cited by 57 · see citing works
Efficient Encoding of the Weighted MAX $$k$$-CUT on a Quantum Computer Using QAOA
Fuchs, F. G., Kolden, H. Ø., Aase, N. H., & Sartor, G. (2021) · SN Computer Science · doi:10.1007/s42979-020-00437-z · Cited by 56 · see citing works
Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
Gambella, C., & Simonetto, A. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3033139 · Cited by 60 · 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
Machine Learning-Based Computational Design Methods for High-Entropy Alloys
Zhao, Y. M., Zhang, J. Y., Liaw, P. K., & Yang, T. (2025) · High Entropy Alloys & Materials · doi:10.1007/s44210-025-00055-5 · Cited by 54 · see citing works
Analyzing the performance of variational quantum factoring on a superconducting quantum processor
Karamlou, A. H., Simon, W., Katabarwa, A., Scholten, T. L., Peropadre, B., & Cao, Y. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00478-z · Cited by 52 · see citing works
An Image Classification Algorithm Based on Hybrid Quantum Classical Convolutional Neural Network
Li, W., Chu, P.-C., Liu, G.-Z., Tian, Y., Qiu, T., & Wang, S. (2022) · Quantum Engineering · doi:10.1155/2022/5701479 · Cited by 54 · see citing works
To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
Moussa, C., Calandra, H., & Dunjko, V. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/abb8e5 · Cited by 50 · see citing works
Quantum Algorithms for Mixed Binary Optimization Applied to Transaction Settlement
Braine, L., Egger, D. J., Glick, J., & Woerner, S. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3063635 · Cited by 51 · see citing works
Challenges of variational quantum optimization with measurement shot noise
Scriva, G., Astrakhantsev, N., Pilati, S., & Mazzola, G. (2024) · Physical Review A · doi:10.1103/physreva.109.032408 · Cited by 51 · see citing works
Carollo, F., & Alba, V. (2022) · Physical review. B./Physical review. B · doi:10.1103/physrevb.106.l220304 · Cited by 48 · see citing works
Li, A., Fang, B., Granade, C., Prawiroatmodjo, G., Heim, B., Roetteler, M., & Krishnamoorthy, S. (2021) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3458817.3476169 · Cited by 46 · see citing works
Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm
Fuchs, F. G., Lye, K. O., Nilsen, H. M., Stasik, A. J., & Sartor, G. (2022) · Algorithms · doi:10.3390/a15060202 · Cited by 47 · see citing works
Short-depth QAOA circuits and quantum annealing on higher-order ising models
Pelofske, E., Bärtschi, A., & Eidenbenz, S. (2024) · npj Quantum Information · doi:10.1038/s41534-024-00825-w · Cited by 49 · see citing works
Towards large-scale quantum optimization solvers with few qubits
Sciorilli, M., Borges, L., Patti, T. L., García-Martín, D., Camilo, G., Anandkumar, A., & Aolita, L. (2025) · Nature Communications · doi:10.1038/s41467-024-55346-z · Cited by 47 · see citing works
Training saturation in layerwise quantum approximate optimization
Campos, E., Rabinovich, D., Akshay, V., & Biamonte, J. (2021) · Physical Review A · doi:10.1103/physreva.104.l030401 · Cited by 44 · see citing works
The Quantum Approximate Algorithm for Solving Traveling Salesman Problem
Ruan, Y., Marsh, S., Xue, X., Liu, Z., & Wang, J. B. (2020) · Computers, materials & continua/Computers, materials & continua (Print) · doi:10.32604/cmc.2020.010001 · Cited by 44 · see citing works
Tate, R., Moondra, J., Gard, B., Mohler, G., & Gupta, S. (2023) · Quantum · doi:10.22331/q-2023-09-26-1121 · Cited by 44 · see citing works
Maciejewski, F. B., Baccari, F., Zimborás, Z., & Oszmaniec, M. (2021) · Quantum · doi:10.22331/q-2021-06-01-464 · Cited by 46 · see citing works
Large-Scale Quantum Approximate Optimization via Divide-and-Conquer
Li, J., Alam, M., & Ghosh, S. (2022) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2022.3212196 · Cited by 43 · see citing works
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
Weggemans, J. R., Urech, A., Rausch, A., Spreeuw, R. J. C., Boucherie, R. J., Schreck, F., Schoutens, K., Minář, J., & Speelman, F. (2022) · Quantum · doi:10.22331/q-2022-04-13-687 · Cited by 41 · see citing works
Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection
Cui, J., Xiong, Y., Ng, S. X., & Hanzo, L. (2022) · IEEE Transactions on Communications · doi:10.1109/tcomm.2022.3185287 · Cited by 41 · see citing works
Entanglement perspective on the quantum approximate optimization algorithm
Dupont, M., Didier, N., Hodson, M. J., Moore, J. E., & Reagor, M. J. (2022) · Physical Review A · doi:10.1103/physreva.106.022423 · Cited by 39 · see citing works
An Efficient Circuit Compilation Flow for Quantum Approximate Optimization Algorithm
Alam, M., Saki, A. A., & Ghosh, S. (2020) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac18072.2020.9218558 · Cited by 39 · see citing works
Applying the quantum approximate optimization algorithm to the minimum vertex cover problem
Zhang, Y., Mu, X. D., Liu, X., Wang, X., Zhang, X., Li, K., Wu, T., Zhao, D., & Dong, C. (2022) · Applied Soft Computing · doi:10.1016/j.asoc.2022.108554 · Cited by 38 · see citing works
A practitioner’s guide to quantum algorithms for optimisation problems
Symons, B. C. B., Galvin, D., Sahin, E., Alexandrov, V., & Mensa, S. (2023) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ad00f0 · Cited by 37 · 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
Variational quantum algorithms: fundamental concepts, applications and challenges
Qi, H., Xiao, S., Liu, Z., Gong, C., & Gani, A. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04438-2 · Cited by 40 · 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
New frontiers of quantum computing in chemical engineering
Ajagekar, A., & You, F. (2022) · Korean Journal of Chemical Engineering · doi:10.1007/s11814-021-1027-6 · Cited by 38 · see citing works
Urgelles, H., Picazo-Martínez, P., García‐Roger, D., & Monserrat, J. F. (2022) · Sensors · doi:10.3390/s22197570 · Cited by 36 · see citing works
Lower bounds on circuit depth of the quantum approximate optimization algorithm
Herrman, R., Ostrowski, J., Humble, T. S., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03001-7 · Cited by 35 · see citing works
Quantum Computing in Supply Chain Management State of the Art and Research Directions
Gachnang, P., Ehrenthal, J. C. F., Hanne, T., & Dornberger, R. (2022) · Asian Journal of Logistics Management · doi:10.14710/ajlm.2022.14325 · Cited by 47 · see citing works
Lykov, D., Wurtz, J., Poole, C., Saffman, M. E., Noel, T., & Alexeev, Y. (2023) · npj Quantum Information · doi:10.1038/s41534-023-00718-4 · Cited by 37 · see citing works
Quantum Divide and Compute: Exploring the Effect of Different Noise Sources
Ayral, T., Régent, F.-M. L., Saleem, Z. H., Alexeev, Y., & Suchara, M. (2021) · SN Computer Science · doi:10.1007/s42979-021-00508-9 · Cited by 35 · see citing works
Ajagekar, A., & You, F. (2024) · Applied Energy · doi:10.1016/j.apenergy.2024.123244 · Cited by 34 · see citing works
Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
Lee, X., Saito, Y., Cai, D., & Asai, N. (2021) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00016 · Cited by 37 · see citing works
Solving various NP-hard problems using exponentially fewer qubits on a quantum computer
Chatterjee, Y., Bourreau, E., & Rančić, M. J. (2024) · Physical Review A · doi:10.1103/physreva.109.052441 · Cited by 37 · see citing works
Evaluation of QAOA based on the approximation ratio of individual samples
Larkin, J. M., Jonsson, M., Justice, D., & Guerreschi, G. G. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac6973 · Cited by 40 · see citing works
Self-citationQuantum approximate optimization algorithm with adaptive bias fields
Yu, Y., Cao, C., Dewey, C., Wang, X., Shannon, N., & Joynt, R. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.023249 · Cited by 33 · see citing works
Maciejewski, F. B., Baccari, F., Zimborás, Z., & Oszmaniec, M. (2021) · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · Cited by 33 · see citing works
Alam, M., Ash-Saki, A., & Ghosh, S. (2019) · arXiv · doi:10.48550/arxiv.1907.09631 · Cited by 33 · see citing works
Serret, M. F., Marchand, B., & Ayral, T. (2020) · Physical Review A · doi:10.1103/physreva.102.052617 · Cited by 32 · see citing works
Zhao, Z., Fan, L., & Han, Z. (2023) · IEEE Transactions on Sustainable Energy · doi:10.1109/tste.2023.3309244 · Cited by 32 · see citing works
Parity Quantum Optimization: Compiler
Ender, K., ter Hoeven, R., Niehoff, B. E., Drieb-Schön, M., & Lechner, W. (2023) · Quantum · doi:10.22331/q-2023-03-17-950 · Cited by 37 · see citing works
Analytical framework for quantum alternating operator ansätze
Hadfield, S., Hogg, T., & Rieffel, E. G. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/aca3ce · Cited by 28 · see citing works
Meta-learning digitized-counterdiabatic quantum optimization
Chandarana, P., Vieites, P. S., Hegade, N. N., Solano, E., Ban, Y., & Chen, X. (2023) · Quantum Science and Technology · doi:10.1088/2058-9565/ace54a · Cited by 28 · see citing works
NAPA: Intermediate-Level Variational Native-Pulse Ansatz for Variational Quantum Algorithms
Liang, Z., Cheng, J., Ren, H., Wang, H., Hua, F., Song, Z., Ding, Y., Chong, F. T., Han, S., Qian, X., et al. (2024) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2024.3355277 · Cited by 38 · see citing works
Subdivided Phase Oracle for NISQ Search Algorithms
Satoh, T., Ohkura, Y., & Meter, R. V. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3012068 · Cited by 27 · see citing works
Quantum approximate optimization for hard problems in linear algebra
Borle, A., Elfving, V. E., & Lomonaco, S. J. (2021) · SciPost Physics Core · doi:10.21468/scipostphyscore.4.4.031 · Cited by 32 · see citing works
Demonstration of Weighted-Graph Optimization on a Rydberg-Atom Array Using Local Light Shifts
de Oliveira, A. G., Diamond-Hitchcock, E., Walker, D. M., Wells-Pestell, M. T., Pelegrí, G., Picken, C., Malcolm, G. P. A., Daley, A. J., Bass, J., & Pritchard, J. D. (2025) · PRX Quantum · doi:10.1103/prxquantum.6.010301 · Cited by 26 · see citing works
Quantum computation and simulation with superconducting qubits*
He, K., Geng, X., Huang, R., Liu, J., & Chen, W. (2021) · Chinese Physics B · doi:10.1088/1674-1056/ac16cf · Cited by 24 · see citing works
Quantum Robustness Verification: A Hybrid Quantum-Classical Neural Network Certification Algorithm
Franco, N., Wollschläger, T., Gao, N., Lorenz, J. M., & Günnemann, S. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00033 · Cited by 23 · see citing works
Zhou, X., Zhao, H. Q., Cao, Y., Fei, X., Liang, G., & Zhao, J. (2024) · Energy Conversion and Economics · doi:10.1049/enc2.12122 · Cited by 23 · see citing works
Topology-driven quantum architecture search framework
Su, J., Fan, J., Wu, S., Li, G., Qin, S., & Gao, F. (2025) · Science China Information Sciences · doi:10.1007/s11432-024-4486-x · Cited by 24 · see citing works
Quantum inverse iteration algorithm for programmable quantum simulators
Kyriienko, O. (2025) · Figshare · Cited by 27 · 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
Multilevel Leapfrogging Initialization Strategy for Quantum Approximate Optimization Algorithm
Ni, X., Cai, B., Liu, H., Qin, S., Gao, F., & Wen, Q. (2024) · Advanced Quantum Technologies · doi:10.1002/qute.202300419 · Cited by 23 · see citing works
A Quantum Planner for Robot Motion
Chella, A., Gaglio, S., Pilato, G., Vella, F., & Zammuto, S. (2022) · Mathematics · doi:10.3390/math10142475 · Cited by 21 · see citing works
An introduction to variational quantum algorithms for combinatorial optimization problems
Grange, C., Poss, M., & Bourreau, E. (2023) · 4OR · doi:10.1007/s10288-023-00549-1 · 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
“Noisy computation leads to scaling issues for QAOA [56, 60].”
BackgroundEnergy-Efficient Cluster Head Selection via Quantum Approximate Optimization
Choi, J., Oh, S., & Kim, J. (2020) · Electronics · doi:10.3390/electronics9101669 · Cited by 20 · see citing works
Variational quantum optimization with multibasis encodings
Patti, T. L., Kossaifi, J., Anandkumar, A., & Yelin, S. F. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.033142 · Cited by 21 · see citing works
Proietti, M., Cerocchi, F., & Dispenza, M. (2022) · Physical Review A · doi:10.1103/physreva.106.022437 · Cited by 20 · see citing works
Rančić, M. J. (2023) · Physical Review Research · doi:10.1103/physrevresearch.5.l012021 · Cited by 19 · see citing works
A Depth-Progressive Initialization Strategy for Quantum Approximate Optimization Algorithm
Lee, X., Xie, N., Cai, D., Saito, Y., & Asai, N. (2023) · Mathematics · doi:10.3390/math11092176 · Cited by 20 · see citing works
Error mitigation for quantum approximate optimization
Weidinger, A., Mbeng, G. B., & Lechner, W. (2023) · Physical Review A · doi:10.1103/physreva.108.032408 · Cited by 21 · see citing works
Quantum Approximate Optimization Algorithm (QAOA)
Fakhimi, R., & Validi, H. (2023) · Springer eBooks · doi:10.1007/978-3-030-54621-2_854-1 · Cited by 22 · see citing works
- Authors
- Guerreschi, G. G., & Matsuura, A. Y.
- Affiliations
- Intel (United States) (US)
- Corresponding author
- Guerreschi, G. G.
- Venue
- Scientific Reports
- Published
- 2019-05-06
- Volume
- 9
- Issue
- 1
- Pages
- 6903-6903
- ISSN
- 2045-2322 (ISSN-L)
- PMC
- PMC6502860
- OpenAlex
- W2951211905
- Cited by
- 337
- References
- 42
- Citations by year
- 2026: 18 · 2025: 57 · 2024: 45 · 2023: 88 · 2022: 50 · 2021: 47 · 2020: 24 · 2019: 8
- FWCI
- 14.71
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Scientific Reports (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- arXiv (Cornell University)
- Funders
- U.S. Department of Energy (-AC02-05CH11231, Contract No. DE-AC02-05-CH11231, 05CH11231, No. DE-AC02-05-CH11231, DE AC02 05CH11231, DE-AC02-)
- University of Texas at Austin
- National Energy Research Scientific Computing Center (DE–AC02–05CH11231, 05CH11231, AC02-05CH11231, Contract No. DE-AC02-05CH11231)
- Office of Science (No. DE-AC02- 05-CH11231, DEAC02–05CH11231, AC02-05CH11231, DE-AC02, 05CH11231, Contract No. DE-AC02-05CH11231)
- Department of Mechanical Engineering, University of Texas at Austin
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- quantum approximate optimization algorithm, MaxCut, quantum advantage, qubit requirements, NISQ devices, hybrid quantum-classical algorithms, combinatorial optimization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
