Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Abstract
The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“In principle, adiabatic quantum computing is equivalent to universal quantum computing [187].This universality holds only if the evolution is allowed to be nonstoquastic, meaning that the Hamiltonian has nonnegative off-diagonal elements at some point of the evolution.”
From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [187]
Citations
Cites
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238 · cited 1×
“It is a crucial ingredient in topological (and later, geometrical) quantum computation [18,23,27].”
BackgroundQuantum 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 · cited 1×
“In [9,30] it was shown that Grover’s quadratic speed-up for an unsorted search [16] can be realized as an adiabatic computation.”
BackgroundQuantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056 · cited 1×
“[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].”
BackgroundAn area law for one-dimensional quantum systems
Hastings, M. B. (2007) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2007/08/p08024 · Cited by 1,131
On the Adiabatic Theorem of Quantum Mechanics
Kato, T. (1950) · Journal of the Physical Society of Japan · doi:10.1143/jpsj.5.435 · Cited by 1,055 · cited 1×
“Experimental realizat ion of small-scale adiabatic computation was already demonstrated [31].”
MethodFeynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023
Geometric quantum computation using nuclear magnetic resonance
Jones, J. A., Vedral, V., Ekert, A., & Castagnoli, G. (2000) · Nature · doi:10.1038/35002528 · Cited by 812 · cited 1×
“It is a crucial ingredient in topological (and later, geometrical) quantum computation [ 18 ,23,27].”
BackgroundTheory 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 · cited 1×
“Moreover, [11,29,32] showed that adiabatic computation can ‘tunnel’ through wide energy barriers and thus outperform simulated annealing, a classical counterpart of the adiabatic model.”
BackgroundEfficient Quantum Algorithms for Simulating Sparse Hamiltonians
Berry, D. W., Ahokas, G., Cleve, R., & Sanders, B. C. (2007) · Communications in Mathematical Physics · doi:10.1007/s00220-006-0150-x · Cited by 692
Research works printed but not linked: 25
- D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, Adiabatic quantum computation is equivalent to standard quantum computation , in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004, pp. 42–51. · DOI · Paper page
- D. Aharonov, D. Gottesman, S. Irani, and J. Kempe, The power of quantum systems on a line , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, pp. 373–383. · DOI
- D. Aharonov, A. Kitaev, and N. Nisan, Quantum circuits with mixed states , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, 1998, pp. 20–30. · DOI · Paper page
- D. Aharonov and T. Naveh, Quantum NP - a Survey , preprint, 2002; available online from http://arxiv.org/abs/quant-ph/0210077. · arXiv
- D. Aharonov and A. Ta-Shma, Adiabatic quantum state generation and statistical zero-knowledge , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego, CA, 2003, pp. 20–29. · DOI · Paper page
- A. Ambainis and O. Regev, An Elementary Proof of the Quantum Adiabatic Theorem , preprint, 2004; available online from http://arxiv.org/abs/quant-ph/0411152v2. · arXiv
- B. Apolloni, N. Cesa-Bianchi, and D. de Falco, A numerical implementation of quantum annealing , in Proceedings of the Ascona/Locarno Conference, 1988, pp. 97–111.
- R. Bhatia, Matrix Analysis , Grad. Texts in Math. 169, Springer-Verlag, New York, 1997. · DOI · Paper page
- A. Childs, Universal Computation by Quantum Walk , preprint, 2008; available online from http://arxiv.org/PS_cache/arxiv/pdf/0806/0806.1972v1.pdf.
- W. van Dam, M. Mosca, and U. Vazirani, How powerful is adiabatic quantum computation? , in Proceedings of the 42nd IEEE Symposium on Foundation of Computer Science, Las Vegas, NV, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 279–287. · DOI · Paper page
- L. Eldar and O. Regev, Quantum SAT for a qutrit-cinquit pair is $QMA_1$-complete , in Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland, 2008, pp. 881–892. · DOI
- E. Farhi, J. Goldstone, and S. Gutmann, Quantum Adiabatic Evolution Algorithms versus Simulated Annealing , preprint, 2002; available online from http://arxiv.org/abs/quant-ph/0201031v1. · arXiv
- E. Farhi, J. Goldstone, and S. Gutmann, Quantum Adiabatic Evolution Algorithms with Different Paths , preprint, 2002; available online from http://arxiv.org/abs/quant-ph/0208135v1. · arXiv
- E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum Computation by Adiabatic Evolution , preprint, 2000; available online from http://arxiv.org/abs/quant-ph/0001106v1. · arXiv
- J. Friedman, Expanding Graphs , DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, Providence, RI, 1993. · doi:10.1090/dimacs/010
- R. A. Horn and C. R. Johnson, Matrix Analysis , Cambridge University Press, Cambridge, UK, 1985. · DOI · Paper page
- A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation , Grad. Stud. in Math. 47, AMS, Providence, RI, 2002. · DOI · Paper page
- L. Lovász, Random walks on graphs: A survey , in Combinatorics, Paul Erdős is Eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 353–397.
- A. Messiah, Quantum Mechanics , John Wiley and Sons, New York, 1958.
- D. Nagaj, Local Hamiltonians in Quantum Computation , Ph.D. thesis, MIT, 2008; available online from http://eprintweb.org/S/article/arxiv/0808.2117.
- M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, UK, 2000.
- X. Peng, Z. Liao, N. Xu, G. Qin, X. Zhou, D. Suter, and J. Du, A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation , preprint, 2008; available online from http://arxiv.org/abs/0808.1935v1. · DOI · Paper page
- B. Pepper, Adiabatic Computing Using 2-Local Hamiltonians on a Line , preprint.
- N. Schuch and F. Verstraete, Interacting Electrons, Density Functional Theory, and Quantum Merlin Arthur , preprint, 2007; available online from http://arxiv.org/abs/0712.0483v1. · arXiv
- A. Sinclair and M. Jerrum, Approximate counting, uniform generation, and rapidly mixing Markov chains (extended abstract), in Graph-Theoretic Concepts in Computer Science (Staffelstein, 1987), Lecture Notes in Comput. Sci. 314, Springer-Verlag, Berlin, 1988, pp. 134–148. · doi:10.1007/3-540-19422-3_11
Cited by
Items 201–300 of 395
New research progress of nuclear magnetic resonance quantum information processing
Xiang-Yu, K., Yuan-Ye, Z., Jing-Wei, W., Xin, T., Ke-Ren, L., & Gui-Lu, L. (2018) · Acta Physica Sinica · doi:10.7498/aps.67.20180754 · Cited by 8
Some Issues in Quantum Information Theory
Duan, R., Ji, Z., Feng, Y., & Ying, M. (2006) · Journal of Computer Science and Technology · doi:10.1007/s11390-006-0776-3 · Cited by 8
Quantum Atom Optics: Theory and Applications to Quantum TechnologyPreprint
Byrnes, T., & Ilo-Okeke, E. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.14601 · Cited by 33
“11.5 Adiabatic quantum computing: Farhi et al. (2001); Das and Chakrabarti (2008); Albash and Lidar (2018); Mizel et al. (2007); Aharonov et al. (2008); Mohseni et al. (2019).”
BackgroundInfluentialA numerical approach for calculating exact non-adiabatic terms in quantum dynamics
Lawrence, E. D. C., Schmid, S. F. J., Čepaitė, I., Kirton, P., & Duncan, C. W. (2025) · SciPost Physics · doi:10.21468/scipostphys.18.1.014 · Cited by 10
Load balancing for high performance computing using quantum annealing
Rathore, O., Basden, A. G., Chancellor, N., & Kusumaatmaja, H. (2025) · Physical Review Research · doi:10.1103/physrevresearch.7.013067 · Cited by 14
Quantum Adiabatic Doping with Incommensurate Optical Lattices
Lin, J. H., Nan, J., Luo, Y., Yao, X.-C., & Li, X. (2019) · Physical Review Letters · doi:10.1103/physrevlett.123.233603 · Cited by 5
Dissipative failure of adiabatic quantum transport as a dynamical phase transition
Barratt, F., Bou-Comas, A., Crowley, P. J. D., Oganesyan, V., Sollich, P., & Green, A. G. (2021) · Physical Review A · doi:10.1103/physreva.103.052427 · Cited by 8
Mandal, A., Sarkar, R. S., Chakraborty, S., & Adhikari, B. (2022) · Physical Review A · doi:10.1103/physreva.106.042405 · Cited by 9
“This long-time behaviour of quantum walks has been fundamental to demonstrate the speedup of several quantum algorithms [4, 14, 15], to prove the equivalence between the circuit and Hamiltonian models of quantum computing [16, 17] and also to understand the phenomenon of mixing of quantum walks [1, 18–20].”
Gülbahar, B. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2286-6 · Cited by 9
Adame, J. I., & Warzel, S. (2015) · Journal of Mathematical Physics · doi:10.1063/1.4934723 · Cited by 6
Symmetry-protected adiabatic quantum transistors
Williamson, D. J. (2014) · The Sydney eScholarship Repository (The University of Sydney) · Cited by 8
From Quantum Computing to Quantum-inspired Computation for Neuromorphic Advancement -- A SurveyPreprint
Jha, R. K. (2023) · doi:10.36227/techrxiv.24053250.v1 · Cited by 5
Variational Ground-State Quantum Adiabatic Theorem
Žunkovič, B., Torta, P., Pecci, G., Lami, G., & Collura, M. (2025) · Physical Review Letters · doi:10.1103/physrevlett.134.130601 · Cited by 14
A Review on Models and Applications of Quantum Computing
Grigoryan, E., Kumar, S., & Pinheiro, P. R. (2025) · Quantum Reports · doi:10.3390/quantum7030039 · Cited by 14
“Later, it was shown that the adiabatic model is polynomially equivalent to gate model [39].”
Parallel quantum computing simulations via quantum accelerator platform virtualization
Claudino, D., Lyakh, D. I., & McCaskey, A. (2024) · Future Generation Computer Systems · doi:10.1016/j.future.2024.06.007 · Cited by 9
Three-flavor collective neutrino oscillation simulations on a qubit quantum annealer
Chernyshev, I. A. (2025) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.111.043017 · Cited by 9
Lagrangian duality in quantum optimization: Overcoming QUBO limitations for constrained problems
Gabbassov, E., Rosenberg, G., & Scherer, A. (2025) · Physical Review Research · doi:10.1103/53gd-2374 · Cited by 12
“Our optimization scheme is based on adiabatic quantum computation (AQC) [6] which is polynomially equivalent to the standard circuit-model of quantum computation [7].”
MethodPolynomial time algorithms for estimating spectra of adiabatic Hamiltonians
Bringewatt, J., Dorland, W., & Jordan, S. P. (2019) · Physical Review A · doi:10.1103/physreva.100.032336 · Cited by 4
“[17] Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, “Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation,” SIAM Journal on Computing.”
BackgroundMethodQuantum Annealing in the NISQ Era: Railway Conflict Management
Domino, K., Koniorczyk, M., Krawiec, K., Jałowiecki, K., Deffner, S., & Gardas, B. (2023) · Entropy · doi:10.3390/e25020191 · Cited by 39
“These have their roots in adiabatic quantum computing, a new computational paradigm [40], which, under additional assumptions, is equivalent [41] to the gate model of quantum computation [42] (provided that the specific interactions between quantum bits can be realized experimentally [43]).”
BackgroundApplications of Quantum Annealing to Music Theory
Arya, A., Botelho, L., Cañete, F., Kapadia, D., & Salehi, Ö. (2022) · Springer eBooks · doi:10.1007/978-3-031-13909-3_15 · Cited by 9
Geometry of the adiabatic theorem
Lobo, A. C., Ribeiro, R. A., Ribeiro, C. D. A., & Dieguez, P. R. (2012) · European Journal of Physics · doi:10.1088/0143-0807/33/5/1063 · Cited by 7
Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds
Dooley, S., Kells, G., Katsura, H., & Dorlas, T. C. (2020) · Physical Review A · doi:10.1103/physreva.101.042302 · Cited by 6
Improving nonstoquastic quantum annealing with spin-reversal transformations
Lykiardopoulou, E. M., Zucca, A., Scivier, S. A., & Amin, M. H. S. (2021) · Physical Review A · doi:10.1103/physreva.104.012619 · Cited by 7
“They also can perform universal quantum computation [20–22] suggesting that nonstoquasticiy may be connected to quantum advantage in QA.”
BackgroundLefschetz thimble quantum Monte Carlo for spin systems
Mooney, T. C., Bringewatt, J., Warrington, N. C., & Brady, L. T. (2022) · Physical review. B./Physical review. B · doi:10.1103/physrevb.106.214416 · Cited by 5
“Adiabatic quantum computation with general Hamiltonians is known to be universal [15], and therefore, it is expected that the quantum advantage over classical computation arises for Hamiltonians that exhibit a sign problem.”
BackgroundAnalysis of the shortest vector problems with quantum annealing to search the excited states
Ura, K., Imoto, T., Nikuni, T., Kawabata, S., & Matsuzaki, Y. (2023) · Japanese Journal of Applied Physics · doi:10.35848/1347-4065/acba21 · Cited by 5
Matrix Product Operator Simulations of Quantum Algorithms
Woolfe, K. J. (2015) · Minerva Access (University of Melbourne) · Cited by 9
A Leap among Entanglement and Neural Networks: A Quantum Survey.Preprint
Massoli, F. V., Vadicamo, L., Amato, G. M., & Falchi, F. (2021) · arXiv (Cornell University) · Cited by 5
An Improved Quantum Solution for the Stereo Matching Problem
Heidari, S., Rogers, M., & Delmas, P. J. (2021) · International Conference on Image and Vision Computing New Zealand (IVCNZ) · doi:10.1109/ivcnz54163.2021.9653310 · Cited by 4
“The quantum annealing model, a relatively new model of quantum computing, was introduced in [16] as an alternative equivalent [17] to the quantum gate model, where qubits are particles in a quantum system that evolves based on special forces acting on them.”
MethodContinuous-time quantum optimization without the adiabatic principle
Banks, R. J., Raftis, G. S., Browne, D. E., & Warburton, P. A. (2025) · Physical Review A · doi:10.1103/physreva.111.032414 · Cited by 6
“Often QA is justi-fied by its apparent proximity to AQO, for which proofs of speedup exist [17–19].”
Experimental verification of the inertial theorem control protocols
Hu, C.-K., Dann, R., Cui, J., Huang, Y., Li, C., Guo, G., Santos, A. C., & Kosloff, R. (2021) · New Journal of Physics · doi:10.1088/1367-2630/ac2710 · Cited by 4
Kernel function based quantum algorithms for finite temperature quantum simulation
Wang, H., Nan, J., Zhang, T., Qiu, X., Chen, W., & Li, X. (2023) · Physical review. B./Physical review. B · doi:10.1103/physrevb.108.085102 · Cited by 7
Building an adiabatic quantum computer simulation in the classroom
Rodríguez-Laguna, J., & Santalla, S. N. (2018) · American Journal of Physics · doi:10.1119/1.5021360 · Cited by 5
Quantum Algebraic Machine Learning
Malov, D. (2020) · IEEE International Conference on Intelligent Systems · doi:10.1109/is48319.2020.9199982 · Cited by 4
“It was proposed by Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser in [5] as a general computational model, and it was later shown to be polynomially equivalent to universal, circuit-model quantum computation by Dorit Aharonov and colleagues in [6].”
MethodExpressing multiagent coalition structure problems for optimisation by quantum annealing
Leon, F., & Bǎdicǎ, C. (2018) · Enterprise Information Systems · doi:10.1080/17517575.2018.1552993 · Cited by 4
“It has been proven (Aharonov et al. 2008) that the model of adiabatic computation is polynomially equivalent to the standard model of quantum computation and that standard quantum computation can be e ffi ciently simulated by adiabatic computation.”
Efficient diabatic quantum algorithm in number factorization
Shi, A., Guan, H., & Zhang, W. (2020) · Physics Letters A · doi:10.1016/j.physleta.2020.126745 · Cited by 4
Quantum advantage from energy measurements of many-body quantum systems
Novo, L., Bermejo-Vega, J., & García−Patrón, R. (2021) · Refubium (Universitätsbibliothek der Freien Universität Berlin) · doi:10.17169/refubium-31445 · Cited by 4
Efficient optimization of perturbative gadgets
Cao, Y., & Kais, S. (2017) · Quantum Information and Computation · doi:10.26421/qic17.9-10 · Cited by 4
“Quantum many-body interactions arise in a variety of contexts in quantum information and quantum computation, such as topological quantum computing [1, 2, 3, 4], measurement-based model of quantum computing [5, 6, 7, 8, 9, 10], adiabatic simulation of quantum chemistry [11], universal adiabatic quantum computation[15,…”
Detailed Analysis of Circuit-to-Hamiltonian MappingsPreprint
Watson, J. D. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.01481 · Cited by 13
Load Balancing For High Performance Computing Using Quantum AnnealingPreprint
Rathore, O., Basden, A. G., Chancellor, N., & Kusumaatmaja, H. (2024) · Research Square · doi:10.21203/rs.3.rs-4145412/v1 · Cited by 4
Statistical Mechanics of Classical and Quantum Computational Complexity
Laumann, C. R., Moessner, R., Scardicchio, A., & Sondhi, S. L. (2012) · Lecture notes in physics · doi:10.1007/978-3-642-10449-7_7 · Cited by 4
An initial step toward a quantum annealing approach to the discrete logarithm problem
Mahasinghe, A., & Jayasinghe, Y. (2022) · Security and Privacy · doi:10.1002/spy2.234 · Cited by 5
“15”
BackgroundProbabilistic tensor optimization of quantum circuits for the max−k−cut problem
Paradezhenko, G. V., Pervishko, A. A., & Yudin, D. (2024) · Physical Review A · doi:10.1103/physreva.109.012436 · Cited by 4
Meli, N. K., Golyanik, V., Benkner, M. S., & Moeller, M. (2025) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52734.2025.01064 · Cited by 5
“Adiabatic Quantum Computing (AQC) is a model of quantum computation which is polynomially equivalent to the circuit model [2].”
Decoherence of a tunable capacitively shunted flux qubit
Trappen, R., Dai, X., Yurtalan, M. A., Melanson, D., Tennant, D., Martinez, A. J., Tang, Y., Gibson, J., Grover, J. A., Disseler, S., et al. (2025) · Communications Physics · doi:10.1038/s42005-025-02360-2 · Cited by 6
“In comparison to the more commonly-pursued gate-model quantum computation (GMQC), QA is in principle computationally equivalent [7, 8], and is more amenable to scaling up in the near term, since it does not require individual dynamic control of each qubit.”
Flux-qubit readout in the persistent-current basis at arbitrary bias points
Schöndorf, M., Lupaşcu, A., & Wilhelm, F. K. (2020) · Physical Review A · doi:10.1103/physreva.101.012305 · Cited by 2
Li, A., Zhang, C., & Li, L. (2021) · International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I-SMAC) · doi:10.1109/i-smac52330.2021.9640784 · Cited by 3
Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
Ramezanpour, A. (2022) · Physical Review A · doi:10.1103/physreva.106.012418 · Cited by 3
“[15] Aharonov D, Van Dam W, Kempe J, Landau Z, Lloyd S, Regev O.”
BackgroundExact counterdiabatic driving in finite topological lattice models
Duncan, C. W. (2024) · Physical review. B./Physical review. B · doi:10.1103/physrevb.109.245421 · Cited by 5
Linear regression using quantum annealing with continuous variables
Koura, A., Imoto, T., Ura, K., & Matsuzaki, Y. (2025) · Japanese Journal of Applied Physics · doi:10.35848/1347-4065/adad7e · Cited by 6
“Additionally, it has been shown that by using a non-stoquastic term and auxiliary qubits, QA can perform computations equivalent to gate-type quantum computation[13–15].”
BackgroundMethodMachine learning assisted quantum adiabatic algorithm design
Lin, J. H., Ye, M., Zhu, J., & Li, X. (2021) · Acta Physica Sinica · doi:10.7498/aps.70.20210831 · Cited by 3
Error-run-time trade-off in the adiabatic approximation beyond scaling relations
Passos, M. R., Taddei, M. M., & Filho, R. L. D. M. (2020) · Annals of Physics · doi:10.1016/j.aop.2020.168172 · Cited by 5
Fundamental Physics and Computation: The Computer-Theoretic Framework
Miguel-Tomé, S., Lázaro, Á. L. S., & Alonso-Romero, L. (2022) · Universe · doi:10.3390/universe8010040 · Cited by 3
A QUBO formulation for the Tree Containment problem
Dinneen, M. J., Ghodla, P. S., & Linz, S. (2022) · Theoretical Computer Science · doi:10.1016/j.tcs.2022.09.012 · Cited by 3
“[2] have developed an adiabatic simulation for any given quantum algorithm, which implies that AQC and the quantum gate model are polynomially equivalent.”
MethodSinha, A. (2022) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2021.0413 · Cited by 3
“Category C (QAC) Category D (QCI) paper id year citation reference paper id year citation reference C1 2001 1959 [52] D1 2000 43720 [53] C2 2000 1217 [54] D2 2001 6569 [55] C3 2008 739 [56] D3 1992 3278 [57] C4 2018 700 [58] D4 2000 3232 [59] C5 2001 517 [60] D5 2000 2933 [61] C6 2016 413 [62] D6 2000 2930 [63] C7 199…”
An anomaly in quantum phases induced by borders
Jing, J., Guidry, M., & Wu, L.-A. (2020) · Scientific Reports · doi:10.1038/s41598-020-63555-x · Cited by 3
Solovay–Kitaev Approximations of Special Orthogonal Matrices
Mahasinghe, A., Bandaranayake, S., & Silva, K. D. (2020) · Advances in Mathematical Physics · doi:10.1155/2020/2530609 · Cited by 4
Enhancement of adiabaticity via combined control in open quantum systems
Xie, Y.-Y., & Wang, Z.-M. (2025) · APL Quantum · doi:10.1063/5.0253494 · Cited by 2
Path Matters: Industrial Data Meet Quantum Optimization
Schmidbauer, L., Riofrío, C. A., Heinrich, F., Junk, V., Schwenk, U., Husslein, T., & Mauerer, W. (2025) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce65121.2025.00230 · Cited by 8
“Nevertheless, both models of computation are poly-nomially equivalent in their computational power [30].”
Asymptotic Exceptional Steady States in Dissipative Dynamics
Hu, Y.-M., & Budich, J. C. (2025) · Physical Review Letters · doi:10.1103/6lkq-8626 · Cited by 5
“…problems of general interest such as NP-complete satisfiability (SAT) problems [1–3] and their quantum counterparts known as QMA-complete problems [4–6] may be readily viewed as quantum state preparation tasks, e.g. solved by preparing the ground state of a suitable local parent Hamiltonian in a…”
Gupta, N., Punia, D., Gautam, K., Sikka, G., Sharma, A. K., & Farouk, A. (2026) · Computer Science Review · doi:10.1016/j.cosrev.2026.100942 · Cited by 4
The Improved Evolution Paths to Speedup Quantum Evolution
He, Y., Deng, Y. K., & Luo, M. (2015) · International Journal of Theoretical Physics · doi:10.1007/s10773-015-2838-1 · Cited by 2
“This approach has been proved to equivalent to the well-known standard quantum circuit model [2, 3].”
ResultQuantum Adiabatic Evolution for Pattern Recognition Problem
Fard, E. R., & Aghayar, K. (2017) · Chinese Physics Letters · doi:10.1088/0256-307x/34/12/120302 · Cited by 2
Role of Quantum Computing in a Data Analytics Environment
Tripathy, B. K., & Singh, A. (2023) · Advances in computational intelligence and robotics book series · doi:10.4018/978-1-6684-6821-0.ch014 · Cited by 3
Bożejko, W., Pempera, J., Uchroński, M., & Wodecki, M. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-36030-5_16 · Cited by 2
“Most importantly, it is shown that the AQC is polynomially equivalent to a universal gate-based quantum computer, since any quantum circuit can be represented as a time-dependent Hamiltonian with at most polynomial charge [1].”
A variational coherent quantum annealing protocol
Barraza, N., Barrios, G. A., Solano, E., & Albarrán-Arriagada, F. (2026) · Physics Letters A · doi:10.1016/j.physleta.2026.132302 · Cited by 6
“Adiabatic quantum computing (AQC) [1] is a universal computational paradigm, equivalent to gate-based quantum computing in terms of theoretical power [2], and it has yielded strong theoretical results [3–5].”
Quantum Software Ecosystem Design
Basermann, A., Epping, M., Fauseweh, B., Felderer, M., Lobe, E., Röhrig-Zöllner, M., Schmiedinghoff, G., Schuhmacher, P. K., Setyawati, Y., & Weinert, A. (2024) · Springer eBooks · doi:10.1007/978-3-031-64136-7_7 · Cited by 9
“Nevertheless, the authors of [170] and [2] have shown that QC and AQC are equivalent in the sense that each can efficiently simulate the other.”
BackgroundRealizations of standard quantum computational circuits by adiabatic evolution
Zobov, V. E., & Ermilov, A. S. (2007) · Theoretical and Mathematical Physics · doi:10.1007/s11232-007-0029-9 · Cited by 2
Measurement-driven analog of adiabatic quantum computation for frustration-free Hamiltonians
Zhao, L., Pérez-Delgado, C. A., Benjamin, S. C., & Fitzsimons, J. F. (2019) · Physical Review A · doi:10.1103/physreva.100.032331 · Cited by 7
Kavokin, A. V., Baumberg, J. J., Malpuech, G., & Laussy, F. P. (2017) · Oxford University Press eBooks · doi:10.1093/oso/9780198782995.003.0006 · Cited by 3
Progress in Quantum Algorithms
Shor, P. W. (2007) · Springer eBooks · doi:10.1007/0-387-27732-3_2 · Cited by 3
Mapping NP-Hard Problems to Restricted Adiabatic Quantum ArchitecturesPreprint
Mooney, G. J., Tonetto, S. U. Y., Hill, C. D., & Hollenberg, L. C. L. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.00249 · Cited by 9
“It has been shown to be polynomially equivalent [9, 10] to the circuit model and is believed to be more robust against control errors and certain kinds of decoherence [11, 12, 13, 14, 15].”
BackgroundTwo Combinatorial MA-Complete ProblemsPreprint
Aharonov, D., & Grilo, A. B. (2020) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2021.36 · Cited by 2
“6 We omit here the details of the proof, since it is a straight forward translation of [3], similarly to what’s done in Lemma 17.”
BackgroundResultSelf-citationOstilli, M., & Carlo Presilla, A. (2023) · Physical Review A · doi:10.1103/physreva.108.022205 · Cited by 3
CONVERGENCE RATE OF ALGORITHM FOR SOLVING LINEAR EQUATIONS BY QUANTUM ANNEALING
Tikhomirov, S. B., & Shalgin, V. S. (2024) · Журнал вычислительной математики и математической физики · doi:10.31857/s0044466924050061 · Cited by 1
Skipper: Improving the Reach and Fidelity of Quantum Annealers by Skipping Long Chains
Ayanzadeh, R., & Qureshi, M. K. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00079 · Cited by 6
“Both digital and analog QCs have polynomial equivalent computing power [2, 4].”
Electronic structure theory with molecular point group symmetries on quantum annealers
Desroches, J., & Dong, S. S. (2025) · The Journal of Chemical Physics · doi:10.1063/5.0261736 · Cited by 3
“Adiabatic quantum computation is an alternative model for universal quantum computation 7 .”
Huang, D., Dai, W., Gao, F., Yang, M., Pan, Y., Ju, J., & Ma, Y. (2025) · Advanced Quantum Technologies · doi:10.1002/qute.202500241 · Cited by 1
A Review of Quantum Scientific Computing Algorithms Relevant to Computational Mechanics
Raisuddin, O. M., & De, S. (2025) · Archives of Computational Methods in Engineering · doi:10.1007/s11831-025-10321-9 · Cited by 6
“The field predominantly adopts two approaches: gate-based quantum computing and adiabatic quantum computing, each representing a distinct methodology for quantum computation [6].”
Thermodynamic significance of QUBO encoding on quantum annealers
Doucet, E., Mzaouali, Z., Robertson, R., Gardas, B., Deffner, S., & Domino, K. (2026) · New Journal of Physics · doi:10.1088/1367-2630/ae6e98 · Cited by 1
“The spectral gap plays a key role in determining the accuracy of the annealing process [58–60], hence we expect comparatively minor performance variations when the gap is fixed.”
Sun, J., Zhang, Z., & Lu, S. (2026) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/ae7758 · Cited by 1
Quantum Computing Meets the Real World
Pudenz, K. L. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-21819-9_4 · Cited by 1
Can adiabatic algorithms with extra items always be efficient in quantum computation?
Zhang, Z., Lu, S., & Zhou, X. C. (2018) · Journal of Intelligent & Fuzzy Systems · doi:10.3233/jifs-169400 · Cited by 1
“We can clearly see this problem in a 2-dimension by using Grover-quantum as paper [7] stated.”
Semiclassical description of light–matter coupling
Kavokin, A. V., Baumberg, J. J., Malpuech, G., & Laussy, F. P. (2017) · Oxford University Press eBooks · doi:10.1093/oso/9780198782995.003.0004 · Cited by 1
Non-classical computing: feasible versus infeasible.
Cockshott, P. W., Mackenzie, L., & Michaelson, G. J. (2010) · Electronic workshops in computing · doi:10.14236/ewic/vocs2010.4 · Cited by 2
“More recent alternative models such as the quantum adiabatic computer have also been shown to be computationally equivalent to the circuit model (Aharonov et al. (2008) ) to within”
MethodQuantum-Walk-Inspired Dynamic Adiabatic Local Search
Chiang, C.-F., & Alsing, P. M. (2023) · Entropy · doi:10.3390/e25091287 · Cited by 3
“In [40] the cost of the Adiabatic algorithm was defined to be the dimensionless quantity”
Quantum Artificial Intelligence: A tutorial
Martín‐Guerrero, J. D., Lamata, L., & Villmann, T. (2023) · European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN) · doi:10.14428/esann/2023.es2023-2 · Cited by 1
“Quantum vector quantization (QVQ) requires an appropriate encoding of the data usually realized as amplitude or basis encoding, both being used in gate-based QC [56] and adiabatic QC [57].”
Co-Design of Quantum Hardware and Algorithms in Nuclear and High Energy Physics
Franz, M., Zurita, P., Diefenthaler, M., & Mauerer, W. (2024) · EPJ Web of Conferences · doi:10.1051/epjconf/202429512002 · Cited by 3
Quantum computation by cooling
Cho, J. (2024) · Journal of the Korean Physical Society · doi:10.1007/s40042-024-01137-0 · Cited by 2
Support vector machine based on the quadratic unconstrained binary optimization model
Wang, Q. (2024) · Journal of Physics Conference Series · doi:10.1088/1742-6596/2858/1/012002 · Cited by 1
“Aharonov et al. [5] showed that adiabatic quantum computing is equivalent to standard quantum computing.”
Subsampling factorization machine annealing
Hama, Y., & Kadowaki, T. (2025) · Physical Review Research · doi:10.1103/qgpq-6dmr · Cited by 4
Generation of elementary gates and Bell’s states using controlled adiabatic evolutions
Benmachiche, A., Ali, S., Turaev, S., Bahloul, D., Messikh, A., & Wahiddin, M. R. (2019) · International Journal of Quantum Information · doi:10.1142/s0219749919500205 · Cited by 1
Command and control organization generation method based on adaptive quantum genetic algorithm
Sun, P., Wu, J., Wang, X., Jiao, Z., & He, Y. (2019) · IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC) · doi:10.1109/imcec46724.2019.8983958 · Cited by 1
“Quantum genetic algorithm Quantum genetic algorithm (QGA)[13][14][15] is a kind of optimization method combining quantum computation and genetic algorithm.”
MethodZulehner, A., & Wille, R. (2020) · Springer eBooks · doi:10.1007/978-3-030-41753-6_2 · Cited by 1
Duda, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.04456 · Cited by 1
Robustness of Discretization in Digital Adiabatic SimulationPreprint
Yi, C. (2021) · arXiv (Cornell University) · Cited by 1
Adiabatic Quantum Graph Matching with Permutation Matrix ConstraintsPreprint
Benkner, M. S., Golyanik, V., Theobalt, C., & Moeller, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.04032 · Cited by 2
“(3) Thus a sufficient upper bound for λ is given by”
BackgroundFrom Quantum Computing to Quantum-inspired Computation for Neuromorphic Advancement – A SurveyPreprint
Jha, R. K. (2023) · doi:10.36227/techrxiv.24053250 · Cited by 6
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0003 · Cited by 1
Economic Consequences of Moore's LawPreprint
Macey-Dare, R. (2013) · SSRN Electronic Journal · doi:10.2139/ssrn.2261119 · Cited by 1
Solving Hard Problems on Adiabatic Quantum Computers
Ciocirlan, D., Ţăpuş, N., & Dragomir, D. (2015) · International Conference on Control Systems and Computer Science · doi:10.1109/cscs.2015.100
“It has been recently proven that these two approaches are computationally equivalent [5] [6].”
Background
Metadata
- Authors
- Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O.
- Venue
- SIAM Review
- Published
- 2008-01
- Volume
- 50
- Issue
- 4
- Pages
- 755-787
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2041432245
- Semantic Scholar
- ab891721d230583649a4af16d8af6f602ff2f6b8
- Cited by
- 395
- References
- 35
- Citations by year
- 2026: 15 · 2025: 30 · 2024: 26 · 2023: 53 · 2022: 36 · 2021: 48 · 2020: 40 · 2019: 25 · 2018: 20 · 2017: 36 · 2016: 9 · 2015: 12 · 2014: 7 · 2013: 4 · 2012: 9
- FWCI
- 7.93
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Review (publishedVersion)
- 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
- adiabatic quantum computation, eigenvectors, nearest-neighbor interactions, two-dimensional grids
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.