{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T23:14:18Z","timestamp":1782342858608,"version":"3.54.5"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,3,14]],"date-time":"2010-03-14T00:00:00Z","timestamp":1268524800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s11128-010-0168-z","type":"journal-article","created":{"date-parts":[[2010,3,13]],"date-time":"2010-03-13T05:53:01Z","timestamp":1268459581000},"page":"33-52","source":"Crossref","is-referenced-by-count":88,"title":["A study of heuristic guesses for adiabatic quantum computation"],"prefix":"10.1007","volume":"10","author":[{"given":"Alejandro","family":"Perdomo-Ortiz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Salvador E.","family":"Venegas-Andraca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Al\u00e1n","family":"Aspuru-Guzik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,3,14]]},"reference":[{"key":"168_CR1","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution, quant-ph\/0001106 (2000)"},{"key":"168_CR2","doi-asserted-by":"crossref","first-page":"012322","DOI":"10.1103\/PhysRevA.65.012322","volume":"65","author":"A.M. Childs","year":"2001","unstructured":"Childs A.M., Farhi E., Preskill J.: Robustness of adiabatic quantum computation. Phys. Rev. A 65, 012322 (2001)","journal-title":"Phys. Rev. A"},{"key":"168_CR3","doi-asserted-by":"crossref","first-page":"160506","DOI":"10.1103\/PhysRevLett.100.160506","volume":"100","author":"D.A. Lidar","year":"2008","unstructured":"Lidar D.A.: Towards fault tolerant adiabatic quantum computation. Phys. Rev. Lett. 100, 160506 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR4","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1126\/science.1057726","volume":"292","author":"E. Farhi","year":"2001","unstructured":"Farhi E., Goldstone J., Gutmann S., Lapan J., Lundgren A., Preda D.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472\u2013475 (2001)","journal-title":"Science"},{"key":"168_CR5","doi-asserted-by":"crossref","first-page":"022314","DOI":"10.1103\/PhysRevA.67.022314","volume":"67","author":"T. Hogg","year":"2003","unstructured":"Hogg T.: Adiabatic quantum computing for random satisfiability problems. Phys. Rev. A 67, 022314 (2003)","journal-title":"Phys. Rev. A"},{"key":"168_CR6","doi-asserted-by":"crossref","first-page":"170503","DOI":"10.1103\/PhysRevLett.101.170503","volume":"101","author":"A.P. Young","year":"2008","unstructured":"Young A.P., Knysh S., Smelyanskiy V.N.: Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Phys. Rev. Lett. 101, 170503 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR7","doi-asserted-by":"crossref","first-page":"012320","DOI":"10.1103\/PhysRevA.78.012320","volume":"78","author":"A. Perdomo","year":"2008","unstructured":"Perdomo A., Truncik C., Tubert-Brohman I., Rose G., Aspuru-Guzik A.: Construction of model Hamiltonians for adiabatic quantum computation and its application to finding low-energy conformations of lattice protein models. Phys. Rev. A 78, 012320 (2008)","journal-title":"Phys. Rev. A"},{"key":"168_CR8","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: Quantum adiabatic evolution algorithms with different paths, quant-ph\/0208135 (2002)"},{"key":"168_CR9","doi-asserted-by":"crossref","first-page":"080502","DOI":"10.1103\/PhysRevLett.103.080502","volume":"103","author":"A.T. Rezakhani","year":"2009","unstructured":"Rezakhani A.T., Kuo W., Hamma A., Lidar D.A., Zanardi P.: Quantum adiabatic brachistochrone. Phys. Rev. Lett. 103, 080502 (2009)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR10","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1142\/S021974990800358X","volume":"06","author":"E. Farhi","year":"2008","unstructured":"Farhi E., Goldstone J., Gutmann S., Nagaj D.: How to make the quantum adiabatic algorithm fail. Int. J. Quantum Inf. 06, 503\u2013516 (2008)","journal-title":"Int. J. Quantum Inf."},{"key":"168_CR11","doi-asserted-by":"crossref","first-page":"042308","DOI":"10.1103\/PhysRevA.65.042308","volume":"65","author":"J. Roland","year":"2002","unstructured":"Roland J., Cerf N.J.: Quantum search by local adiabatic evolution. Phys. Rev. A 65, 042308 (2002)","journal-title":"Phys. Rev. A"},{"key":"168_CR12","doi-asserted-by":"crossref","first-page":"022329","DOI":"10.1103\/PhysRevA.73.022329","volume":"73","author":"M. Znidaric","year":"2006","unstructured":"Znidaric M., Horvat M.: Exponential complexity of an adiabatic algorithm for an NP-complete problem. Phys. Rev. A 73, 022329 (2006)","journal-title":"Phys. Rev. A"},{"key":"168_CR13","doi-asserted-by":"crossref","first-page":"130503","DOI":"10.1103\/PhysRevLett.100.130503","volume":"100","author":"M.H.S. Amin","year":"2008","unstructured":"Amin M.H.S.: Effect of local minima on adiabatic quantum optimization. Phys. Rev. Lett. 100, 130503 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR14","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey M., Johnson D.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"168_CR15","volume-title":"Introduction to the Theory of Computation","author":"M. Sipser","year":"2005","unstructured":"Sipser M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (2005)"},{"key":"168_CR16","doi-asserted-by":"crossref","first-page":"2473","DOI":"10.1103\/PhysRevLett.80.2473","volume":"80","author":"T. Hogg","year":"1998","unstructured":"Hogg T.: Highly structured searches with quantum computers. Phys. Rev. Lett. 80, 2473 (1998)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR17","doi-asserted-by":"crossref","first-page":"052311","DOI":"10.1103\/PhysRevA.61.052311","volume":"61","author":"T. Hogg","year":"2000","unstructured":"Hogg T.: Quantum search heuristics. Phys. Rev. A 61, 052311 (2000)","journal-title":"Phys. Rev. A"},{"key":"168_CR18","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"L.K. Grover","year":"1997","unstructured":"Grover L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325 (1997)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR19","doi-asserted-by":"crossref","first-page":"1704","DOI":"10.1126\/science.1113479","volume":"309","author":"A. Aspuru-Guzik","year":"2005","unstructured":"Aspuru-Guzik A., Dutoi A.D., Love P.J., Head-Gordon M.: Simulated quantum computation of molecular energies. Science 309, 1704\u20131707 (2005)","journal-title":"Science"},{"key":"168_CR20","doi-asserted-by":"crossref","first-page":"194105","DOI":"10.1063\/1.3115177","volume":"130","author":"N.J. Ward","year":"2009","unstructured":"Ward N.J., Kassal I., Aspuru-Guzik A.: Preparation of many-body states for quantum simulation. J. Chem. Phys. 130, 194105 (2009)","journal-title":"J. Chem. Phys."},{"key":"168_CR21","doi-asserted-by":"crossref","first-page":"5388","DOI":"10.1039\/b804804e","volume":"10","author":"H. Wang","year":"2008","unstructured":"Wang H., Kais S., Aspuru-Guzik A., Hoffmann M.R.: Quantum algorithm for obtaining the energy spectrum of molecular systems. Phys. Chem. Chem. Phys. 10, 5388\u20135393 (2008)","journal-title":"Phys. Chem. Chem. Phys."},{"key":"168_CR22","doi-asserted-by":"crossref","first-page":"042335","DOI":"10.1103\/PhysRevA.79.042335","volume":"79","author":"H. Wang","year":"2009","unstructured":"Wang H., Ashhab S., Nori F.: Efficient quantum algorithm for preparing molecular-system-like states on a quantum computer. Phys. Rev. A 79, 042335 (2009)","journal-title":"Phys. Rev. A"},{"key":"168_CR23","doi-asserted-by":"crossref","first-page":"3168","DOI":"10.1063\/1.464089","volume":"98","author":"D. Kohen","year":"1993","unstructured":"Kohen D., Tannor D.J.: Quantum adiabatic switching. J. Chem. Phys. 98, 3168 (1993)","journal-title":"J. Chem. Phys."},{"key":"168_CR24","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical zero knowledge, In: Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, pp. 20\u201329. San Diego, CA, USA, ACM (2003)","DOI":"10.1145\/780542.780546"},{"key":"168_CR25","volume-title":"Quantum Mechanics (Physics)","author":"A. Messiah","year":"1999","unstructured":"Messiah A.: Quantum Mechanics (Physics). Dover Publications, Mineola (1999)"},{"key":"168_CR26","doi-asserted-by":"crossref","first-page":"160408","DOI":"10.1103\/PhysRevLett.93.160408","volume":"93","author":"K. Marzlin","year":"2004","unstructured":"Marzlin K., Sanders B.C.: Inconsistency in the application of the adiabatic theorem. Phys. Rev. Lett. 93, 160408 (2004)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR27","doi-asserted-by":"crossref","first-page":"150402","DOI":"10.1103\/PhysRevLett.98.150402","volume":"98","author":"D.M. Tong","year":"2007","unstructured":"Tong D.M., Singh K., Kwek L.C., Oh C.H.: Sufficiency criterion for the validity of the adiabatic approximation. Phys. Rev. Lett. 98, 150402 (2007)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR28","doi-asserted-by":"crossref","first-page":"024304","DOI":"10.1103\/PhysRevA.76.024304","volume":"76","author":"Z. Wei","year":"2007","unstructured":"Wei Z., Ying M.: Quantum adiabatic computation and adiabatic conditions. Phys. Rev. A 76, 024304 (2007)","journal-title":"Phys. Rev. A"},{"key":"168_CR29","doi-asserted-by":"crossref","first-page":"032109","DOI":"10.1103\/PhysRevA.77.032109","volume":"77","author":"Y. Zhao","year":"2008","unstructured":"Zhao Y.: Reexamination of the quantum adiabatic theorem. Phys. Rev. A 77, 032109 (2008)","journal-title":"Phys. Rev. A"},{"key":"168_CR30","doi-asserted-by":"crossref","first-page":"220401","DOI":"10.1103\/PhysRevLett.102.220401","volume":"102","author":"M.H.S. Amin","year":"2009","unstructured":"Amin M.H.S.: Consistency of the adiabatic theorem. Phys. Rev. Lett. 102, 220401 (2009)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR31","doi-asserted-by":"crossref","first-page":"044102","DOI":"10.1103\/PhysRevA.76.044102","volume":"76","author":"R. MacKenzie","year":"2007","unstructured":"MacKenzie R., Morin-Duchesne A., Paquette H., Pinel J.: Validity of the adiabatic approximation in quantum mechanics. Phys. Rev. A 76, 044102 (2007)","journal-title":"Phys. Rev. A"},{"key":"168_CR32","unstructured":"Ambainis, A., Regev, O.: An elementary proof of the quantum adiabatic theorem, quant-ph\/0411152s (2004)"},{"key":"168_CR33","doi-asserted-by":"crossref","first-page":"102111","DOI":"10.1063\/1.2798382","volume":"48","author":"S. Jansen","year":"2007","unstructured":"Jansen S., Ruskai M., Seiler R.: Bounds for the adiabatic approximation with applications to quantum computation. J. Math. Phys. 48, 102111 (2007)","journal-title":"J. Math. Phys."},{"key":"168_CR34","unstructured":"Da Wu, J., Sheng Z.M., Lan C.J., De Zhang, Y.: Adiabatic approximation condition, arXiv:0706.0264v2 (2007)"},{"key":"168_CR35","unstructured":"Chen, J.-L., Sheng Z.M., Da Wu, J., De Zhang, Y.: Invariant perturbation theory of adiabatic process, http:\/\/arxiv.org\/abs\/0706.0299 (2007)"},{"key":"168_CR36","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1023\/B:IJTP.0000048589.20608.aa","volume":"43","author":"M. Andrecut","year":"2004","unstructured":"Andrecut M., Ali M.K.: Unstructured adiabatic quantum search. Int. J. Theor. Phys. 43, 925\u2013931 (2004)","journal-title":"Int. J. Theor. Phys."},{"key":"168_CR37","doi-asserted-by":"crossref","first-page":"062337","DOI":"10.1103\/PhysRevA.75.062337","volume":"75","author":"M.S. Siu","year":"2007","unstructured":"Siu M.S.: Adiabatic rotation, quantum search, and preparation of superposition states. Phys. Rev. A 75, 062337 (2007)","journal-title":"Phys. Rev. A"},{"key":"168_CR38","doi-asserted-by":"crossref","first-page":"33","DOI":"10.3233\/SAT190037","volume":"4","author":"S. Acharyya","year":"2007","unstructured":"Acharyya S.: SAT algorithms for colouring some special classes of graphs: some theoretical and experimental results. J. Satisfiability, Boolean Model. Comput. 4, 33\u201335 (2007)","journal-title":"J. Satisfiability, Boolean Model. Comput."},{"key":"168_CR39","unstructured":"Gent, I., Walsh, T.: The search for satisfaction, Internal report, department of computer science, University of Strathclyde (1999)"},{"key":"168_CR40","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M. Mezard","year":"2002","unstructured":"Mezard M., Parisi G., Zecchina R.: Analytic and algorithmic solution of random satisfiability problems. Science 297, 812\u2013815 (2002)","journal-title":"Science"},{"key":"168_CR41","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1038\/nature03602","volume":"435","author":"D. Achlioptas","year":"2005","unstructured":"Achlioptas D., Naor A., Peres Y.: Rigorous location of phase transitions in hard optimization problems. Nature 435, 759\u2013764 (2005)","journal-title":"Nature"},{"key":"168_CR42","doi-asserted-by":"crossref","first-page":"197205","DOI":"10.1103\/PhysRevLett.94.197205","volume":"94","author":"M. Mezard","year":"2005","unstructured":"Mezard M., Mora T., Zecchina R.: Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett. 94, 197205 (2005)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR43","unstructured":"Watanabe research group of Department of Mathematics and Computing Sciences, Tokyo Institute of Technology, http:\/\/www.is.titech.ac.jp\/~watanabe\/gensat\/"},{"key":"168_CR44","unstructured":"Farhi, E., Goldstone, J., Gosset, D., Gutmann, S., Meyer, H., Shor, P.: Quantum adiabatic algorithms, small gaps, and different paths, arxiv.org\/abs\/0909.4766 (2009)"},{"key":"168_CR45","doi-asserted-by":"crossref","first-page":"062305","DOI":"10.1103\/PhysRevA.71.062305","volume":"71","author":"M. \u017dnidaric","year":"2005","unstructured":"\u017dnidaric M.: Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability. Phys. Rev. A 71, 062305 (2005)","journal-title":"Phys. Rev. A"},{"key":"168_CR46","doi-asserted-by":"crossref","first-page":"060403","DOI":"10.1103\/PhysRevLett.101.060403","volume":"101","author":"J. Du","year":"2008","unstructured":"Du J., Hu L., Wang Y., Wu J., Zhao M., Suter D.: Experimental study of the validity of quantitative conditions in the quantum adiabatic theorem. Phys. Rev. Lett. 101, 060403 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR47","doi-asserted-by":"crossref","first-page":"1514","DOI":"10.1016\/j.dam.2006.10.004","volume":"155","author":"H. Kautz","year":"2007","unstructured":"Kautz H., Selman B.: The state of SAT. Discrete Appl. Math. 155, 1514\u20131524 (2007)","journal-title":"Discrete Appl. Math."},{"key":"168_CR48","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: Quantum adiabatic evolution algorithms with different paths, quant-ph\/0208135 (2002)"},{"key":"168_CR49","doi-asserted-by":"crossref","first-page":"1070","DOI":"10.1137\/S0097539704445226","volume":"35","author":"J. Kempe","year":"2006","unstructured":"Kempe J., Kitaev A., Regev O.: The complexity of the local Hamiltonian problem. SIAM J. Comput. 35, 1070\u20131097 (2006)","journal-title":"SIAM J. Comput."},{"key":"168_CR50","unstructured":"Bravyi, S.: Efficient algorithm for a quantum analogue of 2-SAT, quant-ph\/0602108 (2006)"},{"key":"168_CR51","first-page":"0900","volume":"8","author":"R. Oliveira","year":"2008","unstructured":"Oliveira R., Terhal B.M.: The complexity of quantum system on a two-dimensional square lattice. Quantum Inf. Comput. 8, 0900\u20130924 (2008)","journal-title":"Quantum Inf. Comput."},{"key":"168_CR52","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1137\/060648829","volume":"37","author":"D. Aharonov","year":"2007","unstructured":"Aharonov D., Ta-Shma A.: Adiabatic quantum state generation. SIAM J. Comput. 37, 47\u201382 (2007)","journal-title":"SIAM J. Comput."},{"key":"168_CR53","doi-asserted-by":"crossref","first-page":"070502","DOI":"10.1103\/PhysRevLett.99.070502","volume":"99","author":"A. Mizel","year":"2007","unstructured":"Mizel A., Lidar D.A., Mitchell M.: Simple proof of equivalence between adiabatic quantum computation and the circuit model. Phys. Rev. Lett. 99, 070502 (2007)","journal-title":"Phys. Rev. Lett."},{"key":"168_CR54","doi-asserted-by":"crossref","first-page":"060304","DOI":"10.1103\/PhysRevA.74.060304","volume":"74","author":"R. Schutzhold","year":"2006","unstructured":"Schutzhold R., Schaller G.: Adiabatic quantum algorithms as quantum phase transitions: first versus second order. Phys. Rev. A 74, 060304 (2006)","journal-title":"Phys. Rev. A"},{"key":"168_CR55","doi-asserted-by":"crossref","first-page":"062302","DOI":"10.1103\/PhysRevA.69.062302","volume":"69","author":"J. Latorre","year":"2004","unstructured":"Latorre J., Orus R.: Adiabatic quantum computation and quantum phase transitions. Phys. Rev. A 69, 062302 (2004)","journal-title":"Phys. Rev. A"},{"key":"168_CR56","doi-asserted-by":"crossref","first-page":"052308","DOI":"10.1103\/PhysRevA.69.052308","volume":"69","author":"R. Orus","year":"2004","unstructured":"Orus R., Latorre J.I.: Universality of entanglement and quantum-computation complexity. Phys. Rev. A 69, 052308 (2004)","journal-title":"Phys. Rev. A"},{"key":"168_CR57","doi-asserted-by":"crossref","unstructured":"Young, A.P., Knysh, S., Smelyanskiy, V.N.: First-order phase transition in the quantum adiabatic algorithm. Phys. Rev. Lett. 104 (2010)","DOI":"10.1103\/PhysRevLett.104.020502"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-010-0168-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-010-0168-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-010-0168-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T00:51:10Z","timestamp":1591145470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-010-0168-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,14]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["168"],"URL":"https:\/\/doi.org\/10.1007\/s11128-010-0168-z","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,14]]}}}