Obstacles to Variational Quantum Optimization from Symmetry Protection
Open accessAbstract
The quantum approximate optimization algorithm (QAOA) employs variational states generated by a parameterized quantum circuit to maximize the expected value of a Hamiltonian encoding a classical cost function. Whether or not the QAOA can outperform classical algorithms in some tasks is an actively debated question. Our work exposes fundamental limitations of the QAOA resulting from the symmetry and the locality of variational states. A surprising consequence of our results is that the classical Goemans-Williamson algorithm outperforms the QAOA for certain instances of MaxCut, at any constant level. To overcome these limitations, we propose a nonlocal version of the QAOA and give numerical evidence that it significantly outperforms the standard QAOA for frustrated Ising models.
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?
An empirical evaluation of recursive QAOA has demonstrated its superiority compared to the standard version and its competitiveness compared to the Newman benchmark algorithm for the Max-Cut problem.
“An empirical evaluation of recursive QAOA has demonstrated its superiority compared to the standard version as well as its competitiveness compared to the Newman benchmark algorithm [203] for the Max-Cut problem [23].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [23]
The numerical comparison in Additional information (page unavailable) reports that level-1 recursive QAOA outperformed Goemans–Williamson on 14 of 15 tested instances, while standard level-1 QAOA achieved ratios below 1/2. Those instances were random-coupling Ising problems, not the ordinary Max-Cut instances described in the claim, and this paper does not report a comparison with a Newman algorithm. (LLM, conf=0.88)
Experimental — accuracy not yet measured
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
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238 · see citing works
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552 · 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
Quantum information and computation
Bennett, C. H., & DiVincenzo, D. P. (2000) · Nature · doi:10.1038/35005001 · Cited by 3,263 · 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
Barren plateaus in quantum neural network training landscapes
McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H. (2018) · Nature Communications · doi:10.1038/s41467-018-07090-4 · Cited by 2,329 · see citing works
Entanglement spectrum of a topological phase in one dimension
Pollmann, F., Turner, A. M., Berg, E., & Oshikawa, M. (2010) · Physical Review B · doi:10.1103/physrevb.81.064439 · Cited by 1,341 · see citing works
On the computational complexity of Ising spin glass models
Barahona, F. (1982) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/15/10/028 · Cited by 1,303 · see citing works
Tensor-entanglement-filtering renormalization approach and symmetry-protected topological order
Gu, Z., & Wen, X.-G. (2009) · Physical Review B · doi:10.1103/physrevb.80.155131 · Cited by 1,002 · see citing works
Classifying quantum phases using matrix product states and projected entangled pair states
Schuch, N., Pérez-Garcı́a, D., & Cirac, J. I. (2011) · Physical Review B · doi:10.1103/physrevb.84.165139 · Cited by 794 · see citing works
Lieb-Robinson Bounds and the Generation of Correlations and Topological Quantum Order
Bravyi, S., Hastings, M. B., & Verstraete, F. (2006) · Physical Review Letters · doi:10.1103/physrevlett.97.050401 · Cited by 664 · see citing works
Self-citationQuantum 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
Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q
Morgenstern, M. (1994) · Journal of Combinatorial Theory Series B · doi:10.1006/jctb.1994.1054 · Cited by 315 · see citing works
Interlacing families I: Bipartite Ramanujan graphs of all degrees
Marcus, A. W., Spielman, D. A., & Srivastava, N. (2015) · Annals of Mathematics · doi:10.4007/annals.2015.182.1.7 · Cited by 227 · see citing works
Classical and Quantum Bounded Depth Approximation Algorithms
Hastings, M. B. (2019) · arXiv · doi:10.48550/arxiv.1905.07047 · Cited by 96 · see citing works
Classical and quantum bounded depth approximation algorithms
Hastings, M. B. (2019) · Quantum Information and Computation · doi:10.26421/qic19.13-14-3 · Cited by 65 · see citing works
Local Hamiltonians Whose Ground States Are Hard to Approximate
Eldar, L., & Harrow, A. W. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.46 · Cited by 58 · see citing works
Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemesPreprint
Mbeng, G. B., Fazio, R., & Santoro, G. E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.08948 · Cited by 35 · see citing works
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
Marcus, A. W., Spielman, D. A., & Srivastava, N. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.87 · Cited by 24 · see citing works
Quantum Circuit Depth Lower Bounds For Homological CodesPreprint
Aharonov, D., & Touati, Y. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.03912 · Cited by 9 · see citing works
Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground StatesPreprint
Nirkhe, C., Vazirani, U. V., & Yuen, H. (2018) · arXiv (Cornell University) · doi:10.4230/lipics.icalp.2018.91 · Cited by 7 · see citing works
Flagged first, then by citations
Research works printed but not linked: 6
- E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028. · arXiv
- R. Shaydulin and Y. Alexeev, Evaluating quantum approxi- mate optimization algorithm: A case study, in 2019 Tenth International Green and Sustainable Computing Conference (IGSC) (IEEE, New York, 2019), pp. 1-6.
- J. Friedman, arXiv:cs/0405020. · arXiv
- See Supplemental Material at http://link.aps.org/ supplemental/10.1103/PhysRevLett.125.260505 for further details on state preparation and implementation.
- E. Farhi, D. Gamarnik, and S. Gutmann, arXiv:2004.09002. · arXiv
- E. Farhi, D. Gamarnik, and S. Gutmann, arXiv:2005.08747. · arXiv
Cited by
Sorted by citations
Variational quantum algorithms
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., et al. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00348-9 · Cited by 3,385 · 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
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
Quantum Algorithm Implementations for Beginners
Jayakumar, A., Adedoyin, A. A., Ambrosiano, J. J., Anisimov, P. M., Casper, W., Chennupati, G., Coffrin, C., Djidjev, H. N., Gunter, D., Karra, S., et al. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3517340 · Cited by 299 · see citing works
Quantum Computing for High-Energy Physics: State of the Art and Challenges
Meglio, A. D., Jansen, K., Tavernelli, I., Alexandrou, C., Arunachalam, S., Bauer, C., Borras, K., Carrazza, S., Crippa, A., Croft, V. A., et al. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.037001 · Cited by 257 · 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
Challenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201 · see citing works
“57), which uses a quantum computer to produce a sequence of reduced problem instances.”
NISQ computing: where are we and where do we go?
Lau, J. W. Z., Lim, K. H., Shrotriya, H., & Kwek, L. C. (2022) · AAPPS bulletin · doi:10.1007/s43673-022-00058-z · Cited by 176 · see citing works
Exploiting Symmetry in Variational Quantum Machine Learning
Meyer, J. J., Mularski, M., Gil-Fuster, E., Mele, A. A., Arzani, F., Wilms, A., & Eisert, J. (2023) · PRX Quantum · doi:10.1103/prxquantum.4.010328 · Cited by 172 · see citing works
Noisy intermediate-scale quantum (NISQ) algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2021) · arXiv · doi:10.48550/arxiv.2101.08448 · Cited by 166 · 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
Prospects for quantum enhancement with diabatic quantum annealing
Crosson, E., & Lidar, D. A. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00313-6 · Cited by 137 · see citing works
Shaydulin, R., Li, C., Chakrabarti, S., DeCross, M., Herman, D., Kumar, N., Larson, J., Lykov, D., Minssen, P., Sun, Y., et al. (2024) · Science Advances · doi:10.1126/sciadv.adm6761 · Cited by 120 · see citing works
“Due to QAOA preserving the D 4 symmetry of the problem (80), this is a highly entangled state, which is hard to prepare (81).”
BackgroundParameter 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
Hybrid quantum-classical algorithms for approximate graph coloring
Bravyi, S. B., Kliesch, A., König, R., & Tang, E. (2022) · Quantum · doi:10.22331/q-2022-03-30-678 · Cited by 105 · see citing works
Self-citationScaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
Weidenfeller, J., Valor, L. C., Gacon, J., Tornow, C., Bello, L., Woerner, S., & Egger, D. J. (2022) · Quantum · doi:10.22331/q-2022-12-07-870 · Cited by 97 · see citing works
Exponentially tighter bounds on limitations of quantum error mitigation
Quek, Y., França, D. S., Khatri, S., Meyer, J. J., & Eisert, J. (2024) · Nature Physics · doi:10.1038/s41567-024-02536-7 · Cited by 121 · see citing works
The Quantum Wasserstein Distance of Order 1
Palma, G. D., Marvian, M., Trevisan, D., & Lloyd, S. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3076442 · Cited by 90 · see citing works
Limitations of Variational Quantum Algorithms: A Quantum Optimal Transport Approach
Palma, G. D., Marvian, M., Rouzé, C., & França, D. S. (2023) · PRX Quantum · doi:10.1103/prxquantum.4.010309 · Cited by 86 · 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
Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
Liu, X., Angone, A., Shaydulin, R., Safro, I., Alexeev, Y., & Cincio, L. (2022) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3140190 · 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
NISQ Computers: A Path to Quantum Supremacy
AbuGhanem, M., & Eleuch, H. (2024) · IEEE Access · doi:10.1109/access.2024.3432330 · Cited by 80 · see citing works
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical CasePreprint
Farhi, E., Gamarnik, D., & Gutmann, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.09002 · Cited by 106 · see citing works
The Quantum Wasserstein Distance of Order 1Preprint
Palma, G. D., Marvian, M., Trevisan, D., & Lloyd, S. (2021) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 74 · see citing works
Equivariant quantum circuits for learning on weighted graphs
Skolik, A., Cattelan, M., Yarkoni, S., Bäck, T., & Dunjko, V. (2023) · npj Quantum Information · doi:10.1038/s41534-023-00710-y · Cited by 70 · see citing works
Fast quantum circuit cutting with randomized measurements
Lowe, A., Medvidović, M., Hayes, A., Riordan, L. J. O. A., Bromley, T. R., Arrazola, J. M., & Killoran, N. (2023) · Quantum · doi:10.22331/q-2023-03-02-934 · Cited by 68 · see citing works
Bridging Classical and Quantum with SDP initialized warm-starts for QAOA
Tate, R., Farhadi, M., Herold, C. D., Mohler, G., & Gupta, S. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3549554 · Cited by 64 · 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
Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets
Lacroix, N., Hellings, C., Andersen, C. K., Paolo, A. D., Remm, A., Lazar, S., Krinner, S., Norris, G. J., Gabureac, M. S., Heinsoo, J., et al. (2020) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-b-000464528 · Cited by 59 · see citing works
Quantum Optimization: Potential, Challenges, and the Path Forward
Abbas, A., (NNSA), U. N. N. S. A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D., et al. (2023) · doi:10.2172/2229681 · Cited by 63 · 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
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
A Perspective on Protein Structure Prediction Using Quantum Computers
Doğa, H., Raubenolt, B. A., Cumbo, F., Joshi, J., DiFilippo, F. P., Qin, J., Blankenberg, D. J., & Shehab, O. (2024) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.4c00067 · Cited by 59 · see citing works
Quantum Optimization via Four-Body Rydberg Gates
Dlaska, C., Ender, K., Mbeng, G. B., Kruckenhauser, A., Lechner, W., & van Bijnen, R. (2022) · Physical Review Letters · doi:10.1103/physrevlett.128.120503 · Cited by 51 · 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
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case ExamplesPreprint
Farhi, E., Gamarnik, D., & Gutmann, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.08747 · Cited by 67 · see citing works
Graph neural network initialisation of quantum approximate optimisation
Jain, N., Coyle, B., Kashefi, E., & Kumar, N. (2022) · Quantum · doi:10.22331/q-2022-11-17-861 · Cited by 50 · see citing works
Variational quantum simulation for periodic materials
Yoshioka, N., Sato, T., Nakagawa, Y. O., Ohnishi, Y.-Y., & Mizukami, W. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.013052 · Cited by 49 · 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
Building spatial symmetries into parameterized quantum circuits for faster training
Sauvage, F., Larocca, M., Coles, P. J., & Cerezo, M. (2023) · Quantum Science and Technology · doi:10.1088/2058-9565/ad152e · 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
Low-Depth Mechanisms for Quantum Optimization
McClean, J. R., Harrigan, M. P., Mohseni, M., Rubin, N. C., Zhang, J., Boixo, S., Smelyanskiy, V., Babbush, R., & Neven, H. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.030312 · Cited by 45 · 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
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
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
Streif, M., Yarkoni, S., Skolik, A., Neukart, F., & Leib, M. (2021) · Physical Review A · doi:10.1103/physreva.104.012403 · Cited by 41 · see citing works
A Conceptual Architecture for a Quantum-HPC Middleware
Saurabh, N., Jha, S., & Luckow, A. (2023) · IEEE International Conference on Quantum Software (QSW) · doi:10.1109/qsw59989.2023.00023 · Cited by 41 · see citing works
Quantum-enhanced greedy combinatorial optimization solver
Dupont, M., Evert, B., Hodson, M. J., Sundar, B., Jeffrey, S., Yamaguchi, Y., Feng, D., Maciejewski, F. B., Hadfield, S., Alam, M. S., et al. (2023) · Science Advances · doi:10.1126/sciadv.adi0487 · Cited by 41 · see citing works
Symmetry-protected sign problem and magic in quantum phases of matter
Ellison, T. D., Kato, K., Liu, Z.-W., & Hsieh, T. H. (2021) · Quantum · doi:10.22331/q-2021-12-28-612 · Cited by 41 · see citing works
An efficient quantum proactive incremental learning algorithm
Li, L., Li, J., Song, Y., Qin, S., Wen, Q., & Gao, F. (2024) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-024-2501-4 · Cited by 41 · see citing works
Symmetry enhanced variational quantum spin eigensolver
Lyu, C., Xu, X., Yung, M., & Bayat, A. (2023) · Quantum · doi:10.22331/q-2023-01-19-899 · Cited by 41 · see citing works
Exploiting Symmetry Reduces the Cost of Training QAOA
Shaydulin, R., & Wild, S. M. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3066275 · Cited by 39 · 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
Quantum-Informed Recursive Optimization Algorithms
Finžgar, J. R., Kerschbaumer, A., Schuetz, M. J. A., Mendl, C. B., & Katzgraber, H. G. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.020327 · Cited by 40 · see citing works
Ozaeta, A., van Dam, W., & McMahon, P. L. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac9013 · Cited by 39 · see citing works
Assessing Quantum Computing Performance for Energy Optimization in a Prosumer Community
Mastroianni, C., Plastina, F., Scarcello, L., Settino, J., & Vinci, A. (2023) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2023.3286106 · Cited by 40 · see citing works
Optimized SWAP networks with equivalent circuit averaging for QAOA
Hashim, A., Rines, R., Omole, V., Naik, R., Kreikebaum, J. M., Santiago, D., Chong, F. T., Siddiqi, I. A., & Gokhale, P. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.033028 · Cited by 38 · 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
Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
Bechtold, M., Barzen, J., Leymann, F., Mandl, A., Obst, J., Truger, F., & Weder, B. (2023) · Quantum Science and Technology · doi:10.1088/2058-9565/acf59c · Cited by 35 · 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
Quantum 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
Approximate Solutions of Combinatorial Problems via Quantum Relaxations
Fuller, B., Hadfield, C. F., Glick, J. R., Imamichi, T., Itoko, T., Thompson, R. J., Jiao, Y., Kagele, M., Blom, A. W., Raymond, R., et al. (2024) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2024.3421294 · Cited by 35 · see citing works
Lumia, L., Torta, P., Mbeng, G. B., Santoro, G. E., Ercolessi, E., Burrello, M., & Wauters, M. M. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.020320 · Cited by 33 · 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
Reinforcement learning assisted recursive QAOA
Patel, Y. J., Jerbi, S., Bäck, T., & Dunjko, V. (2024) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-023-00214-w · Cited by 32 · see citing works
Fast Black-Box Quantum State Preparation
Bausch, J. (2022) · Quantum · doi:10.22331/q-2022-08-04-773 · Cited by 30 · see citing works
Secure and Reliable Big-Data-Based Decision Making Using Quantum Approach in IIoT Systems
Azzaoui, A. E., Salim, M. M., & Park, J. H. (2023) · Sensors · doi:10.3390/s23104852 · Cited by 26 · see citing works
Quantum Approximate Optimization Algorithm Pseudo-Boltzmann States
Díez-Valle, P., Porras, D., & García‐Ripoll, J. J. (2023) · Physical Review Letters · doi:10.1103/physrevlett.130.050601 · Cited by 26 · see citing works
Provable bounds for noise-free expectation values computed from noisy samples
Barron, S. V., Egger, D. J., Pelofske, E., Bärtschi, A., Eidenbenz, S., Lehmkuehler, M., & Woerner, S. (2024) · Nature Computational Science · doi:10.1038/s43588-024-00709-1 · Cited by 25 · see citing works
Quantum approximate multi-objective optimization
Kotil, A., Pelofske, E., Riedmüller, S., Egger, D. J., Eidenbenz, S., Koch, T., & Woerner, S. (2025) · Nature Computational Science · doi:10.1038/s43588-025-00873-y · Cited by 27 · see citing works
Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
Shaydulin, R., & Galda, A. (2021) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00046 · Cited by 24 · see citing works
Evolving objective function for improved variational quantum optimization
Kolotouros, I., & Wallden, P. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.023225 · Cited by 24 · see citing works
Quantum approximate optimization for combinatorial problems with constraints
Ruan, Y., Yuan, Z., Xue, X., & Liu, Z. (2022) · Information Sciences · doi:10.1016/j.ins.2022.11.020 · Cited by 26 · see citing works
Basso, J., Gamarnik, D., Mei, S., & Zhou, L. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00039 · Cited by 24 · see citing works
Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem
Palackal, L., Poggel, B., Wulff, M., Ehm, H., Lorenz, J. M., & Mendl, C. B. (2023) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00080 · Cited by 24 · see citing works
Golden, J. K., Bärtschi, A., O’Malley, D., & Eidenbenz, S. (2023) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00063 · Cited by 31 · see citing works
Scaling whole-chip QAOA for higher-order ising spin glass models on heavy-hex graphs
Pelofske, E., Bärtschi, A., Cincio, Ł., Golden, J. K., & Eidenbenz, S. (2024) · npj Quantum Information · doi:10.1038/s41534-024-00906-w · Cited by 24 · see citing works
Quantum supremacy and random circuitsPreprint
Movassagh, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.06210 · Cited by 30 · 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
“To overcome fundamental limitations of QAOA, like the ones mentioned in Section 4.1.4 (e.g., References [43, 44]), a drastically different, non-local version of QAOA is proposed by Bravyi et al. [23], which is called Recursive QAOA (RQAOA) .”
MethodInfluentialQuantum optimization for training quantum neural networks
Liao, Y., Hsieh, M.-H., & Ferrie, C. (2024) · Quantum Machine Intelligence · doi:10.1007/s42484-024-00169-w · Cited by 26 · see citing works
Bounds on approximating Max k XOR with quantum and classical local algorithms
Marwaha, K., & Hadfield, S. (2022) · Quantum · doi:10.22331/q-2022-07-07-757 · Cited by 23 · see citing works
Efficient variational synthesis of quantum circuits with coherent multi-start optimization
Nemkov, N. A., Kiktenko, E. O., Luchnikov, I. A., & Fedorov, A. K. (2023) · Quantum · doi:10.22331/q-2023-05-04-993 · Cited by 22 · 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
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
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
Extending relax-and-round combinatorial optimization solvers with quantum correlations
Dupont, M., & Sundar, B. (2024) · Physical Review A · doi:10.1103/physreva.109.012429 · Cited by 22 · see citing works
Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
Bae, E., & Lee, S. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04286-0 · Cited by 22 · see citing works
Maciejewski, F. B., Hadfield, S., Hall, B., Hodson, M. J., Dupont, M., Evert, B., Sud, J., Alam, M. S., Wang, Z., Jeffrey, S., et al. (2024) · Physical Review Applied · doi:10.1103/physrevapplied.22.044074 · Cited by 22 · 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
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0002 · Cited by 20 · see citing works
Practical Verification of Quantum Properties in Quantum-Approximate-Optimization Runs
Alam, M. S., Wudarski, F., Reagor, M. J., Sud, J., Grabbe, S. R., Wang, Z., Hodson, M. J., Lott, P. A., Rieffel, E. G., & Venturelli, D. (2022) · Physical Review Applied · doi:10.1103/physrevapplied.17.024026 · Cited by 19 · see citing works
Aramyan, S., McGregor, K., Sandeep, S., & Haczku, A. (2022) · Frontiers in Immunology · doi:10.3389/fimmu.2022.945317 · Cited by 19 · see citing works
Leveraging Knapsack QAOA Approach for Optimal Electric Vehicle Charging
Kea, K., Huot, C., & Han, Y. (2023) · IEEE Access · doi:10.1109/access.2023.3320800 · Cited by 18 · see citing works
Assessing and advancing the potential of quantum computing: A NASA case study
Rieffel, E. G., Asanjan, A. A., Alam, M. S., Anand, N., Bernal, D. E., Block, S., Brady, L. T., Cotton, S., Izquierdo, Z. G., Grabbe, S. R., et al. (2024) · Future Generation Computer Systems · doi:10.1016/j.future.2024.06.012 · Cited by 20 · see citing works
A SAT Approach to the Initial Mapping Problem in SWAP Gate Insertion for Commuting Gates
Matsuo, A., Yamashita, S., & Egger, D. J. (2023) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.2022eap1159 · Cited by 17 · see citing works
Solution of SAT problems with the adaptive-bias quantum approximate optimization algorithm
Yu, Y., Cao, C., Wang, X., Shannon, N., & Joynt, R. (2023) · Physical Review Research · doi:10.1103/physrevresearch.5.023147 · Cited by 17 · see citing works
Fair Sampling Error Analysis on NISQ Devices
Golden, J. K., Bärtschi, A., O’Malley, D., & Eidenbenz, S. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3510857 · Cited by 17 · see citing works
Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms
Wurtz, J., Sack, S. H., & Wang, S.-T. (2024) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2024.3443660 · Cited by 21 · see citing works
- Authors
- Bravyi, S., Kliesch, A., Koenig, R., & Tang, E.
- Affiliations
- IBM (United States) (US)
- Technical University of Munich (DE)
- California Institute of Technology (US)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2020-12-24
- Volume
- 125
- Issue
- 26
- Pages
- 260505-260505
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2980835754
- Cited by
- 278
- References
- 22
- Citations by year
- 2026: 23 · 2025: 50 · 2024: 52 · 2023: 71 · 2022: 42 · 2021: 31 · 2020: 8 · 2019: 1
- FWCI
- 14.93
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CaltechAUTHORS (California Institute of Technology) (submittedVersion)
- mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Army Research Office (W911NF-20-1-0014)
- Natural Sciences and Engineering Research Council of Canada
- National Science Foundation (PHY-1733907)
- Deutsche Forschungsgemeinschaft
- IBM Research Frontiers Institute
- 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, variational quantum optimization, symmetry protection, Goemans-Williamson algorithm, MaxCut, frustrated Ising model
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
