The DOI matches its DataCite record; 32 of the 34 references it cites were found in a registry or an index.
Quantum Supremacy through the Quantum Approximate Optimization Algorithm
Open accessAbstract
The Quantum Approximate Optimization Algorithm (QAOA) is designed to run on a gate model quantum computer and has shallow depth. It takes as input a combinatorial optimization problem and outputs a string that satisfies a high fraction of the maximum number of clauses that can be satisfied. For certain problems the lowest depth version of the QAOA has provable performance guarantees although there exist classical algorithms that have better guarantees. Here we argue that beyond its possible computational value the QAOA can exhibit a form of Quantum Supremacy in that, based on reasonable complexity theoretic assumptions, the output distribution of even the lowest depth version cannot be efficiently simulated on any classical device. We contrast this with the case of sampling from the output of a quantum computer running the Quantum Adiabatic Algorithm (QADI) with the restriction that the Hamiltonian that governs the evolution is gapped and stoquastic. Here we show that there is an oracle that would allow sampling from the QADI but even with this oracle, if one could efficiently classically sample from the output of the QAOA, the Polynomial Hierarchy would collapse. This suggests that the QAOA is an excellent candidate to run on near term quantum computers not only because it may be of use for optimization but also because of its potential as a route to establishing quantum supremacy.
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 cited source says what the claim attributes to it.
In the citing paper
“The quantum advantage of QAOA algorithm has been studied in (Farhi and Harrow, 2016), where they showed that the efficient sampling of the output distribution of QAOA, even for the lowest depth case of p = 1 , implies the collapse of the polynomial hierarchy (see Sec. I.A).”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Farhi and Harrow, 2016
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
Ladd, T. D., Jelezko, F., Laflamme, R., Nakamura, Y., Monroe, C., & O’Brien, J. L. (2010) · Nature · doi:10.1038/nature08812 · Cited by 3,592
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,374
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789
Self-citationEvidence 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
Defining and detecting quantum speedup
Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014) · Science · doi:10.1126/science.1252319 · Cited by 601 · cited 2×
“In fact this procedure can be viewed as a classical algorithm for finding the minimum of −C and is sometimes referred to as SQA for Simulated Quantum Annealing [8, 15,21,31].”
MethodQuantum Computation by Adiabatic Evolution
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000) · arXiv · doi:10.48550/arxiv.quant-ph/0001106 · Cited by 536 · cited 6×
“With the Quantum Adiabatic Algorithm in optimization mode, we are seeking the maximum of the cost function C given by (2).”
MethodInfluentialSelf-citationAdiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447323 · Cited by 457
Research works printed but not linked: 1
- [3][3] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing , 9(4):143-252, 2013, arXiv:1011.3245 . - · arXiv
Cited by
Sorted by citations
Items 101–200 of 346
Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
Verdon, G., Marks, J., Nanda, S., Leichenauer, S., & Hidary, J. (2019) · arXiv · doi:10.48550/arxiv.1910.02071 · Cited by 45
Oszmaniec, M., Dangniam, N., Morales, M. E. S., & Zimborás, Z. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.020328 · Cited by 63
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
Experimental Quantum Advantage with Quantum Coupon Collector
Zhou, M.-G., Cao, X., Lu, Y.-S., Wang, Y., Bao, Y., Jia, Z.-Y., Fu, Y., Yin, H., & Chen, Z. (2022) · Research · doi:10.34133/2022/9798679 · Cited by 43
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
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 47
Quantum computing for chemistry and physics applications from a Monte Carlo perspective
Mazzola, G. (2024) · The Journal of Chemical Physics · doi:10.1063/5.0173591 · Cited by 48
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
Generalized quantum assisted simulator
Haug, T., & Bharti, K. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac83e7 · Cited by 49
VSQL: Variational Shadow Quantum Learning for Classification
Li, G., Song, Z., & Wang, X. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i9.17016 · Cited by 43
A Grover-search based quantum learning scheme for classification
Du, Y., Hsieh, M.-H., Liu, T., & Tao, D. (2021) · New Journal of Physics · doi:10.1088/1367-2630/abdefa · Cited by 46
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
Generalized Quantum Assisted Simulator
Haug, T., & Bharti, K. (2020) · arXiv · doi:10.48550/arxiv.2011.14737 · Cited by 38
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 43
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
Patel, T., Potharaju, A., Li, B., Roy, R. B., & Tiwari, D. (2020) · SC20: International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc41405.2020.00050 · Cited by 37
GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
Willsch, D., Willsch, M., Jin, F., Michielsen, K. F. L., & Raedt, H. A. D. (2022) · Computer Physics Communications · doi:10.1016/j.cpc.2022.108411 · Cited by 48
Quantum semi-supervised generative adversarial network for enhanced data classification
Nakaji, K., & Yamamoto, N. (2021) · Scientific Reports · doi:10.1038/s41598-021-98933-6 · Cited by 39
Quantum Algorithms for Scientific Computing and Approximate OptimizationPreprint
Hadfield, S. (2018) · arXiv (Cornell University) · doi:10.7916/d8x650c9 · Cited by 76
Comparison of QAOA with Quantum and Simulated Annealing
Streif, M., & Leib, M. (2019) · arXiv · doi:10.48550/arxiv.1901.01903 · Cited by 35
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
Mitarai, K., Yan, T., & Fujii, K. (2019) · Physical Review Applied · doi:10.1103/physrevapplied.11.044087 · Cited by 32
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 45
Bouchmal, O., Cimoli, B., Stabile, R., Olmos, J. J. V., & Monroy, I. T. (2023) · Frontiers in Communications and Networks · doi:10.3389/frcmn.2023.1220227 · Cited by 37
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
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
Ultrafast variational simulation of nontrivial quantum states with long-range interactions
Ho, W. W., Jonay, C., & Hsieh, T. H. (2019) · Physical Review A · doi:10.1103/physreva.99.052332 · Cited by 46
AccQOC: Accelerating Quantum Optimal Control Based Pulse Generation
Cheng, J., Deng, H., & Qia, X. (2020) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca45697.2020.00052 · Cited by 37
Community Detection Across Emerging Quantum ArchitecturesPreprint
Shaydulin, R., Ushijima‐Mwesigwa, H., Safro, I., Mniszewski, S. M., & Alexeev, Y. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.07765 · Cited by 34
Peptide conformational sampling using the Quantum Approximate Optimization Algorithm
Boulebnane, S., Lucas, X., Meyder, A., Adaszewski, S., & Montanaro, A. (2023) · npj Quantum Information · doi:10.1038/s41534-023-00733-5 · Cited by 32
Channel Decoding with Quantum Approximate Optimization Algorithm
Matsumine, T., Koike–Akino, T., & Wang, Y. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849710 · Cited by 31
Noisy intermediate-scale quantum algorithm for semidefinite programming
Bharti, K., Haug, T., Vedral, V., & Kwek, L. C. (2022) · Physical Review A · doi:10.1103/physreva.105.052445 · Cited by 39
Explicit Lower Bounds on Strong Quantum Simulation
Huang, C., Newman, M., & Szegedy, M. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3004427 · Cited by 46
Quantum Kitchen Sinks: An algorithm for machine learning on near-term quantum computersPreprint
Wilson, C. M., Otterbach, J., Tezak, N., Smith, R., Polloreno, A., Karalekas, P. J., Heidel, S., Alam, M., Crooks, G. E., & Silva, M. P. D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.08321 · Cited by 68
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
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 30
Learning Unitaries by Gradient DescentPreprint
Kiani, B. T., Lloyd, S., & Maity, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.11897 · Cited by 44
Further extensions of Clifford circuits and their classical simulation complexities
Koh, D. E. (2017) · Quantum Information and Computation · doi:10.26421/qic17.3-4-5 · Cited by 31
Accelerating quantum computer developments
Alberts, G., Rol, M. A., Last, T., Broer, B. W., Bultink, C. C., Rijlaarsdam, M. S. C., & Hauwermeiren, A. E. V. (2021) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-021-00107-w · Cited by 30
A review of Quantum Neural Networks: Methods, Models, Dilemma
Zhao, R., & Wang, S. (2021) · arXiv · doi:10.48550/arxiv.2109.01840 · Cited by 26
Hybrid quantum–classical optimization with cardinality constraints and applications to finance
Fernández-Lorenzo, S., Porras, D., & García‐Ripoll, J. J. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/abf9af · Cited by 28
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
Approaches to Constrained Quantum Approximate Optimization
Saleem, Z. H., Tomesh, T., Tariq, B., & Suchara, M. (2023) · SN Computer Science · doi:10.1007/s42979-022-01638-4 · Cited by 25
Miller, J., Sanders, S. K., & Miyake, A. (2017) · Physical Review A · doi:10.1103/physreva.96.062320 · Cited by 29
Meng, F., Li, Z., Yu, X., & Zhang, Z. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3119010 · Cited by 27
Implementing Graph-Theoretic Feature Selection by Quantum Approximate Optimization Algorithm
Li, Y., Zhou, R., Xu, R., Luo, J., Hu, W., & Fan, P. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3190042 · Cited by 28
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 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
Performance Evaluation and Acceleration of the QTensor Quantum Circuit Simulator on GPUs
Lykov, D., Chen, A., Chen, H., Keipert, K., Zhang, Z., Gibbs, T., & Alexeev, Y. (2021) · IEEE/ACM International Workshop on Quantum Computing Software (QCS) · doi:10.1109/qcs54837.2021.00007 · Cited by 23
Optimizing QAOA: Success Probability and Runtime Dependence on Circuit DepthPreprint
Niu, M. Y., Lu, S., & Chuang, I. L. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.12134 · Cited by 45
Complexity Classification of Conjugated Clifford CircuitsPreprint
Bouland, A., Fitzsimons, J. F., & Koh, D. E. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.ccc.2018.21 · Cited by 43
Quantum Machine Learning: Unraveling a New Paradigm in Computational IntelligencePreprint
Khurana, S., & Nene, M. J. (2024) · doi:10.22541/au.171037552.27623320/v1 · Cited by 22
Quantum computing critical exponents
Dreyer, H., Bejan, M., & Granet, E. (2021) · Physical Review A · doi:10.1103/physreva.104.062614 · Cited by 22
Optimizing the Number of Gates in Quantum Search
Arunachalam, S., & de Wolf, R. (2017) · Quantum Information and Computation · doi:10.26421/qic17.3-4 · Cited by 21
Energy-Efficient Cluster Head Selection via Quantum Approximate Optimization
Choi, J., Oh, S., & Kim, J. (2020) · Electronics · doi:10.3390/electronics9101669 · Cited by 20
Unsupervised Quantum Gate Control for Gate-Model Quantum Computers
Gyöngyösi, L. (2020) · Scientific Reports · doi:10.1038/s41598-020-67018-1 · Cited by 19
Generic detection-based error mitigation using quantum autoencoders
Zhang, X., Kong, W., Farooq, M. U., Yung, M., Guo, G., & Wang, X. (2021) · Physical Review A · doi:10.1103/physreva.103.l040403 · Cited by 24
Proietti, M., Cerocchi, F., & Dispenza, M. (2022) · Physical Review A · doi:10.1103/physreva.106.022437 · Cited by 23
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
Quantum Transfer Learning for Wi-Fi Sensing
Koike–Akino, T., Wang, P. P., & Wang, Y. (2022) · International Conference on Communications · doi:10.1109/icc45855.2022.9839011 · Cited by 21
AutoQML: Automated Quantum Machine Learning for Wi-Fi Integrated Sensing and Communications
Koike–Akino, T., Wang, P. P., & Wang, Y. (2022) · IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM) · doi:10.1109/sam53842.2022.9827846 · Cited by 19
Experimental demonstration of quantum advantage for NP verification with limited information
Centrone, F., Kumar, N., Diamanti, E., & Kerenidis, I. (2021) · Nature Communications · doi:10.1038/s41467-021-21119-1 · Cited by 21
Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs
Barak, B., & Marwaha, K. (2022) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.itcs.2022.14 · Cited by 19
Quantum Computing for High-Energy Physics: State of the Art and ChallengesPreprint
Meglio, A. D., Jansen, K., Tavernelli, I., Alexandrou, C., Arunachalam, S., Bauer, C., Borras, K., Carrazza, S., Crippa, A., Croft, V. A., et al. (2023) · arXiv (Cornell University) · doi:10.3204/pubdb-2023-04595 · Cited by 24
Classical algorithms and quantum limitations for maximum cut on high-girth graphs
Barak, B., & Marwaha, K. (2021) · arXiv · doi:10.48550/arxiv.2106.05900 · Cited by 19
The Future of Drug Development with Quantum Computing
Bonde, B. K., Patil, P., & Choubey, B. (2023) · Methods in molecular biology · doi:10.1007/978-1-0716-3449-3_7 · Cited by 21
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
Douce, T., Markham, D., Kashefi, E., van Loock, P., & Ferrini, G. (2019) · Physical Review A · doi:10.1103/physreva.99.012344 · Cited by 18
Error mitigation on a near-term quantum photonic device
Su, D., Israel, R., Sharma, K., Qi, H., Dhand, I., & Brádler, K. (2021) · Quantum · doi:10.22331/q-2021-05-04-452 · Cited by 19
Bouchmal, O., Cimoli, B., Stabile, R., Olmos, J. J. V., & Monroy, I. T. (2025) · Computer Networks · doi:10.1016/j.comnet.2025.111345 · Cited by 17
Importance of Diagonal Gates in Tensor Network Simulations
Lykov, D., & Alexeev, Y. (2021) · IEEE Computer Society Annual Symposium on VLSI · doi:10.1109/isvlsi51109.2021.00088 · Cited by 17
Multiple Query Optimization Using a Gate-Based Quantum Computer
Fankhauser, T., Solèr, M. E., Füchslin, R. M., & Stockinger, K. (2023) · IEEE Access · doi:10.1109/access.2023.3324253 · Cited by 43
Realization of arbitrary doubly-controlled quantum phase gatesPreprint
Hill, A. D., Hodson, M. J., Didier, N., & Reagor, M. J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.01652 · Cited by 17
Assessing the potential of quantum computing in agriculture
Pook, T., Vandenplas, J., Boschero, J. C., Aguilera, E., Leijnse, K., Chauhan, A., Bouzembrak, Y., Knapen, R., & Aldridge, M. N. (2025) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2025.110332 · Cited by 18
Simulating quantum circuit expectation values by Clifford perturbation theory
Begušić, T., Hejazi, K., & Chan, G. K. (2025) · The Journal of Chemical Physics · doi:10.1063/5.0269149 · Cited by 50
Review of ansatz designing techniques for variational quantum algorithms
Qin, J. (2023) · Journal of Physics Conference Series · doi:10.1088/1742-6596/2634/1/012043 · Cited by 20
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
Wulff, A., Chen, B., Steinberg, M., Tang, Y., Möller, M., & Feld, S. (2024) · Computer Methods in Applied Mechanics and Engineering · doi:10.1016/j.cma.2024.117380 · Cited by 19
Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
Zhu, Y., Zhang, Z., Sundar, B., Green, A., Alderete, C. H., Nguyen, N. H., Hazzard, K. R. A., & Linke, N. M. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac91ef · Cited by 21
Average-Case Quantum Advantage with Shallow CircuitsPreprint
Gall, F. L. (2018) · arXiv (Cornell University) · doi:10.4230/lipics.ccc.2019.21 · Cited by 25
Quantum gradient descent and Newton’s method for constrained polynomial optimization
Rebentrost, P., Schuld, M., Wossnig, L., Petruccione, F., & Lloyd, S. (2019) · New Journal of Physics · doi:10.1088/1367-2630/ab2a9e · Cited by 152
High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
Pelofske, E., Bärtschi, A., Golden, J., & Eidenbenz, S. (2023) · 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00064 · Cited by 15
Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
Bakó, B., Glos, A., Salehi, Ö., & Zimborás, Z. (2025) · Quantum · doi:10.22331/q-2025-03-20-1663 · Cited by 32
Quantum Information and Computation for Chemistry
Olson, J., Cao, Y., Romero, J., Johnson, P., Dallaire-Demers, P.-L., Sawaya, N., Narang, P., Kivlichan, I., Wasielewski, M., & Aspuru-Guzik, A. (2017) · arXiv · doi:10.48550/arxiv.1706.05413 · Cited by 15
Gülbahar, B. (2024) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2024.3383101 · Cited by 14
Quantum Approximate Optimization Algorithm for Test Case Optimization
Wang, X., Ali, S., Yue, T., & Arcaini, P. (2024) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2024.3479421 · Cited by 22
Hybrid quantum variational algorithm for simulating open quantum systems with near-term devices
Mahdian, M., & Yeganeh, H. D. (2020) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/abad76 · Cited by 14
Minimal constraints in the parity formulation of optimization problems
Lanthaler, M., & Lechner, W. (2021) · New Journal of Physics · doi:10.1088/1367-2630/ac1897 · Cited by 14
Hamiltonian Sparsification and Gap-SimulationPreprint
Aharonov, D., & Zhou, L. (2018) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2019.2 · Cited by 21
Classical symmetries and QAOAPreprint
Shaydulin, R., Hadfield, S., Hogg, T., & Safro, I. (2020) · arXiv (Cornell University) · Cited by 14
Quantum Computing for Healthcare: A ReviewPreprint
Qayyum, A., Rasool, R. U., Ahmad, H. F., Rafique, W., Qadir, J., & Anwar, Z. (2021) · doi:10.36227/techrxiv.17198702.v2 · Cited by 15
Kundu, S., Gupta, T., Sardar, A., Bandyopadhyay, A., Swain, S., & Mallik, S. (2025) · Franklin Open · doi:10.1016/j.fraope.2025.100371 · Cited by 21
Characterization of QUBO reformulations for the maximum k-colorable subgraph problem
Quintero, R. A., Bernal, D. E., Tamás Terlaky, B., & Zuluaga, L. F. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03421-z · Cited by 13
Effects of cosine tapering window on quantum phase estimation
Rendon, G., Izubuchi, T., & Kikuchi, Y. (2022) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.106.034503 · Cited by 14
Normalized Gradient Descent for Variational Quantum Algorithms
Suzuki, Y., Yano, H., Raymond, R., & Yamamoto, N. (2021) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00015 · Cited by 13
What do QAOA energies reveal about graphs?Preprint
Szegedy, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.12277 · Cited by 23
quEEGNet: Quantum AI for Biosignal Processing
Koike–Akino, T., & Wang, Y. (2022) · IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI ...) · doi:10.1109/bhi56158.2022.9926814 · Cited by 12
Rehman, J. U., Al-Hraishawi, H., & Chatzinotas, S. (2023) · International Conference on Communications · doi:10.1109/icc45041.2023.10279239 · Cited by 12
Metadata
- Authors
- Farhi, E., & Harrow, A. W.
- Affiliations
- Google (United States) (US)
- Massachusetts Institute of Technology (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2016
- Volume
- 2017
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1602.07674
- OpenAlex
- W2297565774
- Cited by
- 331
- References
- 34
- Citations by year
- 2026: 1 · 2025: 21 · 2024: 32 · 2023: 47 · 2022: 46 · 2021: 68 · 2020: 40 · 2019: 33 · 2018: 24 · 2017: 18 · 2016: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Bulletin of the American Physical Society
- Funders
- National Science Foundation (1452616, 1111382, 1218176)
- Intelligence Advanced Research Projects Activity (D15PC00242)
- Army Research Office (W911NF-12-1-0486, W911NF)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum advantage, quantum approximate optimization algorithm, adiabatic quantum computation, stoquastic Hamiltonians, gapped Hamiltonians, polynomial hierarchy collapse, 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
