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
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
Probing many-body dynamics on a 51-atom quantum simulator
Bernien, H., Schwartz, S., Keesling, A., Levine, H., Omran, A., Pichler, H., Choi, S., Zibrov, A. S., Endres, M., Greiner, M., et al. (2017) · Nature · doi:10.1038/nature24622 · Cited by 2,460
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
Mitarai, K., Negoro, M., Kitagawa, M., & Fujii, K. (2018) · Physical Review A · doi:10.1103/physreva.98.032309 · Cited by 1,639
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560
Parameterized quantum circuits as machine learning models
Benedetti, M., Lloyd, E., Sack, S., & Fiorentini, M. (2019) · Quantum Science and Technology · doi:10.1088/2058-9565/ab4eb5 · Cited by 1,528
Characterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J., Degroote, M., Johnson, P., Kieferová, M., Kivlichan, I., Menke, T., Peropadre, B., Sawaya, N., et al. (n.d.) · OPUS - Open Publications of UTS Scholars (University of Technology Sydney) · Cited by 1,265
Quantum computational supremacy
Harrow, A. W., & Montanaro, A. (2017) · Nature · doi:10.1038/nature23458 · Cited by 702
Self-citationProgrammable Quantum Simulations of Spin Systems with Trapped Ions
Monroe, C., Campbell, W. C., Duan, L. M., Gong, Z. X., Gorshkov, A. V., Hess, P., Islam, R., Kim, K., Linke, N., Pagano, G., et al. (2019) · arXiv · doi:10.48550/arxiv.1912.07845 · Cited by 806
Programmable quantum simulations of spin systems with trapped ions
Monroe, C. R., Campbell, W. C., Duan, L.-M., Gong, Z., Gorshkov, A. V., Hess, P., Islam, R., Kim, K., Linke, N. M., Pagano, G., et al. (2021) · Reviews of Modern Physics · doi:10.1103/revmodphys.93.025001 · Cited by 891
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
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772
Quantum optimization using variational algorithms on near-term quantum devices
Moll, N., Barkoutsos, P., Bishop, L. S., Chow, J. M., Cross, A., Egger, D. J., Filipp, S., Fuhrer, A., Gambetta, J. M., Ganzhorn, M., et al. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aab822 · Cited by 744
A Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646
Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
Qiang, X., Zhou, X., Wang, J., Wilkes, C. M., Loke, T., O’Gara, S., Kling, L., Marshall, G. D., Santagati, R., Ralph, T. C., et al. (2018) · Nature Photonics · doi:10.1038/s41566-018-0236-y · Cited by 516
Quantum advantage with shallow circuits
Bravyi, S. B., Gosset, D., & König, R. (2018) · Science · doi:10.1126/science.aar3106 · Cited by 406
A generative modeling approach for benchmarking and training shallow quantum circuits
Benedetti, M., Garcia-Pintos, D., Perdomo, O., Leyton-Ortega, V., Nam, Y., & Perdomo-Ortiz, A. (2019) · npj Quantum Information · doi:10.1038/s41534-019-0157-8 · Cited by 379
Quantum approximate optimization algorithm for MaxCut: A fermionic view
Wang, Z., Hadfield, S., Jiang, Z., & Rieffel, E. G. (2018) · Physical Review A · doi:10.1103/physreva.97.022304 · Cited by 353
QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
Guerreschi, G. G., & Matsuura, A. Y. (2019) · Scientific Reports · doi:10.1038/s41598-019-43176-9 · Cited by 337
Strawberry Fields: A Software Platform for Photonic Quantum Computing
Killoran, N., Izaac, J., Quesada, N., Bergholm, V., Amy, M., & Weedbrook, C. (2019) · Quantum · doi:10.22331/q-2019-03-11-129 · Cited by 395
Expressive power of parametrized quantum circuits
Du, Y., Hsieh, M.-H., Liu, T., & Tao, D. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033125 · Cited by 318
Towards a distributed quantum computing ecosystem
Cuomo, D., Caleffi, M., & Cacciapuoti, A. S. (2020) · IET Quantum Communication · doi:10.1049/iet-qtc.2020.0002 · Cited by 329
Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms
Foxen, B., Neill, C., Dunsworth, A., Roushan, P., Chiaro, B., Megrant, A., Kelly, J., Chen, Z., Satzinger, K. J., Barends, R., et al. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.120504 · Cited by 324
Self-citationObstacles to Variational Quantum Optimization from Symmetry Protection
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.260505 · Cited by 278
Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator
Pagano, G., Bapat, A., Becker, P., Collins, K. S., De, A., Hess, P. W., Kaplan, H. B., Kyprianidis, A., Tan, W. L., Baldwin, C., et al. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2006373117 · Cited by 262
Complexity-Theoretic Foundations of Quantum Supremacy ExperimentsPreprint
Aaronson, S., & Chen, L. (2016) · arXiv (Cornell University) · doi:10.14288/1.0343134 · Cited by 400
Achieving quantum supremacy with sparse and noisy commuting quantum computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2017) · Quantum · doi:10.22331/q-2017-04-25-8 · Cited by 191
XY mixers: Analytical and numerical results for the quantum alternating operator ansatz
Wang, Z., Rubin, N. C., Dominy, J. M., & Rieffel, E. G. (2020) · Physical Review A · doi:10.1103/physreva.101.012320 · Cited by 190
Sequential minimal optimization for quantum-classical hybrid algorithms
Nakanishi, K. M., Fujii, K., & Todo, S. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.043158 · Cited by 221
Quantum sampling problems, BosonSampling and quantum supremacy
Lund, A. P., Bremner, M. J., & Ralph, T. C. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0018-2 · Cited by 202
Resource-efficient quantum algorithm for protein folding
Robert, A., Barkoutsos, P. K., Woerner, S., & Tavernelli, I. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00368-4 · Cited by 201
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
Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
Crooks, G. E. (2018) · arXiv · doi:10.48550/arxiv.1811.08419 · Cited by 158
Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
Wierichs, D., Gogolin, C., & Kastoryano, M. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.043246 · Cited by 172
The Born supremacy: quantum advantage and training of an Ising Born machine
Coyle, B., Mills, D., Danos, V., & Kashefi, E. (2020) · npj Quantum Information · doi:10.1038/s41534-020-00288-9 · Cited by 155
Formulating and Solving Routing Problems on Quantum Computers
Harwood, S., Gambella, C., Trenev, D., Simonetto, A., Bernal Neira, D., & Greenberg, D. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3049230 · Cited by 145
Quantum advantage with noisy shallow circuits
Bravyi, S., Gosset, D., König, R., & Tomamichel, M. (2020) · Nature Physics · doi:10.1038/s41567-020-0948-z · Cited by 144
Near-optimal quantum circuit for Grover's unstructured search using a transverse field
Zhang, J., Rieffel, E. G., & Wang, Z. (2017) · Physical Review A · doi:10.1103/physreva.95.062317 · Cited by 145
Using Gaussian Boson Sampling to Find Dense Subgraphs
Arrazola, J. M., & Bromley, T. R. (2018) · Physical Review Letters · doi:10.1103/physrevlett.121.030503 · Cited by 143
Efficient variational simulation of non-trivial quantum states
Ho, W. W., & Hsieh, T. H. (2019) · SciPost Physics · doi:10.21468/scipostphys.6.3.029 · Cited by 139
Compiling quantum circuits to realistic hardware architectures using temporal planners
Venturelli, D., Do, M., Rieffel, E. G., & Frank, J. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/aaa331 · Cited by 140
Variational Thermal Quantum Simulation via Thermofield Double States
Wu, J., & Hsieh, T. H. (2019) · Physical Review Letters · doi:10.1103/physrevlett.123.220502 · Cited by 163
Variational Spin-Squeezing Algorithms on Programmable Quantum Sensors
Kaubruegger, R., Silvi, P., Kokail, C., van Bijnen, R., Rey, A. M., Ye, J., Kaufman, A. M., & Zoller, P. (2019) · Physical Review Letters · doi:10.1103/physrevlett.123.260505 · Cited by 133
Variational quantum algorithm for the Poisson equation
Liu, H., Wu, Y., Wan, L., Pan, S., Qin, S., Gao, F., & Wen, Q. (2021) · Physical Review A · doi:10.1103/physreva.104.022418 · Cited by 130
Harrow, A. W., & Mehraban, S. A. (2023) · Communications in Mathematical Physics · doi:10.1007/s00220-023-04675-z · Cited by 182
Self-citationTraining the quantum approximate optimization algorithm without access to a quantum processing unit
Streif, M., & Leib, M. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8c2b · Cited by 125
Harrow, A. W., & Napp, J. C. (2021) · Physical Review Letters · doi:10.1103/physrevlett.126.140502 · Cited by 121
Self-citationFiltering variational quantum algorithms for combinatorial optimization
Amaro, D., Modica, C., Rosenkranz, M., Fiorentini, M., Benedetti, M., & Lubasch, M. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/ac3e54 · Cited by 144
(2019) · doi:10.1145/3297858.3304018 · Cited by 118
Optimal Protocols in Quantum Annealing and Quantum Approximate Optimization Algorithm Problems
Brady, L. T., Baldwin, C. L., Bapat, A., Kharkov, Y., & Gorshkov, A. V. (2021) · Physical Review Letters · doi:10.1103/physrevlett.126.070505 · Cited by 119
Optimal Protocols in Quantum Annealing and QAOA Problems
Brady, L. T., Baldwin, C. L., Bapat, A., Kharkov, Y., & Gorshkov, A. V. (2020) · arXiv · doi:10.48550/arxiv.2003.08952 · Cited by 117
Recent Advances for Quantum Neural Networks in Generative Learning
Tian, J., Sun, X., Du, Y., Zhao, S., Liu, Q., Zhang, K., Yi, W., Huang, W., Wang, C., Wu, X., et al. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2023.3272029 · Cited by 147
Benchmarking the quantum approximate optimization algorithm
Willsch, M., Willsch, D., Jin, F., Raedt, H. A. D., & Michielsen, K. F. L. (2020) · RWTH Publications (RWTH Aachen) · Cited by 109
Theory of Quantum System Certification
Kliesch, M., & Roth, I. (2021) · Refubium (Universitätsbibliothek der Freien Universität Berlin) · doi:10.17169/refubium-32392 · Cited by 112
Parameter concentrations in quantum approximate optimization
Akshay, V., Rabinovich, D., Campos, E., & Biamonte, J. (2021) · Physical Review A · doi:10.1103/physreva.104.l010401 · Cited by 103
MaxCut quantum approximate optimization algorithm performance guarantees for p>1
Wurtz, J., & Love, P. J. (2021) · Physical Review A · doi:10.1103/physreva.103.042612 · Cited by 135
Quantum optimization with a novel Gibbs objective function and ansatz architecture search
Li, L., Fan, M., Coram, M., Riley, P., & Leichenauer, S. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.023074 · Cited by 98
Quantum Algorithms for Fixed Qubit Architectures
Farhi, E., Goldstone, J., Gutmann, S., & Neven, H. (2017) · arXiv · doi:10.48550/arxiv.1703.06199 · Cited by 93
Self-citationA QUBO Model for the Traveling Salesman Problem with Time Windows
Papalitsas, C., Andronikos, T., Giannakis, K., Theocharopoulou, G., & Fanarioti, S. (2019) · Algorithms · doi:10.3390/a12110224 · Cited by 98
Architecting Noisy Intermediate-Scale Trapped Ion Quantum Computers
Murali, P., Debroy, D. M., Brown, K. R., & Martonosi, M. (2020) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca45697.2020.00051 · Cited by 96
A case study of variational quantum algorithms for a job shop scheduling problem
Amaro, D., Rosenkranz, M., Fitzpatrick, N., Hirano, K., & Fiorentini, M. (2022) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-022-00123-4 · Cited by 96
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. (2020) · Physical Review Applied · doi:10.1103/physrevapplied.14.034010 · Cited by 87
Reinforcement learning using quantum Boltzmann machines
Crawford, D., Levit, A., Ghadermarzy, N., Oberoi, J. S., & Ronagh, P. (2018) · Quantum Information and Computation · doi:10.26421/qic18.1-2-3 · Cited by 117
Circuit Compilation Methodologies for Quantum Approximate Optimization Algorithm
Alam, M., Saki, A. A., & Ghosh, S. (2020) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro50266.2020.00029 · Cited by 78
Campos, J., & Souto, A. (2021) · IEEE/ACM International Workshop on Quantum Software Engineering (Q-SE) · doi:10.1109/q-se52541.2021.00013 · Cited by 74
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
Quantum approximate optimization is computationally universalPreprint
Lloyd, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.11075 · Cited by 68
Input Redundancy for Parameterized Quantum Circuits
Vidal, F. J. G., & Theis, D. O. (2020) · Frontiers in Physics · doi:10.3389/fphy.2020.00297 · Cited by 88
Storing quantum information in spins and high-sensitivity ESR
Morton, J. J. L., & Bertet, P. (2018) · Journal of Magnetic Resonance · doi:10.1016/j.jmr.2017.11.015 · Cited by 66
The Quantum software lifecycle
Weder, B., Barzen, J., Leymann, F., Salm, M., & Vietz, D. (2020) · doi:10.1145/3412451.3428497 · Cited by 69
Novel Resolution of Unit Commitment Problems Through Quantum Surrogate Lagrangian Relaxation
Feng, F., Zhang, P., Bragin, M. A., & Zhou, Y. (2022) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2022.3181221 · Cited by 65
Genome assembly using quantum and quantum-inspired annealing
Boev, A. S., Rakitko, A. S., Usmanov, S. R., Kobzeva, A. N., Popov, I. V., Ilinsky, V. V., Kiktenko, E. O., & Fedorov, A. K. (2021) · Scientific Reports · doi:10.1038/s41598-021-88321-5 · Cited by 63
"Quantum Supremacy" and the Complexity of Random Circuit SamplingPreprint
Bouland, A., Fefferman, B., Nirkhe, C., & Vazirani, U. V. (2018) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2019.15 · Cited by 126
Application of quantum approximate optimization algorithm to job shop scheduling problem
Kurowski, K., Pecyna, T., Slysz, M., Różycki, R., Waligóra, G., & Węglarz, J. (2023) · European Journal of Operational Research · doi:10.1016/j.ejor.2023.03.013 · Cited by 72
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
Ge, X., Wu, R.-B., & RABITZ, H. A. (2022) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2022.06.001 · Cited by 69
Quantum Approximate Optimization With Parallelizable Gates
Lechner, W. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3034798 · Cited by 57
“The quantum approximate optimization algorithm (QAOA) [21], [22] has been recently introduced as a heuristic digital quantum algorithm to sample approximate ground states using shallow quantum circuits.”
MethodNetwork Community Detection on Small Quantum Computers
Shaydulin, R., Ushijima‐Mwesigwa, H., Safro, I., Mniszewski, S. M., & Alexeev, Y. (2019) · Advanced Quantum Technologies · doi:10.1002/qute.201900029 · Cited by 61
Training Optimization for Gate-Model Quantum Neural Networks
Gyöngyösi, L., & Imre, S. (2019) · Scientific Reports · doi:10.1038/s41598-019-48892-w · Cited by 59
Quantum walk-based portfolio optimisation
Slate, N., Matwiejew, E., Marsh, S., & Wang, J. B. (2021) · Quantum · doi:10.22331/q-2021-07-28-513 · Cited by 61
Iterative quantum-assisted eigensolver
Bharti, K., & Haug, T. (2021) · Physical Review A · doi:10.1103/physreva.104.l050401 · Cited by 64
Portfolio Optimisation Using the D-Wave Quantum Annealer
Phillipson, F., & Bhatia, H. S. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-77980-1_4 · Cited by 54
Continuous-variable sampling from photon-added or photon-subtracted squeezed states
Chabaud, U., Douce, T., Markham, D., van Loock, P., Kashefi, E., & Ferrini, G. (2017) · Physical Review A · doi:10.1103/physreva.96.062307 · Cited by 55
Quantum Computing: An Overview Across the System StackPreprint
Resch, S., & Karpuzcu, U. R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.07240 · Cited by 94
Tensor Network Quantum Simulator With Step-Dependent Parallelization
Lykov, D., Schutski, R., Galda, A., Vinokur, V. M., & Alexeev, Y. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00081 · Cited by 52
Quantum Approximate Optimization with Hard and Soft Constraints
Hadfield, S., Wang, Z., Rieffel, E. G., O'Gorman, B., Venturelli, D., & Biswas, R. (2017) · Proceedings of the Second International Workshop on Post Moores Era Supercomputing · doi:10.1145/3149526.3149530 · Cited by 51
Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
Pelofske, E., Bärtschi, A., & Eidenbenz, S. (2023) · Lecture Notes in Computer Science · doi:10.1007/978-3-031-32041-5_13 · Cited by 47
A Survey on Available Tools and Technologies Enabling Quantum Computing
Singh, P., Dasgupta, R., Singh, A., Pandey, H., Hassija, V., Chamola, V., & Sikdar, B. (2024) · IEEE Access · doi:10.1109/access.2024.3388005 · Cited by 52
Non-stoquastic Hamiltonians in quantum annealing via geometric phases
Vinci, W., & Lidar, D. A. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0037-z · Cited by 53
qTorch: The quantum tensor contraction handler
Fried, E., Sawaya, N. P. D., Cao, Y., Kivlichan, I., Romero, J., & Aspuru‐Guzik, A. (2018) · PLoS ONE · doi:10.1371/journal.pone.0208510 · Cited by 48
Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral
Pednault, E., Gunnels, J. A., Nannicini, G., Horesh, L., Magerlein, T., Solomonik, E., Draeger, E. W., Holland, E. T., & Wisnieff, R. (2017) · arXiv · doi:10.48550/arxiv.1710.05867 · Cited by 48
Classically verifiable quantum advantage from a computational Bell test
Kahanamoku–Meyer, G. D., Choi, S., Vazirani, U. V., & Yao, N. Y. (2022) · Nature Physics · doi:10.1038/s41567-022-01643-7 · Cited by 62
Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware
Schönberger, M., Scherzinger, S., & Mauerer, W. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3588946 · Cited by 49
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
Dynamical Phase Transitions in Sampling Complexity
Deshpande, A., Fefferman, B., Tran, M. C., Foss‐Feig, M., & Gorshkov, A. V. (2018) · Physical Review Letters · doi:10.1103/physrevlett.121.030501 · Cited by 52
Accelerating Quantum Approximate Optimization Algorithm using Machine Learning
Alam, M., Saki, A. A., & Ghosh, S. (2020) · Design, Automation, and Test in Europe · doi:10.23919/date48585.2020.9116348 · Cited by 46
Moussa, C., Wang, H., Bäck, T., & Dunjko, V. (2022) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-022-00131-4 · Cited by 55
Self-correcting quantum many-body control using reinforcement learning with tensor networks
Metz, F., & Bukov, M. (2023) · Nature Machine Intelligence · doi:10.1038/s42256-023-00687-5 · Cited by 46
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
