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 101–200 of 395
Period finding with adiabatic quantum computation
Hen, I. (2014) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/105/50005 · Cited by 33
The Physics of Quantum Information
Sevrin, A. (2023) · doi:10.1142/13369 · Cited by 28
De-Signing Hamiltonians for Quantum Adiabatic Optimization
Crosson, E., Albash, T., Hen, I., & Young, A. P. (2020) · Quantum · doi:10.22331/q-2020-09-24-334 · Cited by 34
“We will compare these matrices to a distributionW+ of random matrices with nonnegative entries drawn uniformly from [0, 1] — these would be the ‘shifted’ matrices.”
BackgroundMethodQuantum and classical dynamics in adiabatic computation
Crowley, P. J. D., Đurić, T., Vinci, W., Warburton, P. A., & Green, A. G. (2014) · Physical Review A · doi:10.1103/physreva.90.042317 · Cited by 29
Solving the Hamiltonian Cycle Problem using a Quantum Computer
Mahasinghe, A., Hua, R., Dinneen, M. J., & Goyal, R. (2019) · Australasian Computer Science Week Multiconference (ACSW) · doi:10.1145/3290688.3290703 · Cited by 36
“Although polynomial equivalence of the circuit and adiabatic frameworks has been proved under certain conditions [3, 26], the run-time of adiabatic algorithms can become exponential due to physical effects.”
BackgroundHow Fast Do Quantum Walks Mix?
Chakraborty, S., Luh, K., & Roland, J. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.050501 · Cited by 38
“[12] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev.”
BackgroundQuantum Science and Quantum Technology
Wang, Y., & Song, X. (2020) · Statistical Science · doi:10.1214/19-sts745 · Cited by 27
Cryogenic Electronics and Quantum Information Processing
Holmes, D. S. (2021) · doi:10.1109/irds54852.2021.00012 · Cited by 31
Quantum algorithms for scientific computing
Au-Yeung, R., Camino, B., Rathore, O., & Kendon, V. M. (2024) · Reports on Progress in Physics · doi:10.1088/1361-6633/ad85f0 · Cited by 44
Family of [[6k,2k,2]] codes for practical and scalable adiabatic quantum computation
Ganti, A., Onunkwo, U., & Young, K. C. (2014) · Physical Review A · doi:10.1103/physreva.89.042313 · Cited by 20
On the power of coherently controlled quantum adiabatic evolutions
Kieferová, M., & Wiebe, N. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/12/123034 · Cited by 22
“Therefore the class of adiabatic evolutions considered includes a set of Hamiltonians that generate a family of evolutions that are polynomially equivalent to the circuit model [36].”
BackgroundManenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0002 · Cited by 20
Wild, K., Breitenbücher, U., Harzenetter, L., Leymann, F., Vietz, D., & Zimmermann, M. (2020) · IEEE International Enterprise Distributed Object Computing Conference (EDOC) · doi:10.1109/edoc49727.2020.00024 · Cited by 33
Bożejko, W., Pempera, J., Uchroński, M., & Wodecki, M. (2024) · Future Generation Computer Systems · doi:10.1016/j.future.2024.02.016 · Cited by 18
Assessing and advancing the potential of quantum computing: A NASA case study
Rieffel, E. G., Asanjan, A. A., Alam, M. S., Anand, N., Bernal, D. E., Block, S., Brady, L. T., Cotton, S., Izquierdo, Z. G., Grabbe, S. R., et al. (2024) · Future Generation Computer Systems · doi:10.1016/j.future.2024.06.012 · Cited by 34
“Quantum annealing [32, 33] is a general and universal [34] setting for quantum computation that relies on continuous time evolution of a quantum system under mixing and problem Hamiltonians.”
BackgroundAnalysis and limitations of modified circuit-to-Hamiltonian constructions
Bausch, J., & Crosson, E. (2018) · Quantum · doi:10.22331/q-2018-09-19-94 · Cited by 48
“Keeping with tradition [18, 4, 6], we exhibit H as a T + 1 by T + 1 matrix in the time register basis,”
Error suppression in adiabatic quantum computing with qubit ensembles
Mohseni, N., Narożniak, M., Pyrkov, A. N., Ivannikov, V., Dowling, J. P., & Byrnes, T. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00405-2 · Cited by 20
Problem Solving with Hopfield Networks and Adiabatic Quantum Computing
Bauckhage, C., Sánchez, R. J., & Sifa, R. (2020) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn48605.2020.9206916 · Cited by 20
“We also note again that adiabatic quantum computing (as considered in this paper) and quantum gate computing are polynomially equivalent [15].”
BackgroundQuantum annealing – foundations and frontiers
Cohen, E., & Tamir, B. (2015) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2015-02345-1 · Cited by 20
Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
Bohdanowicz, T. C., Crosson, E., Nirkhe, C., & Yuen, H. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316384 · Cited by 24
Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer
Vinci, W., Markstrom, K., Boixo, S., Roy, A., Spedalieri, F., Warburton, P. A., & Simone Severini, B. (2014) · UCL Discovery (University College London) · Cited by 17
Lower Bounds on Quantum Annealing Times
García-Pintos, L. P., Brady, L. T., Bringewatt, J., & Liu, Y.-K. (2023) · Physical Review Letters · doi:10.1103/physrevlett.130.140601 · Cited by 19
“This mechanism is as powerful as standard quantum computation [7].”
BackgroundFermionic quantum approximate optimization algorithm
Yoshioka, T., Sasada, K., Nakano, Y., & Fujii, K. (2023) · Physical Review Research · doi:10.1103/physrevresearch.5.023071 · Cited by 26
Determining system Hamiltonian from eigenstate measurements without correlation functions
Hou, S., Cao, N., Lu, S., Shen, Y., Poon, Y., & Zeng, B. (2020) · New Journal of Physics · doi:10.1088/1367-2630/abaacf · Cited by 16
Analysis and limitations of modified circuit-to-Hamiltonian constructions
Bausch, J., & Crosson, E. (2018) · Apollo (University of Cambridge) · doi:10.17863/cam.44094 · Cited by 17
QProv: A provenance system for quantum computing
Weder, B., Barzen, J., Leymann, F., Salm, M., & Wild, K. (2021) · IET Quantum Communication · doi:10.1049/qtc2.12012 · Cited by 30
“As already discussed, QProv can also be extended to collect provenance attributes targeting other quantum computing models, such as the adiabatic model [47, 48].”
BackgroundA comparative study of universal quantum computing models: Toward a physical unification
Wang, D. (2021) · Quantum Engineering · doi:10.1002/que2.85 · Cited by 23
“At the mean time, various universal quantum computing models (UQCM) have been developed [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24], and some of them hardly have classical analog.”
BackgroundMitigating algorithmic errors in quantum optimization through energy extrapolation
Cao, C., Yu, Y., Wu, Z., Shannon, N., Zeng, B., & Joynt, R. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac969c · Cited by 26
Mandrà, S., Guerreschi, G. G., & Aspuru‐Guzik, A. (2015) · Physical Review A · doi:10.1103/physreva.92.062320 · Cited by 19
“[16] Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and O.”
BackgroundMethodImproved Gap Estimates for Simulating Quantum Circuits by Adiabatic Evolution
Deift, P. A., Ruskai, M. B., & Spitzer, W. (2006) · Quantum Information Processing · doi:10.1007/s11128-006-0045-y · Cited by 17
“Although this may affect the time estimates, it seems unlikely to do more than change the order of the polynomial.”
BackgroundInfluentialLocal Hamiltonians in Quantum ComputationPreprint
Nagaj, D. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0808.2117 · Cited by 37
Simulation of quantum walks and fast mixing with classical processes
Apers, S., Sarlette, A., & Ticozzi, F. (2018) · Physical Review A · doi:10.1103/physreva.98.032115 · Cited by 20
A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing ProblemPreprint
Harikrishnakumar, R., Nannapaneni, S., Nguyen, N. H., Steck, J. E., & Behrman, E. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.12478 · Cited by 61
“Quantum annealing is implemented by evolving the Hamiltonian dynamics from an initial quantum state to a final quantum state, which corresponds to the solution of an optimization problem of interest [15].”
Quantum-Resistance in Blockchain Networks
López, M. A., León, D. L., Cerón, S., Batista, A. L., Pareja, A., da Silva, M. M., Pardo, A., Jones, D., Worrall, D., Merriman, B., et al. (2021) · doi:10.18235/0003313 · Cited by 20
Least-squares solutions to polynomial systems of equations with quantum annealing
Chang, T. H., Lux, T. C. H., & Tipirneni, S. S. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2489-x · Cited by 20
Simulation of adiabatic quantum computing for molecular ground states
Kremenetski, V., Mejuto-Zaera, C., Cotton, S. J., & Tubman, N. M. (2021) · The Journal of Chemical Physics · doi:10.1063/5.0060124 · Cited by 28
Success of digital adiabatic simulation with large Trotter step
Yi, C. (2021) · Physical Review A · doi:10.1103/physreva.104.052603 · Cited by 22
“[23] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev.”
BackgroundQuantum SVR for Chlorophyll Concentration Estimation in Water With Remote Sensing
Pasetto, E., Riedel, M., Melgani, F., Michielsen, K. F. L., & Cavallaro, G. (2022) · IEEE Geoscience and Remote Sensing Letters · doi:10.1109/lgrs.2022.3200325 · Cited by 15
“QA is closely related to adiabatic QC (AQC) [16], which was shown to be polynomially equivalent to the universal gate-based model, which is a different paradigm of QC [17].”
MethodEnvironment-assisted analog quantum search
Novo, L., Chakraborty, S., Mohseni, M., & Omar, Y. (2018) · Physical Review A · doi:10.1103/physreva.98.022316 · Cited by 16
“Furthermore, for alternative models of quantum computation such as adiabatic [5,6] or quantum walks [7,8], the theory of error correction is much less developed or nonexistent [9–11].”
BackgroundOptimization of a refinery scheduling process with column generation and a quantum annealer
Ossorio-Castillo, J., & Pena-Brage, F. (2021) · Optimization and Engineering · doi:10.1007/s11081-021-09662-8 · Cited by 19
Tomography of time-dependent quantum Hamiltonians with machine learning
Han, C.-D., Glaz, B. J., Haile, M., & Lai, Y. (2021) · Physical Review A · doi:10.1103/physreva.104.062404 · Cited by 19
“Since the Hamiltonian is constant over time, this effectively leads to quantum adiabatic computing systems, where quantum computing algorithms can be performed on the ground states [10].”
BackgroundKavokin, A. V., Baumberg, J. J., Malpuech, G., & Laussy, F. P. (2017) · Oxford University Press eBooks · doi:10.1093/oso/9780198782995.003.0001 · Cited by 15
Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers
Rouzé, C., França, D. S., & Alhambra, A. M. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718268 · Cited by 26
Speedup of the quantum adiabatic algorithm using delocalization catalysis
Cao, C., Xue, J., Shannon, N., & Joynt, R. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.013092 · Cited by 20
From Digital Humanities to Quantum Humanities: Potentials and Applications
Barzen, J. (2022) · Springer eBooks · doi:10.1007/978-3-030-95538-0_1 · Cited by 24
Quantum Hypercomputation—Hype or Computation?
Hagar, A., & Korolev, A. (2007) · Philosophy of Science · doi:10.1086/521969 · Cited by 15
“In section ( 2 ) we describe the quantum adiabatic “hypercomputer”.”
BackgroundCustomized Quantum Annealing Schedules
Khezri, M., Dai, X., Yang, R., Albash, T., Lupaşcu, A., & Lidar, D. A. (2022) · Physical Review Applied · doi:10.1103/physrevapplied.17.044005 · Cited by 22
Quantum Optimization Algorithms in Operations Research: Methods, Applications, and ImplicationsPreprint
Klug, F. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4854668 · Cited by 25
Manenti, R., & Motta, M. (2023) · doi:10.1093/oso/9780198787488.001.0001 · Cited by 29
Jin, S., & Liu, N. (2024) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2023.0370 · Cited by 41
“For instance, combinatorial search problems can be turned into optimisation problems that are solved in continuous time through quantum adiabatic computation [11, 12] Here one begins with the known ground state of one Hamiltonian which adiabatically evolves to the ground state of another Hamiltonian whose ground state…”
Fixing detailed balance in ancilla-based dissipative state engineering
Lambert, N., Cirio, M., Lin, J.-D., Menczel, P., Liang, P., & Nori, F. (2024) · Physical Review Research · doi:10.1103/physrevresearch.6.043229 · Cited by 21
Accuracy Guarantees and Quantum Advantage in Analog Open Quantum Simulation with and without Noise
Kashyap, V., Styliaris, G., Mouradian, S., Cirac, J. I., & Trivedi, R. (2025) · Physical Review X · doi:10.1103/physrevx.15.021017 · Cited by 45
Nonpairwise Interactions Induced by Virtual Transitions in Four Coupled Artificial Atoms
Schöndorf, M., & Wilhelm, F. K. (2019) · Physical Review Applied · doi:10.1103/physrevapplied.12.064026 · Cited by 12
Investigating the Chinese postman problem on a quantum annealer
Siloi, I., Carnevali, V., Pokharel, B., Fornari, M., & Felice, R. D. (2021) · Quantum Machine Intelligence · doi:10.1007/s42484-020-00031-9 · Cited by 15
Nonperturbative embedding for highly nonlocal Hamiltonians
Subaşı, Y., & Jarzynski, C. (2016) · Physical Review A · doi:10.1103/physreva.94.012342 · Cited by 14
Hybrid quantum annealing decomposition framework for unit commitment
Ling, J., Zhang, Q., Geng, G., & Jiang, Q. (2024) · Electric Power Systems Research · doi:10.1016/j.epsr.2024.111121 · Cited by 22
Mediator-assisted cooling in quantum annealing
Pino, M., & García‐Ripoll, J. J. (2020) · Physical Review A · doi:10.1103/physreva.101.032324 · Cited by 11
Anneal-path correction in flux qubits
Khezri, M., Grover, J. A., Basham, J. I., Disseler, S., Chen, H., Novikov, S., Zick, K. M., & Lidar, D. A. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00371-9 · Cited by 15
“1⁄4 e2 Cz n̂ 2 2 þ e 2 2Cshþð4αþ1ÞCz ð2n̂1 þ n̂2Þ (2); (7)”
Quantum Natural Language Generation on Near-Term Devices
Karamlou, A., Wootton, J. R., & Pfaffhauser, M. (2022) · International Conference on Natural Language Generation · doi:10.18653/v1/2022.inlg-main.22 · Cited by 22
On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma
Gilyén, A., & Sattath, O. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.47 · Cited by 25
“levels – denoted Δ(H), plays an important role both in physics and computer science, particularly in Hamiltonian complexity theory, see for example [28], [29], [30], [31].”
BackgroundDigitized counterdiabatic quantum algorithms for logistics scheduling
Dalal, A., Montalban, I., Hegade, N. N., Cadavid, A. G., Solano, E., Awasthi, A., Vodola, D., Jones, C. R., Weiß, H., & Füchsel, G. (2024) · Physical Review Applied · doi:10.1103/physrevapplied.22.064068 · Cited by 16
“Since adiabatic quantum computing (AQC) with non-stoquastic Hamiltonians is equivalent with the circuit model of quantum computing [49], any computational problem can in principle be treated with AQC.”
Solving the Shipment Rerouting Problem with Quantum Optimization Techniques
Yarkoni, S., Huck, A., Schülldorf, H., Speitkamp, B., Tabrizi, M. S., Leib, M., Bäck, T., & Neukart, F. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-87672-2_33 · Cited by 17
Accelerated Quantum Adiabatic Transfer in Superconducting Qubits
Zheng, W., Xu, J., Wang, Z., Dong, Y., Lan, D., Tan, X., & Yu, Y. (2022) · Physical Review Applied · doi:10.1103/physrevapplied.18.044014 · Cited by 14
Nau, M. A., Vija, A. H., Gohn, W., Reymann, M. P., & Maier, A. (2023) · Journal of Imaging · doi:10.3390/jimaging9100221 · Cited by 19
“In theory, AQC is equivalent to gate-based QC and, therefore, universal [4].”
MethodOptimization by a quantum reinforcement algorithm
Ramezanpour, A. (2017) · Physical Review A · doi:10.1103/physreva.96.052307 · Cited by 12
“Quantum random walks [8–13] and adiabatic quantum computation [14, 15] are important examples of quantum approaches to universal computations [16, 17].”
BackgroundFiorelli, E., Rotondo, P., Marcuzzi, M., Garrahan, J. P., & Lesanovsky, I. (2019) · Physical Review A · doi:10.1103/physreva.99.032126 · Cited by 12
Disorder-assisted graph coloring on quantum annealers
Więckowski, A., Deffner, S., & Gardas, B. (2019) · Physical Review A · doi:10.1103/physreva.100.062304 · Cited by 11
“Adi-abatic quantum computing is a computational paradigm [14] that has the potential to solve many problems that a universal quantum computer can also solve [15].”
BackgroundImproved QUBO Formulation of the Graph Isomorphism Problem
Hua, R., & Dinneen, M. J. (2019) · SN Computer Science · doi:10.1007/s42979-019-0020-1 · Cited by 10
Grand Challenge of Quantum Applications
Babbush, R., King, R., Boixo, S., Huggins, W. J., Khattar, T., Low, G. H., McClean, J. R., O’Brien, T. E., & Rubin, N. C. (2026) · PRX Quantum · doi:10.1103/6r9l-lynr · Cited by 70
“Adiabatic algorithm [22,67,68] Early results on QAOA [23] Topological data analysis [61] Simulating differential equations [69–72] Generative learning of shallow quantum circuits [54,73] However, this does not mean the Algorithms Stage is without challenge.”
Smart Rebalancing for Bike Sharing Systems using Quantum Approximate Optimization Algorithm
Harikrishnakumar, R., & Nannapaneni, S. (2021) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc48978.2021.9564714 · Cited by 11
The Kitaev–Feynman clock for open quantum systems
Tempel, D. G., & Aspuru‐Guzik, A. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/11/113066 · Cited by 12
Optimizing adiabatic quantum pathways via a learning algorithm
Yang, X., Liu, R., Li, J., & Peng, X. (2020) · Physical Review A · doi:10.1103/physreva.102.012614 · Cited by 11
Symmetry-protected adiabatic quantum transistors
Williamson, D. J., & Bartlett, S. D. (2015) · New Journal of Physics · doi:10.1088/1367-2630/17/5/053019 · Cited by 17
“Although not immediately obvious, it can be shown that this model is equivalent in computational power to the standard circuit model using a standard construction that encodes the history of a whole quantum circuit into the ground state of a local Hamiltonian [40].”
BackgroundModels of optical quantum computing
Krovi, H. (2017) · Nanophotonics · doi:10.1515/nanoph-2016-0136 · Cited by 10
“In fact, in [40], this has been made into a computational model and it was shown that it is equivalent to the standard circuit model.”
MethodQuantum annealing in spin-boson model: from a perturbative to an ultrastrong mediated coupling
Pino, M., & García‐Ripoll, J. J. (2018) · New Journal of Physics · doi:10.1088/1367-2630/aaeeea · Cited by 11
“Adiabatic quantum computers can be as powerful as universal quantum computers based on quantum gates [2], provided the Hamiltonian H is a general enough spin model.”
BackgroundSemi-supervised time series classification method for quantum computing
Yarkoni, S., Kleshchonok, A., Dzerin, Y., Neukart, F., & Hilbert, M. (2021) · Quantum Machine Intelligence · doi:10.1007/s42484-021-00042-0 · Cited by 11
Quantum ground state isoperimetric inequalities for the energy spectrum of local HamiltoniansPreprint
Crosson, E., & Bowen, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.10133 · Cited by 16
Position Papers for the ASCR Workshop on Basic Research Needs in Quantum Computing and Networking
Lougovski, P., Parekh, O., Broz, J., Byrd, M., Chembo, Y. K., de Jong, W. A., Figueroa, E. V., Humble, T. S., Larson, J. M., Quiroz, G., et al. (2023) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/2283320 · Cited by 11
Solving systems of Boolean multivariate equations with quantum annealing
Ramos-Calderer, S., Bravo-Prieto, C., Lin, R., Bellini, E., Manzano, M., Aaraj, N., & Latorre, J. I. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.013096 · Cited by 12
“The so-called adiabatic quantum computation model was shown to be polynomially equivalent to the quantum gate-based model proposed by Deutsch in 1989 [30, 31], and is one of the most promising models of quantum computing due to its natural robustness against errors [32].”
BackgroundMethodSpeedup of the quantum adiabatic algorithm using delocalization catalysis
Cao, C., Xue, J. Y., Shannon, N., & Joynt, R. (2021) · Institutional Repositories DataBase (IRDB) · Cited by 9
General Conditions for Universality of Quantum Hamiltonians
Kohler, T., Piddock, S., Bausch, J., & Cubitt, T. S. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010308 · Cited by 14
Quantum Algorithms for the Physical Layer: Potential Applications to Physical Layer Security
Matsumine, T., Ochiai, H., & Shikata, J. (2025) · IEEE Access · doi:10.1109/access.2025.3528443 · Cited by 13
“In principle, it has been demonstrated that AQC is polynomially equivalent to gate-based universal quantum computing, since any quantum circuit can be represented as a time-dependent Hamiltonian with at most polynomial overhead [36].”
Counterdiabatic Driving with Performance Guarantees
Finžgar, J. R., Notarnicola, S., Cain, M., Lukin, M. D., & Sels, D. (2025) · Physical Review Letters · doi:10.1103/pqhl-nbtk · Cited by 29
Quantum Social Computing Approaches for Influence Maximization
Dinh, T. N., Nguyen, A. N., Nguyen, U., & Nguyen, V. G. (2022) · Globecom · doi:10.1109/globecom48099.2022.10000698 · Cited by 9
“AQC has been shown to be equivalent to gate-based QC with at most polynomial overhead [23].”
A quantum computing concept for 1-D elastic wave simulation with exponential speedup
Schade, M., Bösch, C., Hapla, V., & Fichtner, A. (2024) · Geophysical Journal International · doi:10.1093/gji/ggae160 · Cited by 22
“It should be noted that there is controversy about whether or not QA can achieve the same speedup as gate-based quantum computation in real-world contexts (Van Dam et al. (2001); Aharonov et al. (2008); Albash and Lidar (2018b); Villanueva et al. (2023)).”
BackgroundNoisy, Intermediate-Scale Quantum Computing and Industrial Revolution 4.0
Senekane, M., Maseli, M., & Taele, B. M. (2020) · Lecture notes in electrical engineering · doi:10.1007/978-3-030-48230-5_9 · Cited by 9
Realizing an adiabatic quantum search algorithm with shortcuts to adiabaticity in an ion-trap system
Zhang, J., Li, F., Xie, Y., Wu, C.-W., Ou, B.-Q., Wu, W., & Chen, P. (2018) · Physical Review A · doi:10.1103/physreva.98.052323 · Cited by 8
Constant-Round Blind Classical Verification of Quantum Sampling
Chung, K.-M., Lee, Y., Lin, H.-H., & Wu, X. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-07082-2_25 · Cited by 13
High fidelity readout and protection of a 43Ca+ trapped ion qubit
Szwer, D. J. (2009) · Oxford University Research Archive (ORA) (University of Oxford) · doi:10.5287/ora-jxk0zobg5 · Cited by 18
QUBO formulation for the contact map overlap problem
de Oliveira, N. M., Silva, R. M. D. A., & de Oliveira, W. R. (2018) · International Journal of Quantum Information · doi:10.1142/s0219749918400075 · Cited by 7
Targeting Classical Code to a Quantum Annealer
Pakin, S. (2019) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3297858.3304071 · Cited by 8
“task: given values of x 1 , x 2 , and x 3 , return the value of x 10 (For readers not familiar with Verilog, one can think of a wire variables, x[1] through x[10] .) and run it on a quantum annealer with y (= x[10] ) pinned to True , the hardware returns a (= x[1] ) and b (= x[2] ) True and c (=…”
BackgroundQuantum advantage from energy measurements of many-body quantum systems
Novo, L., Bermejo-Vega, J., & García−Patrón, R. (2021) · Quantum · doi:10.22331/q-2021-06-02-465 · Cited by 25
“In fact, the Hamiltonian that has the properties we require is used in the proof that the adiabatic model of quantum computation is equivalent to the circuit model [78].”
BackgroundMethodInfluentialNoise-tolerant quantum speedups in quantum annealing without fine tuning
Kapit, E., & Oganesyan, V. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/abd59a · Cited by 9
tqix.pis: A toolbox for quantum dynamics simulation of spin ensembles in Dicke basis
Viet, N. T., Chuong, N. T., Huyen, V. T. N., & Ho, L. B. (2023) · Computer Physics Communications · doi:10.1016/j.cpc.2023.108686 · Cited by 8
Quantum Computing Approaches for Vector Quantization—Current Perspectives and Developments
Engelsberger, A., & Villmann, T. (2023) · Entropy · doi:10.3390/e25030540 · Cited by 10
“It can be shown that both paradigms are computationally equivalent [65].”
BackgroundSparse Random Hamiltonians Are Quantumly Easy
Chen, C.-F., Dalzell, A. M., Berta, M., Brandão, F. G. S. L., & Tropp, J. A. (2024) · Physical Review X · doi:10.1103/physrevx.14.011014 · Cited by 25
Adiabatic Times for Markov Chains and Applications
Bradford, K., & Kovchegov, Y. (2011) · Journal of Statistical Physics · doi:10.1007/s10955-011-0219-6 · Cited by 7
“Now we extend the notion of adiabatic dynamics for the continuous-time Markov generators as follows.”
BackgroundBringewatt, J., & Jarret, M. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.170504 · Cited by 8
Quantum walk on a graph of spins: Magnetism and entanglement
Sellapillay, K., & Verga, A. (2021) · Physical review. E · doi:10.1103/physreve.103.032123 · Cited by 9
Quantum Computing with Octonions
Freedman, M. H., Zini, M. S., & Wang, Z. (2019) · Peking Mathematical Journal · doi:10.1007/s42543-019-00020-3 · Cited by 7
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.