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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Efficient sampling of the output distribution of QAOA, even for p=1, implies the collapse of the polynomial hierarchy.
“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.
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 · see citing works
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · see citing works
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,375 · see citing works
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 · see citing works
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 · see citing works
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789 · see citing works
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 · see citing works
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× · see citing works
“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 · see citing works
Self-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 · see citing works
What is the Computational Value of Finite-Range Tunneling?
Denchev, V. S., Boixo, S., Isakov, S. V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., & Neven, H. (2016) · Physical Review X · doi:10.1103/physrevx.6.031015 · Cited by 399 · see citing works
Unambiguous discrimination between linearly independent quantum states
Chefles, A. (1998) · Physics Letters A · doi:10.1016/s0375-9601(98)00064-4 · Cited by 396 · see citing works
Quantum computing, postselection, and probabilistic polynomial-time
Aaronson, S. (2005) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2005.1546 · Cited by 312 · see citing works
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308 · see citing works
Entanglement in a Quantum Annealing Processor
Lanting, T., Przybysz, A. J., Smirnov, A. Y., Spedalieri, F. M., Amin, M. H., Berkley, A. J., Harris, R., Altomare, F., Boixo, S., Bunyk, P., et al. (2014) · Physical Review X · doi:10.1103/physrevx.4.021041 · Cited by 303 · see citing works
Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.080501 · Cited by 299 · see citing works
Computational multiqubit tunnelling in programmable quantum annealers
Boixo, S., Smelyanskiy, V., Shabani, A., Isakov, S. V., Dykman, M. I., Denchev, V. S., Amin, M. H. S., Smirnov, A. Y., Mohseni, M., & Neven, H. (2016) · Nature Communications · doi:10.1038/ncomms10327 · Cited by 232 · see citing works
Thermally assisted quantum annealing of a 16-qubit problem
Dickson, N. G., Johnson, M. W., Amin, M. H. S., Harris, R., Altomare, F., Berkley, A. J., Bunyk, P., Cai, J., Chapple, E. M., Chavez, P., et al. (2013) · Nature Communications · doi:10.1038/ncomms2920 · Cited by 224 · see citing works
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., Shepherd, D. J., et al. (2010) · Cited by 216 · see citing works
A Simple Proof that Toffoli and Hadamard are Quantum UniversalPreprint
Aharonov, D. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0301040 · Cited by 162 · see citing works
The complexity of stoquastic local Hamiltonian problems
Bravyi, S. B., Divincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2008) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011772.2011773 · Cited by 141 · see citing works
A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1412.6062 · Cited by 131 · see citing works
Self-citationAdaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
Terhal, B. M., & Divincenzo, D. P. (2004) · Quantum Information and Computation · doi:10.26421/qic4.2-5 · Cited by 124 · see citing works
Farhi, E., Gosset, D., Hen, I., Sandvik, A. W., Shor, P. W., Young, A. P., & Zamponi, F. (2012) · Physical Review A · doi:10.1103/physreva.86.052334 · Cited by 114 · see citing works
Self-citationSimulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
Crosson, E., & Harrow, A. W. (2016) · CaltechAUTHORS (California Institute of Technology) · Cited by 89 · see citing works
Self-citationDetermining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
Fenner, S., Green, F., Homer, S., & Pruim, R. J. (1999) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1999.0485 · Cited by 69 · see citing works
Obstructions to classically simulating the quantum adiabatic algorithm
Hastings, M. B. (2013) · Quantum Information and Computation · doi:10.26421/qic13.11-12-8 · Cited by 55 · see citing works
Beating the random assignment on constraint satisfaction problems of bounded degree
Barak, B., Moitra, A., O’Donnell, R., Raghavendra, P., Regev, O., Steurer, D., Trevisan, L., Vijayaraghavan, A., Witmer, D. K., & Wright, J. C. (2015) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 32 · see citing works
Complexity of simulating constant-depth BosonSampling
Brod, D. J. (2015) · Physical Review A · doi:10.1103/physreva.91.042316 · Cited by 22 · see citing works
The Equivalence of Sampling and Searching
Aaronson, S. (2013) · Theory of Computing Systems · doi:10.1007/s00224-013-9527-3 · Cited by 18 · see citing works
Threshold computation and cryptographic security
Han, Y., Hemaspaandra, L. A., & Thierauf, T. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57568-5_253 · Cited by 9 · see citing works
Computational Complexity of Some Quantum Theories in $1+1$ DimensionsPreprint
Mehraban, S. A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.09243 · Cited by 4 · see citing works
Flagged first, then by citations
2 of the 34 references couldn’t be matched to a known paper.
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 · see citing works
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 · see citing works
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 1,726 · see citing works
Mitarai, K., Negoro, M., Kitagawa, M., & Fujii, K. (2018) · Physical Review A · doi:10.1103/physreva.98.032309 · Cited by 1,639 · see citing works
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546 · see citing works
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 · see citing works
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,324 · see citing works
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 · see citing works
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 · see citing works
Quantum computational supremacy
Harrow, A. W., & Montanaro, A. (2017) · Nature · doi:10.1038/nature23458 · Cited by 823 · see citing works
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 807 · see citing works
Noise-induced barren plateaus in variational quantum algorithms
Wang, S., Fontana, E., Cerezo, M., Sharma, K., Sone, A., Cincio, L., & Coles, P. J. (2021) · Nature Communications · doi:10.1038/s41467-021-27045-6 · Cited by 773 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 530 · see citing works
Quantum advantage with shallow circuits
Bravyi, S. B., Gosset, D., & König, R. (2018) · Science · doi:10.1126/science.aar3106 · Cited by 406 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 327 · see citing works
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 · see citing works
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 302 · see citing works
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 298 · see citing works
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 · see citing works
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 · see citing works
Complexity-Theoretic Foundations of Quantum Supremacy ExperimentsPreprint
Aaronson, S., & Chen, L. (2016) · arXiv (Cornell University) · doi:10.14288/1.0343134 · Cited by 268 · see citing works
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 · see citing works
Wang, Z., Rubin, N. C., Dominy, J. M., & Rieffel, E. G. (2020) · Physical Review A · doi:10.1103/physreva.101.012320 · Cited by 190 · see citing works
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 · see citing works
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 184 · see citing works
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 · see citing works
Noisy intermediate-scale quantum (NISQ) algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2021) · arXiv · doi:10.48550/arxiv.2101.08448 · Cited by 166 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 136 · see citing works
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 · see citing works
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 137 · see citing works
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 137 · see citing works
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 · see citing works
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 · see citing works
Harrow, A. W., & Mehraban, S. A. (2023) · Communications in Mathematical Physics · doi:10.1007/s00220-023-04675-z · Cited by 126 · see citing works
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 · see citing works
Harrow, A. W., & Napp, J. C. (2021) · Physical Review Letters · doi:10.1103/physrevlett.126.140502 · Cited by 121 · see citing works
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 123 · see citing works
(2019) · doi:10.1145/3297858.3304018 · Cited by 118 · see citing works
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 · see citing works
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 116 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 111 · see citing works
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 · see citing works
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 · see citing works
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 91 · see citing works
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 85 · see citing works
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 83 · see citing works
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 81 · see citing works
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 100 · see citing works
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 76 · see citing works
Campos, J., & Souto, A. (2021) · IEEE/ACM International Workshop on Quantum Software Engineering (Q-SE) · doi:10.1109/q-se52541.2021.00013 · Cited by 69 · see citing works
Fast quantum circuit cutting with randomized measurements
Lowe, A., Medvidović, M., Hayes, A., Riordan, L. J. O. A., Bromley, T. R., Arrazola, J. M., & Killoran, N. (2023) · Quantum · doi:10.22331/q-2023-03-02-934 · Cited by 68 · see citing works
Quantum approximate optimization is computationally universalPreprint
Lloyd, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.11075 · Cited by 68 · see citing works
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 71 · see citing works
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 67 · see citing works
The Quantum software lifecycle
Weder, B., Barzen, J., Leymann, F., Salm, M., & Vietz, D. (2020) · doi:10.1145/3412451.3428497 · Cited by 66 · see citing works
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 · see citing works
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 · see citing works
"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 92 · see citing works
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 64 · see citing works
Classical symmetries and the Quantum Approximate Optimization Algorithm
Shaydulin, R., Hadfield, S., Hogg, T., & Safro, I. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03298-4 · Cited by 73 · see citing works
Ge, X., Wu, R.-B., & RABITZ, H. A. (2022) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2022.06.001 · Cited by 61 · see citing works
Quantum Approximate Optimization With Parallelizable Gates
Lechner, W. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3034798 · Cited by 57 · see citing works
Network 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 57 · see citing works
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 57 · see citing works
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 57 · see citing works
Iterative quantum-assisted eigensolver
Bharti, K., & Haug, T. (2021) · Physical Review A · doi:10.1103/physreva.104.l050401 · Cited by 57 · see citing works
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 · see citing works
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 53 · see citing works
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 80 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 51 · see citing works
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 48 · see citing works
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 · see citing works
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 · see citing works
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 49 · see citing works
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 · see citing works
Short-depth QAOA circuits and quantum annealing on higher-order ising models
Pelofske, E., Bärtschi, A., & Eidenbenz, S. (2024) · npj Quantum Information · doi:10.1038/s41534-024-00825-w · Cited by 49 · see citing works
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 46 · see citing works
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 · see citing works
Moussa, C., Wang, H., Bäck, T., & Dunjko, V. (2022) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-022-00131-4 · Cited by 46 · see citing works
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 · see citing works
- 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 › Computer Science › Artificial Intelligence › 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
