The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
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.
Overview
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
Verification
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?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“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]
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.
Citations
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
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
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Quantum information and computation
Bennett, C. H., & DiVincenzo, D. P. (2000) · Nature · doi:10.1038/35005001 · Cited by 3,263
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
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
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
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
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
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
Research works printed but not linked: 3
- R. Shaydulin, 2019, Evaluating quantum approximate optimization algorithm: A case study, in 2019 Tenth International Green and Sustainable Computing Conference (IGSC)
- A. W. Marcus, 2015, Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science
- L. Eldar, 2017, Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
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
Noisy intermediate-scale quantum 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. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
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
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 563
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
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 362
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 359
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 293
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
“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 199
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
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
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 182
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 153
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
“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
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 116
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 127
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 193
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 117
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 106
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
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
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
NISQ Computers: A Path to Quantum Supremacy
AbuGhanem, M., & Eleuch, H. (2024) · IEEE Access · doi:10.1109/access.2024.3432330 · Cited by 94
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 182
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 76
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 80
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 92
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 81
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
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
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) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/2229681 · Cited by 65
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 70
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
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 67
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
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 55
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
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 54
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 54
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 82
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 60
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
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 50
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 45
Tate, R., Moondra, J., Gard, B., Mohler, G., & Gupta, S. (2023) · Quantum · doi:10.22331/q-2023-09-26-1121 · Cited by 59
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 49
Streif, M., Yarkoni, S., Skolik, A., Neukart, F., & Leib, M. (2021) · Physical Review A · doi:10.1103/physreva.104.012403 · Cited by 41
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 46
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 54
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
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 47
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 43
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
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 47
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
Ozaeta, A., van Dam, W., & McMahon, P. L. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac9013 · Cited by 57
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 41
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 46
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 50
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 43
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 44
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 41
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
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 36
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 36
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 41
Fast Black-Box Quantum State Preparation
Bausch, J. (2022) · Quantum · doi:10.22331/q-2022-08-04-773 · Cited by 30
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
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 32
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
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 42
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
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
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 28
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
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
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 42
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 41
Quantum supremacy and random circuitsPreprint
Movassagh, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.06210 · Cited by 60
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
“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 36
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
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 27
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
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
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 24
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
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
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 28
Quantum Approximate Optimization Algorithm (QAOA)
Fakhimi, R., & Validi, H. (2023) · Springer eBooks · doi:10.1007/978-3-030-54621-2_854-1 · Cited by 24
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0002 · Cited by 20
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
Aramyan, S., McGregor, K., Sandeep, S., & Haczku, A. (2022) · Frontiers in Immunology · doi:10.3389/fimmu.2022.945317 · Cited by 18
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
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 25
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 22
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 21
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
Metadata
- 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
- 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 › Physics and Astronomy › Atomic and Molecular Physics, and Optics › 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
