A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Open accessAbstract
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
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?
Numerical experiments can evaluate the adiabatic algorithm's performance on small instances, but this rapidly becomes infeasible for larger problems.
“Although numerical experiments can be carried out to evaluate its performance on small instances, 31 this rapidly becomes infeasible for larger problems.”
From Quantum algorithms: an overview (2016) · cites this paper as [31]
The original AQC approach makes superadiabatic implementations seem prohibitive because the whole set of eigenlevels of a many-body Hamiltonian is required.
“For instance, by adopting the original AQC approach14, superadiabatic implementations seem prohibitive, since the whole set of eigenlevels of a many-body Hamiltonian is required.”
From Superadiabatic Controlled Evolutions and Universal Quantum Computation (2015) · cites this paper as [14]
It is believed that adiabatic quantum computing, and quantum computing in general, is unable to efficiently solve the class of NP-complete problems, or at least no such feat has withstood scrutiny.
“It is believed that adiabatic quantum computing (and quantum computing, in general) is unable to efficiently solve the class of NP-complete problems, or at least no such feat has withstood scrutiny [17,186].”
From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [186]
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
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472 · see citing works
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · 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
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · see citing works
Sharp thresholds of graph properties, and the $k$-sat problem
Friedgut, E., & Bourgain, A. B. J. (1999) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-99-00305-7 · Cited by 696 · see citing works
Critical Behavior in the Satisfiability of Random Boolean Expressions
Kirkpatrick, S., & Selman, B. (1994) · Science · doi:10.1126/science.264.5163.1297 · Cited by 582 · see citing works
Quantum 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-citationQuantum Annealing of a Disordered Magnet
Brooke, J., Bitko, D., F., T., Rosenbaum, & Aeppli, G. (1999) · Science · doi:10.1126/science.284.5415.779 · Cited by 518 · see citing works
Analog analogue of a digital quantum computation
Farhi, E., & Gutmann, S. (1998) · Physical Review A · doi:10.1103/physreva.57.2403 · Cited by 389 · see citing works
Self-citationFinding cliques by quantum adiabatic evolution
Childs, A. M., Farhi, E., Goldstone, J., & Gutmann, S. (2002) · Quantum Information and Computation · doi:10.26421/qic2.3-1 · Cited by 81 · see citing works
Self-citationA Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for SatisfiabilityPreprint
Farhi, E., Goldstone, J., & Gutmann, S. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0007071 · Cited by 50 · see citing works
Self-citationSalomaa, A. K. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9781107325630.008 · Cited by 27 · see citing works
Flagged first, then by citations
Research works printed but not linked: 3
- [1][1] P.W. Shor, SIAM J. Comput. 26 (5), 1484 (1997). -
- [7][7] D.G. Mitchell, B. Selman, and H.J. Levesque, in Proc. 10th Natl. Conf. Artif. Intell. (AAAI-92), 459 (1992). -
- [10][10] B. Selman, H.J. Levesque, and D.G. Mitchell, in Proc. 10th Natl. Conf. Artif. Intell. (AAAI-92), 440 (1992). -
Cited by
Sorted by citations
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325 · see citing works
Georgescu, I. M., Ashhab, S., & Nori, F. (2014) · Reviews of Modern Physics · doi:10.1103/revmodphys.86.153 · Cited by 2,932 · see citing works
“…progress in quantum simulation will also have a positive impact on the development of other fields such as adiabatic quantum computation (Farhi et al., 2001), measurement-based quantum computation (Raussendorf et al., 2003), topological quantum computation (Kitaev, 2003) and the theory…”
BackgroundIsing formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512 · see citing works
The theory of variational hybrid quantum-classical algorithms
McClean, J. R., Romero, J., Babbush, R., & Aspuru-Guzik, A. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/2/023023 · Cited by 2,227 · 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
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
Simulated Quantum Computation of Molecular Energies
Aspuru-Guzik, A., Dutoi, A. D., Love, P. J., & Head-Gordon, M. (2005) · Science · doi:10.1126/science.1113479 · Cited by 1,418 · see citing works
Suppressing quantum errors by scaling a surface code logical qubit
Google Quantum, A. I., Acharya, R., Aleiner, I., Allen, R., Andersen, T. I., Ansmann, M., Arute, F., Arya, K., Asfaw, A., Atalaya, J., et al. (2023) · Nature · doi:10.1038/s41586-022-05434-1 · Cited by 1,103 · see citing works
Self-citationMeasurement-based quantum computation
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009) · Nature Physics · doi:10.1038/nphys1157 · Cited by 1,090 · see citing works
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071 · see citing works
“Although numerical experiments can be carried out to evaluate its performance on small instances [38], this rapidly becomes infeasible for larger problems.”
Evidence 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
Quantum Algorithms for Quantum Chemistry and Quantum Materials Science
Bauer, B., Bravyi, S., Motta, M., & Chan, G. K.-L. (2020) · Chemical Reviews · doi:10.1021/acs.chemrev.9b00829 · Cited by 848 · see citing works
Programmable 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
Towards quantum chemistry on a quantum computer
Lanyon, B. P., Whitfield, J. D., Gillett, G. G., Goggin, M. E., Almeida, M. P., Kassal, I., Biamonte, J. D., Mohseni, M., Powell, B. J., Barbieri, M., et al. (2010) · Nature Chemistry · doi:10.1038/nchem.483 · Cited by 796 · see citing works
Power of data in quantum machine learning
Huang, H.-Y., Broughton, M., Mohseni, M., Babbush, R., Boixo, S., Neven, H., & McClean, J. R. (2021) · Nature Communications · doi:10.1038/s41467-021-22539-9 · Cited by 896 · see citing works
Quantum error correction below the surface code threshold
Collaborators, G. Q. A. A., Acharya, R., Abanin, D. A., Aghababaie-Beni, L., Aleiner, I., Andersen, T. I., Ansmann, M., Arute, F., Arya, K., Asfaw, A., et al. (2025) · Nature · doi:10.1038/s41586-024-08449-y · Cited by 778 · see citing works
“4% in this case) generated by Stim [7], and neural network [8]).”
InfluentialSelf-citationTheory of Quantum Annealing of an Ising Spin Glass
Santoro, G. E., Martoňák, R., Tosatti, E., & Car, R. (2002) · Science · doi:10.1126/science.1068774 · Cited by 734 · see citing works
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913 · see citing works
<i>Colloquium</i> : Quantum annealing and analog quantum computation
Das, A., & Chakrabarti, B. K. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1061 · Cited by 700 · 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
Quantum search by local adiabatic evolution
Roland, J., & Cerf, N. J. (2002) · Physical Review A · doi:10.1103/physreva.65.042308 · Cited by 629 · see citing works
Dynamics of Loschmidt echoes and fidelity decay
Gorin, T., Prosen, T., Seligman, T. H., & Žnidarič, M. (2006) · Physics Reports · doi:10.1016/j.physrep.2006.09.003 · Cited by 623 · 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 · see citing works
Criticality, the Area Law, and the Computational Power of Projected Entangled Pair States
Verstraete, F., Wolf, M. M., Perez-Garcia, D., & Cirac, J. I. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.220601 · Cited by 580 · see citing works
Optimal Control at the Quantum Speed Limit
Caneva, T., Murphy, M., Calarco, T., Fazio, R., Montangero, S., Giovannetti, V., & Santoro, G. E. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.240501 · Cited by 509 · see citing works
Perspectives of quantum annealing: methods and implementations
Hauke, P., Katzgraber, H. G., Lechner, W., Nishimori, H., & Oliver, W. D. (2020) · Reports on Progress in Physics · doi:10.1088/1361-6633/ab85b8 · Cited by 507 · see citing works
Simulation of electronic structure Hamiltonians using quantum computers
Whitfield, J. D., Biamonte, J., & Aspuru-Guzik, A. (2011) · Molecular Physics · doi:10.1080/00268976.2011.552441 · Cited by 472 · see citing works
Bason, M. G., Viteau, M., Malossi, N., Huillery, P., Arimondo, E., Ciampini, D., Fazio, R., Giovannetti, V., Mannella, R., & Morsch, O. (2012) · Nature Physics · doi:10.1038/nphys2170 · Cited by 462 · see citing works
Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
Harrigan, M. P., Sung, K. J., Neeley, M., Satzinger, K. J., Arute, F., Arya, K., Atalaya, J., Bardin, J. C., Barends, R., Boixo, S., et al. (2021) · Nature Physics · doi:10.1038/s41567-020-01105-y · Cited by 564 · 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
Quantum optimization of maximum independent set using Rydberg atom arrays
Ebadi, S., Keesling, A., Cain, M., Wang, T. T., Levine, H., Bluvstein, D., Semeghini, G., Omran, A., Liu, J.-G., Samajdar, R., et al. (2022) · Science · doi:10.1126/science.abo6587 · Cited by 430 · see citing works
Self-citationOnset of a quantum phase transition with a trapped ion quantum simulator
Islam, R., Edwards, E. E., Kim, K., Korenblit, S., Noh, C., Carmichael, H., Lin, G.-D., Duan, L.-M., Joseph Wang, C.-C., Freericks, J. K., et al. (2011) · Nature Communications · doi:10.1038/ncomms1374 · Cited by 411 · 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
Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2008) · SIAM Review · doi:10.1137/080734479 · Cited by 395 · see citing works
“[14, 15] suggested an ingenious paradigm for quantum algorithms calledadiabatic computation , which attracted considerable attention [14–21] since it w as shown to exhibit promising algorithmic capabilities [16–18], as well as inherent robustness against decoherence and control errors [20].”
BackgroundEncoding Electronic Spectra in Quantum Circuits with Linear T Complexity
Babbush, R., Gidney, C., Berry, D. W., Wiebe, N., McClean, J., Paler, A., Fowler, A., & Neven, H. (2018) · Physical Review X · doi:10.1103/physrevx.8.041015 · Cited by 383 · see citing works
Finding low-energy conformations of lattice protein models by quantum annealing
Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G., & Aspuru-Guzik, A. (2012) · Scientific Reports · doi:10.1038/srep00571 · Cited by 366 · see citing works
Optimization using quantum mechanics: quantum annealing through adiabatic evolution
Santoro, G. E., & Tosatti, E. (2006) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/39/36/r01 · Cited by 354 · see citing works
Harnessing Disordered-Ensemble Quantum Dynamics for Machine Learning
Fujii, K., & Nakajima, K. (2017) · Physical Review Applied · doi:10.1103/physrevapplied.8.024030 · Cited by 337 · see citing works
Adiabatic quantum state generation and statistical zero knowledge
Aharonov, D., & Ta-Shma, A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780546 · Cited by 322 · see citing works
Temme, K., Osborne, T. J., Vollbrecht, K. G., Poulin, D., & Verstraete, F. (2011) · Nature · doi:10.1038/nature09770 · Cited by 305 · see citing works
Solving strongly correlated electron models on a quantum computer
Wecker, D., Hastings, M. B., Wiebe, N., Clark, B. K., Nayak, C., & Troyer, M. (2015) · Physical Review A · doi:10.1103/physreva.92.062318 · Cited by 285 · see citing works
A quantum annealing architecture with all-to-all connectivity from local interactions
Lechner, W., Hauke, P., & Zoller, P. (2015) · Science Advances · doi:10.1126/sciadv.1500838 · Cited by 256 · see citing works
Benedetti, M., Realpe-Gómez, J., Biswas, R., & Perdomo-Ortiz, A. (2016) · Physical Review A · doi:10.1103/physreva.94.022308 · Cited by 215 · see citing works
The prospects of quantum computing in computational molecular biology
Outeiral, C., Strahm, M., Shi, J., Morris, G. M., Benjamin, S. C., & Deane, C. M. (2021) · WIREs Computational Molecular Science · doi:10.1002/wcms.1481 · Cited by 232 · see citing works
Adiabatic approximation in open quantum systems
Sarandy, M. S., & Lidar, D. A. (2005) · Physical Review A · doi:10.1103/physreva.71.012331 · Cited by 198 · see citing works
Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing
Albash, T., & Lidar, D. A. (2018) · Physical Review X · doi:10.1103/physrevx.8.031016 · Cited by 238 · see citing works
“Unlike universal quantum computers that operate using quantum gates and the principles of the circuit model [14], these devices specialize primarily in solving combinatorial optimization problems, and are designed to represent physical implementations of quantum annealing (QA) [15] and the quantum adiabatic algorithm…”
BackgroundAdiabatic Quantum Simulation of Quantum Chemistry
Babbush, R., Love, P. J., & Aspuru-Guzik, A. (2014) · Scientific Reports · doi:10.1038/srep06603 · Cited by 191 · see citing works
Quantum Speedup by Quantum Annealing
Somma, R. D., Nagaj, D., & Kieferová, M. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.050501 · Cited by 176 · see citing works
How powerful is adiabatic quantum computation?
van Dam, W., Mosca, M., & Vazirani, U. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959902 · Cited by 175 · see citing works
Li, R. Y., Di Felice, R., Rohs, R., & Lidar, D. A. (2018) · npj Quantum Information · doi:10.1038/s41534-018-0060-8 · Cited by 202 · see citing works
Application of Quantum Annealing to Nurse Scheduling Problem
Ikeda, K., Nakamura, Y., & Humble, T. S. (2019) · Scientific Reports · doi:10.1038/s41598-019-49172-3 · Cited by 139 · 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
Alicki, R., Lidar, D. A., & Zanardi, P. (2006) · Physical Review A · doi:10.1103/physreva.73.052311 · Cited by 132 · see citing works
Superadiabatic Controlled Evolutions and Universal Quantum Computation
Santos, A. C., & Sarandy, M. S. (2015) · Scientific Reports · doi:10.1038/srep15775 · Cited by 125 · see citing works
Perdomo, A., Truncik, C., Tubert-Brohman, I., Rose, G., & Aspuru-Guzik, A. (2008) · Physical Review A · doi:10.1103/physreva.78.012320 · Cited by 120 · see citing works
Efficient quantum circuits for diagonal unitaries without ancillas
Welch, J., Greenbaum, D., Mostame, S., & Aspuru-Guzik, A. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/3/033040 · Cited by 114 · see citing works
Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
Willsch, D., Willsch, M., Gonzalez Calaza, C. D., Jin, F., De Raedt, H., Svensson, M., & Michielsen, K. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03476-y · Cited by 114 · see citing works
The quantum adiabatic optimization algorithm and local minima
Reichardt, B. W. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007428 · Cited by 110 · see citing works
A study of heuristic guesses for adiabatic quantum computation
Perdomo-Ortiz, A., Venegas-Andraca, S. E., & Aspuru-Guzik, A. (2011) · Quantum Information Processing · doi:10.1007/s11128-010-0168-z · Cited by 111 · see citing works
PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form
Zaman, M., Tanahashi, K., & Tanaka, S. (2022) · IEEE Transactions on Computers · doi:10.1109/tc.2021.3063618 · Cited by 114 · see citing works
Adiabatic Quantum Algorithm for Search Engine Ranking
Garnerone, S., Zanardi, P., & Lidar, D. A. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.230506 · Cited by 102 · see citing works
Adiabatic quantum programming: minor embedding with hard faults
Klymko, C., Sullivan, B. D., & Humble, T. S. (2014) · Quantum Information Processing · doi:10.1007/s11128-013-0683-9 · Cited by 99 · see citing works
“In order to meet these conditions, T must scale inversely with the minimum spectral gap of H(t) [16].”
BackgroundMethodInfluentialQuantum Annealing for Constrained Optimization
Hen, I., & Spedalieri, F. M. (2016) · Physical Review Applied · doi:10.1103/physrevapplied.5.034007 · Cited by 114 · see citing works
General conditions for quantum adiabatic evolution
Comparat, D. (2009) · Physical Review A · doi:10.1103/physreva.80.012106 · Cited by 95 · see citing works
Wecker, D., Hastings, M. B., & Troyer, M. (2016) · Physical Review A · doi:10.1103/physreva.94.022309 · Cited by 88 · see citing works
Quantum Approach to Classical Statistical Mechanics
Somma, R. D., Batista, C. D., & Ortiz, G. (2007) · Physical Review Letters · doi:10.1103/physrevlett.99.030603 · Cited by 87 · see citing works
Fundamentals of universality in one-way quantum computation
Nest, M. V. D., Dür, W., Miyake, A., & Briegel, H. J. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/204 · Cited by 97 · see citing works
A deceptive step towards quantum speedup detection
Mandrà, S., & Katzgraber, H. G. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aac8b2 · Cited by 82 · see citing works
Classical signature of quantum annealing
Smolin, J. A., & Smith, G. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00052 · Cited by 79 · see citing works
Speeding up critical system dynamics through optimized evolution
Caneva, T., Calarco, T., Fazio, R., Santoro, G. E., & Montangero, S. (2011) · Physical Review A · doi:10.1103/physreva.84.012312 · Cited by 78 · see citing works
Benchmarking a quantum annealing processor with the time-to-target metric
King, J., Yarkoni, S., Nevisi, M. M., Hilton, J. P., & McGeoch, C. C. (2015) · arXiv · doi:10.48550/arxiv.1508.05087 · Cited by 77 · see citing works
Mandrà, S., Zhu, Z., & Katzgraber, H. G. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.070502 · Cited by 72 · see citing works
Reinforcement-learning-assisted quantum optimization
Wauters, M. M., Panizon, E., Mbeng, G. B., & Santoro, G. E. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033446 · Cited by 80 · see citing works
Nested quantum annealing correction
Vinci, W., Albash, T., & Lidar, D. A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2016.17 · Cited by 57 · see citing works
Adiabatic approximation for weakly open systems
Thunström, P., Åberg, J., & Sjöqvist, E. (2005) · Physical Review A · doi:10.1103/physreva.72.022328 · Cited by 49 · see citing works
Babbush, R., Perdomo‐Ortiz, A., O'Gorman, B., Macready, W., & Aspuru‐Guzik, A. (2014) · Advances in Chemical Physics · doi:10.1002/9781118755815.ch05 · Cited by 45 · see citing works
Quinton, F. A., Myhr, P. A. S., Barani, M., Crespo del Granado, P., & Zhang, H. (2025) · Scientific Reports · doi:10.1038/s41598-025-96220-2 · Cited by 46 · see citing works
Quantum Approximation for Wireless Scheduling
Choi, J., Oh, S., & Kim, J. (2020) · Applied Sciences · doi:10.3390/app10207116 · Cited by 44 · see citing works
On the emerging potential of quantum annealing hardware for combinatorial optimization
Tasseff, B., Albash, T., Morrell, Z., Vuffray, M., Lokhov, A. Y., Misra, S., & Coffrin, C. (2024) · Journal of Heuristics · doi:10.1007/s10732-024-09530-5 · Cited by 42 · see citing works
Modelling chemical reactions using semiconductor quantum dots
Smirnov, A. Y., Savel'ev, S., Mourokh, L. G., & Nori, F. (2007) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/80/67008 · Cited by 40 · see citing works
Hybrid Quantum Annealing for Larger-than-QPU Lattice-structured Problems
Raymond, J., Stevanovic, R., Bernoudy, W., Boothby, K., McGeoch, C. C., Berkley, A. J., Farré, P., Pasvolsky, J., & King, A. D. (2023) · ACM Transactions on Quantum Computing · doi:10.1145/3579368 · Cited by 39 · see citing works
Quantum adiabatic algorithm design using reinforcement learning
Lin, J., Lai, Z. Y., & Li, X. (2020) · Physical Review A · doi:10.1103/physreva.101.052327 · Cited by 39 · see citing works
Two-parameter counter-diabatic driving in quantum annealing
Prielinger, L., Hartmann, A., Yamashiro, Y., Nishimura, K., Lechner, W., & Nishimori, H. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.013227 · Cited by 39 · see citing works
Quantum gates with controlled adiabatic evolutions
Hen, I. (2015) · Physical Review A · doi:10.1103/physreva.91.022309 · Cited by 37 · see citing works
Relativistic quantum chemistry on quantum computers
Veis, L., Višňák, J., Fleig, T., Knecht, S., Saue, T., Visscher, L., & Pittner, J. (2012) · Physical Review A · doi:10.1103/physreva.85.030304 · Cited by 36 · see citing works
Adiabatic optimization versus diffusion Monte Carlo methods
Jarret, M., Jordan, S. P., & Lackey, B. (2016) · Physical Review A · doi:10.1103/physreva.94.042318 · Cited by 36 · see citing works
Energetic Cost of Superadiabatic Quantum Computation
Coulamy, I. B., Santos, A. C., Hen, I., & Sarandy, M. S. (2016) · Frontiers in ICT · doi:10.3389/fict.2016.00019 · Cited by 38 · see citing works
Hybrid quantum annealing via molecular dynamics
Irie, H., Liang, H., Doi, T., Gongyo, S., & Hatsuda, T. (2021) · Scientific Reports · doi:10.1038/s41598-021-87676-z · Cited by 32 · see citing works
Kim, S., Jung, S., Bobbitt, A., Lee, E., & Luo, T. (2024) · Cell Reports Physical Science · doi:10.1016/j.xcrp.2024.101847 · Cited by 28 · see citing works
Combinatorial Optimization on Gate Model Quantum Computers: A Survey
Zahedinejad, E., & Zaribafiyan, A. (2017) · arXiv · doi:10.48550/arxiv.1708.05294 · Cited by 29 · see citing works
Optimal suppression of defect generation during a passage across a quantum critical point
Wu, N., Nanduri, A., & Rabitz, H. (2015) · Physical Review B · doi:10.1103/physrevb.91.041115 · Cited by 26 · see citing works
Quantum Adiabatic Computation with a Constant Gap Is Not Useful in One Dimension
Hastings, M. B. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.050502 · Cited by 22 · see citing works
Energy-Efficient Cluster Head Selection via Quantum Approximate Optimization
Choi, J., Oh, S., & Kim, J. (2020) · Electronics · doi:10.3390/electronics9101669 · Cited by 20 · see citing works
Fair sampling of ground-state configurations of binary optimization problems
Zhu, Z., Ochoa, A. J., & Katzgraber, H. G. (2019) · Physical Review E · doi:10.1103/physreve.99.063314 · Cited by 17 · see citing works
Bass, G., Tomlin, C., Kumar, V., Rihaczek, P., & Dulny, J. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aaadc2 · Cited by 16 · see citing works
On good encodings for quantum annealer and digital optimization solvers
Ceselli, A., & Premoli, M. (2023) · Scientific Reports · doi:10.1038/s41598-023-32232-0 · Cited by 10 · see citing works
Enhancing quantum control by bootstrapping a quantum processor of 12 qubits
Lu, D., Li, K., Li, J., Katiyar, H., Park, A. J., Feng, G., Xin, T., Li, H., Long, G., Brodutch, A., et al. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0045-z · Cited by 80 · see citing works
“This procedure, benchmarked in our previous work [3], is mainly done with the aid of SSGRAPE.”
BackgroundMethodInfluentialQuantum Computing Approach to Nonrelativistic and Relativistic Molecular Energy Calculations
Veis, L., & Pittner, J. (2014) · Advances in Chemical Physics · doi:10.1002/9781118742631.ch04 · Cited by 3 · see citing works
Non-classical role of potential energy in adiabatic quantum annealing
Das, A. (2009) · Journal of Physics: Conference Series · doi:10.1088/1742-6596/143/1/012001 · Cited by 2 · see citing works
- Authors
- Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D.
- Affiliations
- Massachusetts Institute of Technology (US)
- Northeastern University (US)
- Corresponding author
- Farhi, Edward
- Venue
- Science
- Published
- 2001-04-20
- Volume
- 292
- Issue
- 5516
- Pages
- 472-475
- ISSN
- 0036-8075 (ISSN-L)
- 1095-9203
- OpenAlex
- W2105614108
- Cited by
- 2,056
- References
- 13
- Citations by year
- 2026: 88 · 2025: 149 · 2024: 140 · 2023: 132 · 2022: 123 · 2021: 141 · 2020: 138 · 2019: 116 · 2018: 103 · 2017: 94 · 2016: 89 · 2015: 88 · 2014: 84 · 2013: 58 · 2012: 76
- FWCI
- 23.00
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Science (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › DNA and Biological Computing
- Keywords
- adiabatic quantum computation, NP-complete problems, combinatorial optimization, random instances, ground state, quantum computing, computational complexity
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
