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 201–300 of 346
From Ansätze to Z-Gates: A NASA View of Quantum Computing
Rieffel, E. G., Hadfield, S., Hogg, T., Mandrà, S., Marshall, J., Mossi, G., O’Gorman, B., Plamadeala, E., Tubman, N. M., Venturelli, D., et al. (2019) · Advances in parallel computing · doi:10.3233/apc190010 · Cited by 15
Tetris: A Compilation Framework for VQA Applications in Quantum Computing
Jin, Y., Li, Z., Hua, F., Hao, T., Zhou, H., Huang, Y., & Zhang, E. Z. (2024) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca59077.2024.00029 · Cited by 21
On the Need for Large Quantum Depth
Chia, N.-H., Chung, K.-M., & Lai, C. (2022) · Journal of the ACM · doi:10.1145/3570637 · Cited by 13
Objective function estimation for solving optimization problems in gate-model quantum computers
Gyöngyösi, L. (2020) · Scientific Reports · doi:10.1038/s41598-020-71007-9 · Cited by 11
Automatic depth optimization for a quantum approximate optimization algorithm
Pan, Y., Tong, Y., & Yang, Y. (2022) · Physical Review A · doi:10.1103/physreva.105.032433 · Cited by 14
A Pulse Generation Framework with Augmented Program-aware Basis Gates and Criticality Analysis
Chen, Y., Jin, Y., Hua, F., Hayes, A. B., Li, A., Shi, Y., & Zhang, E. Z. (2023) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca56546.2023.10070990 · Cited by 12
Atchade-Adelomou, P., Golobardes, E., & Vilasis-Cardona, X. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-61705-9_21 · Cited by 11
HybridQ: A Hybrid Simulator for Quantum Circuits
Mandrà, S., Marshall, J., Rieffel, E. G., & Biswas, R. (2021) · IEEE/ACM International Workshop on Quantum Computing Software (QCS) · doi:10.1109/qcs54837.2021.00015 · Cited by 14
Quantum Amplitude Estimation in the Presence of NoisePreprint
Brown, E. G., Göktaş, O., & Tham, W. K. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.14145 · Cited by 11
Application of quantum computing in discrete portfolio optimization
Shunza, J., Akinyemi, M., & Yinka-Banjo, C. (2023) · Journal of Management Science and Engineering · doi:10.1016/j.jmse.2023.02.001 · Cited by 10
Quantum Approximate Optimization Algorithm for Routing Optimization in 6G Optical Networks
Bouchmal, O., Cimoli, B., Stabile, R., Olmos, J. J. V., & Monroy, I. T. (2024) · International Conference on Optical Network Design and Modeling (ONDM) · doi:10.23919/ondm61578.2024.10582687 · Cited by 10
Gülbahar, B. (2025) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2024.3523135 · Cited by 10
Efficient Variational Quantum Linear Solver for Structured Sparse Matrices
Gnanasekaran, A., & Surana, A. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00033 · Cited by 10
Smart Rebalancing for Bike Sharing Systems using Quantum Approximate Optimization Algorithm
Harikrishnakumar, R., & Nannapaneni, S. (2021) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc48978.2021.9564714 · Cited by 10
Faster variational quantum algorithms with quantum kernel-based surrogate models
Smith, A. W. R., Paige, A. J., & Kim, M. S. (2023) · Quantum Science and Technology · doi:10.1088/2058-9565/aceb87 · Cited by 12
Application of quantum-inspired generative models to small molecular datasets
Moussa, C., Wang, H., Araya‐Polo, M., Bäck, T., & Dunjko, V. (2023) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00046 · Cited by 14
Non-Boolean quantum amplitude amplification and quantum mean estimation
Shyamsundar, P. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-04146-3 · Cited by 19
Calibration-Aware Transpilation for Variational Quantum Optimization
Ji, Y., Brandhofer, S., & Polian, I. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00040 · Cited by 15
Models of optical quantum computing
Krovi, H. (2017) · Nanophotonics · doi:10.1515/nanoph-2016-0136 · Cited by 10
Hybrid Quantum-Classical Heuristic to Solve Large-Scale Integer Linear Programs
Svensson, M., Andersson, M., Grönkvist, M., Vikstål, P., Dubhashi, D., Ferrini, G., & Johansson, G. (2023) · Physical Review Applied · doi:10.1103/physrevapplied.20.034062 · Cited by 15
Sun, Z., Wang, Y., Cui, J., & Fan, H. (2023) · New Journal of Physics · doi:10.1088/1367-2630/acb22c · Cited by 13
Singh, H., Majumder, S., & Mishra, S. (2024) · The Journal of Chemical Physics · doi:10.1063/5.0210597 · Cited by 9
Li, J., Alam, M., Saki, A. A., & Ghosh, S. (2020) · International Symposium on Quality Electronic Design (ISQED) · doi:10.1109/isqed48828.2020.9136973 · Cited by 9
Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation
Rabinovich, D., Sengupta, R., Campos, E., Akshay, V., & Biamonte, J. (2022) · Mathematics · doi:10.3390/math10152601 · Cited by 9
Wu, Q., Liu, W., Huang, Y. Y., Liu, H., Xiao, H., & Li, Z. (2024) · iScience · doi:10.1016/j.isci.2024.109394 · Cited by 8
Quantum Algorithms for the Physical Layer: Potential Applications to Physical Layer Security
Matsumine, T., Ochiai, H., & Shikata, J. (2025) · IEEE Access · doi:10.1109/access.2025.3528443 · Cited by 9
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 38
Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
Lazarev, I. D., Narożniak, M., Byrnes, T., & Pyrkov, A. N. (2025) · Physical Review A · doi:10.1103/physreva.111.012416 · Cited by 10
Coarse-grained intermolecular interactions on quantum processors
Anderson, L. W., Kiffner, M., Barkoutsos, P. K., Tavernelli, I., Crain, J. N., & Jaksch, D. (2022) · Physical Review A · doi:10.1103/physreva.105.062409 · Cited by 8
Near-term quantum algorithm for solving the MaxCut problem with fewer quantum resources
Xiumei, Z., Li, Y., Li, J., Wang, S., Wang, S., Qin, S., & Gao, F. (2024) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2024.129951 · Cited by 8
Syndrome decoding by quantum approximate optimization
Lai, C., Kuo, K.-Y., & Liao, B.-J. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04568-7 · Cited by 9
Computability and Complexity of Unconventional Computing Devices
Broersma, H. J., Stepney, S., & Wendin, G. P. (2018) · Natural computing series · doi:10.1007/978-3-319-65826-1_11 · Cited by 8
Entanglement scaling in quantum advantage benchmarks
Biamonte, J., Morales, M. E. S., & Koh, D. E. (2020) · Physical Review A · doi:10.1103/physreva.101.012349 · Cited by 11
Fisher Information: A Crucial Tool for NISQ Research
Bharti, K. (2021) · doi:10.22331/qv-2021-10-06-61 · Cited by 8
Accelerated high-fidelity Bell states generation based on dissipation dynamics and Lyapunov control
Wang, Y., Wang, Y., Zhao, X., Song, J., & Xia, Y. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03351-2 · Cited by 8
On Post-processing the Results of Quantum Optimizers
Borle, A., & McCarter, J. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-34500-6_16 · Cited by 7
Graph Cut Segmentation Methods Revisited with a Quantum AlgorithmPreprint
Tse, L., Mountney, P., Klein, P., & Simone Severini, B. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.03050 · Cited by 10
Quantum hybrid algorithm for solving SAT problem
Moudina, C. V., Fendji, J. L. E. K., Njafa, J.-P. T., & Atemkeng, M. (2023) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2023.106058 · Cited by 7
Continuous Variational Quantum Algorithms for Time Series
Guo, M., Weng, Y., Lili, Y., & Lai, Y. C. (2023) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn54540.2023.10191609 · Cited by 7
PARALLAX: A Compiler for Neutral Atom Quantum Computers under Hardware Constraints
Ludmir, J., & Patel, T. (2024) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc41406.2024.00079 · Cited by 7
Atchade-Adelomou, P., Alonso-Linaje, G., Albó-Canals, J., & Casado-Faulí, D. (2021) · Algorithms · doi:10.3390/a14070194 · Cited by 9
Matching Point Sets with Quantum Circuit Learning
Noormandipour, M., & Wang, H. (2022) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp43922.2022.9746800 · Cited by 7
Parameter-parallel distributed variational quantum algorithm
Niu, Y.-F., Zhang, S., Ding, C., Bao, W., & Huang, H.-L. (2023) · SciPost Physics · doi:10.21468/scipostphys.14.5.132 · Cited by 10
GPU-Accelerated Error-Bounded Compression Framework for Quantum Circuit Simulations
Shah, M., Yu, X., Di, S., Lykov, D., Alexeev, Y., Becchi, M., & Cappello, F. (2023) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps54959.2023.00081 · Cited by 7
Quantum Advantage with Noisy Shallow Circuits in 3D
Bravyi, S. B., Gosset, D., König, R., & Tomamichel, M. (2019) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2019.00064 · Cited by 6
Streif, M., & Leib, M. (2020) · Physical Review A · doi:10.1103/physreva.102.042416 · Cited by 8
Comparison of Superconducting NISQ Architectures
Rempfer, B., & Obenland, K. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00074 · Cited by 8
Classically efficient quantum scalable Fermi-Hubbard benchmark
Gard, B., & Meier, A. M. (2022) · Physical Review A · doi:10.1103/physreva.105.042602 · Cited by 8
An introduction to quantum computing for statisticians and data scientists
Lopatnikova, A., Tran, M., & Sisson, S. A. (2024) · Foundations of Data Science · doi:10.3934/fods.2024013 · Cited by 13
Single entanglement connection architecture between multi-layer bipartite hardware efficient ansatz
Zhang, S., Qin, Z., Yang, Z., Li, R., Du, C., & Xiao, Z. (2024) · New Journal of Physics · doi:10.1088/1367-2630/ad64fb · Cited by 9
QAOA-Assisted Benders' Decomposition for Mixed-integer Linear Programming
Zhao, Z., Fan, L., Guo, Y., Wang, Y., Han, Z., & Hanzo, L. (2024) · International Conference on Communications · doi:10.1109/icc51166.2024.10622474 · Cited by 6
Ghimire, B., Mahmood, A., & Elleithy, K. M. (2021) · International Conference on Soft Computing & Machine Intelligence (ISCMI) · doi:10.1109/iscmi53840.2021.9654824 · Cited by 6
Input Redundancy for Parameterized Quantum Circuits
Vidal, J. G., & Theis, D. O. (2019) · arXiv · doi:10.48550/arxiv.1901.11434 · Cited by 6
Larkin, J. M., Jonsson, M., Justice, D., & Guerreschi, G. G. (2020) · arXiv (Cornell University) · Cited by 6
Test of Quantumness with Small-Depth Quantum CircuitsPreprint
Hirahara, S., & Gall, F. L. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.mfcs.2021.59 · Cited by 18
Robust and Resource-Efficient Quantum Circuit ApproximationPreprint
Patel, T., Younis, E., Iancu, C., de Jong, W. A., & Tiwari, D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.12714 · Cited by 17
Leakage Reduces Device Coherence Demands for Pulse-Level Molecular Simulations
Asthana, A., Liu, C., Meitei, O. R., Economou, S. E., Barnes, E., & Mayhall, N. J. (2023) · Physical Review Applied · doi:10.1103/physrevapplied.19.064071 · Cited by 24
Hybrid Quantum Algorithms and Quantum Software Development FrameworksPreprint
Ramouthar, R., & Şeker, H. (2023) · doi:10.14293/pr2199.000298.v1 · Cited by 7
Díez-Valle, P., Porras, D., & García‐Ripoll, J. J. (2024) · Frontiers in Quantum Science and Technology · doi:10.3389/frqst.2024.1321264 · Cited by 8
DC Optimal Power Flow in Unit Commitment Using Quantum Computing: An ADMM Approach
Magar, M. R., Pandit, D., Nguyen, D., & Nguyen, N. (2024) · North American Power Symposium (NAPS) · doi:10.1109/naps61145.2024.10741684 · Cited by 5
Quantum Feasibility Labeling for NP-Complete Vertex Coloring Problem
Zhan, J. (2025) · IEEE Access · doi:10.1109/access.2025.3545262 · Cited by 9
Decoherence dynamics estimation for superconducting gate-model quantum computers
Gyöngyösi, L. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02863-7 · Cited by 6
A quantum algorithm to count weighted ground states of classical spin HamiltoniansPreprint
Sundar, B., Paredes, R., Damanik, D. T., Dueñas‐Osorio, L., & Hazzard, K. R. A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.01745 · Cited by 12
Multiple Query Optimization using a Hybrid Approach of Classical and Quantum ComputingPreprint
Fankhauser, T., Solèr, M. E., Füchslin, R. M., & Stockinger, K. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.10508 · Cited by 5
Quantum information processing with superconducting circuits: A perspective
Wendin, G. P. (2023) · Elsevier eBooks · doi:10.1016/b978-0-323-90800-9.00226-2 · Cited by 13
Patel, T., Silver, D., & Tiwari, D. (2022) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc41404.2022.00020 · Cited by 7
Exploring Models, Training Methods, and Quantum Supremacy in Machine Learning and Quantum Computing
Muthusamy, A. (2023) · Advances in computer and electrical engineering book series · doi:10.4018/978-1-6684-7535-5.ch002 · Cited by 4
Quantum mean-value approximator for hard integer-value problems
Joseph, D., Martinez, A., Ling, C., & Mintert, F. (2022) · Physical Review A · doi:10.1103/physreva.105.052419 · Cited by 4
Efficient depth selection for the implementation of noisy quantum approximate optimization algorithm
Pan, Y., Tong, Y., Xue, S., & Zhang, G. (2022) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2022.10.027 · Cited by 4
Architecture for Quantum-in-the Loop Real-Time Simulations for Designing Resilient Smart Grids
Chanda, S., Mohanpurkar, M. U., & Hovsapian, R. O. (2023) · International Symposium on Advanced Topics in Electrical Engineering · doi:10.1109/atee58038.2023.10108354 · Cited by 4
Pitfalls of the Sublinear QAOA-Based Factorization Algorithm
Grebnev, S. V., Gavreev, M. A., Kiktenko, E. O., Guglya, A. P., Efimov, A., & Fedorov, A. K. (2023) · IEEE Access · doi:10.1109/access.2023.3336989 · Cited by 11
Quantum-Assisted Clustering Algorithms for NISQ-Era DevicesPreprint
Mendelson, S. S., Strand, R. W., Oldaker, G. B., & Farinholt, J. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.08992 · Cited by 4
Quantum approximate optimization of the exact-cover problem on a superconducting quantum processorPreprint
Bengtsson, A., Vikstål, P., Warren, C., Svensson, M., Gu, X. Q., Kockum, A. F., Krantz, P., Križan, C., Shiri, D., Svensson, I.-M., et al. (2019) · arXiv (Cornell University) · Cited by 4
Quantum Optimization for Phase Unwrapping in SAR Interferometry
Glatting, K., Meyer, J., Huber, S., & Krieger, G. (2024) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2024.3519701 · Cited by 3
A repetitive amplitude encoding method for enhancing the mapping ability of quantum neural networks
Li, Z., Fu, X., Meng, L., & Du, R. (2025) · Scientific Reports · doi:10.1038/s41598-025-17651-5 · Cited by 4
Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
Esposito, A., & Danzig, T. (2024) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw63119.2024.00180 · Cited by 4
Zhang, Y., Zhao, J., Jia, Y., & Shen, X. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04776-9 · Cited by 3
QAOA in Quantum Datacenters: Parallelization, Simulation, and Orchestration
Liaqat, A., Darwish, A., Roman, A., & DiAdamo, S. (2025) · IEEE International Conference on Quantum Software (QSW) · doi:10.1109/qsw67625.2025.00031 · Cited by 3
Quantum approximate optimization algorithm in non-Markovian quantum systems
Yue, B., Xue, S., Pan, Y., & Jiang, M. (2023) · Physica Scripta · doi:10.1088/1402-4896/acf6e8 · Cited by 3
Single-qubit gate teleportation provides a quantum advantage
Caha, L., Coiteux-Roy, X., & König, R. (2024) · Quantum · doi:10.22331/q-2024-12-04-1548 · Cited by 6
Quantum annealing with chaotic driver Hamiltonians
Schlömer, H., & Subir Sachdev, A. (2025) · Annals of Physics · doi:10.1016/j.aop.2025.170042 · Cited by 6
Tabu-driven Quantum Neighborhood SamplersPreprint
Moussa, C., Wang, H., Calandra, H., Bäck, T. H. W., & Dunjko, V. (2020) · Leiden Repository (Leiden University) · Cited by 3
Svensson, M., Andersson, M., Grönkvist, M., Vikstål, P., Dubhashi, D., Ferrini, G., & Johansson, G. (2021) · arXiv (Cornell University) · Cited by 3
Quantum optimisation via maximally amplified statesPreprint
Bennett, T., & Wang, J. B. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.00796 · Cited by 3
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.v1 · Cited by 3
Kea, K., Chang, W.-D., Park, H. C., & Han, Y. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4719914 · Cited by 3
Liu, J., 周, X. 旭. Z., 周, Z. 卓. Z., & Luo, L. (2025) · Chinese Physics B · doi:10.1088/1674-1056/adf4aa · Cited by 2
Policy Gradient Approach to Compilation of Variational Quantum Circuits
Herrera-Martí, D. A. (2022) · Quantum · doi:10.22331/q-2022-09-08-797 · Cited by 5
VelociTI: An Architecture-level Performance Modeling Framework for Trapped Ion Quantum Computers
Hankin, A., Mahmoud, A., Hempstead, M., Brooks, D. M., & Wei, G.-Y. (2023) · IEEE International Symposium on Workload Characterization · doi:10.1109/iiswc59245.2023.00040 · Cited by 2
A Quantum Machine Learning Approach Using an Optimized Application of Grover's Algorithm
Cherif, M. Y., Chaari, W. L., & Driss, O. B. (2023) · IEEE Afro-Mediterranean Conference on Artificial Intelligence (AMCAI) · doi:10.1109/amcai59331.2023.10431508 · Cited by 3
Alonso, M., Martínez, R., Díez-Valle, P., Garbayo, A., García‐Santiago, X., & Gil, G. B. (2025) · IEEE Access · doi:10.1109/access.2025.3578780 · Cited by 2
Bhattacharyya, M., & Raina, A. (2026) · Quantum Information Processing · doi:10.1007/s11128-026-05074-8 · Cited by 2
Quantum approximation of normalized Schatten norms and applications to learning
Chen, Y., Miyahara, H., Bouchard, L., & Roychowdhury, V. (2022) · Physical Review A · doi:10.1103/physreva.106.052409 · Cited by 4
NISQ algorithm for the matrix elements of a generic observable
Erbanni, R., Bharti, K., Kwek, L. C., & Poletti, D. (2023) · SciPost Physics · doi:10.21468/scipostphys.15.4.180 · Cited by 2
Bayesian machine learning for Boltzmann machine in quantum-enhanced feature spacesPreprint
Wu, Y., Yu, C., Qin, S., Wen, Q., & Gao, F. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.10857 · Cited by 4
Quantum Adiabatic Theorem RevisitedPreprint
Duan, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.03063 · Cited by 2
Lower Bounds on Circuit Depth of the Quantum Approximate Optimization AlgorithmPreprint
Ostrowski, J., Herrman, R., Humble, T. S., & Siopsis, G. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.01820 · Cited by 2
Applying the Quantum Alternating Operator Ansatz to the Graph Matching ProblemPreprint
Chatterjee, S., & Bera, D. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.11918 · Cited by 2
A practical guide for building superconducting quantum devicesPreprint
Gao, Y. Y., Rol, M. A., Touzard, S., & Wang, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.06173 · Cited by 2
An introduction to variational quantum algorithms for combinatorial optimization problemsPreprint
Grange, C., Poss, M., & Bourreau, E. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2212.11734 · Cited by 2
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
