{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T13:26:59Z","timestamp":1781270819382,"version":"3.54.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,4,9]],"date-time":"2017-04-09T00:00:00Z","timestamp":1491696000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s11128-017-1586-y","type":"journal-article","created":{"date-parts":[[2017,4,9]],"date-time":"2017-04-09T03:24:36Z","timestamp":1491708276000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":42,"title":["Enhancing quantum annealing performance for the molecular similarity problem"],"prefix":"10.1007","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1869-8243","authenticated-orcid":false,"given":"Maritza","family":"Hernandez","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maliheh","family":"Aramon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,4,9]]},"reference":[{"key":"1586_CR1","doi-asserted-by":"publisher","unstructured":"Abu-Khzam, F.N., Samatova, N.F., Rizk, M.A., Langston, M.A.: The maximum common subgraph problem: faster solutions via vertex cover. In: IEEE\/ACS International Conference on Computer Systems and Applications, pp. 367\u2013373 (2007)","DOI":"10.1109\/AICCSA.2007.370907"},{"key":"1586_CR2","doi-asserted-by":"publisher","first-page":"052,323","DOI":"10.1103\/PhysRevA.92.052323","volume":"92","author":"MH Amin","year":"2015","unstructured":"Amin, M.H.: Searching for quantum speedup in quasistatic quantum annealers. Phys. Rev. A 92, 052,323 (2015)","journal-title":"Phys. Rev. A"},{"key":"1586_CR3","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/opre.1100.0851","volume":"59","author":"B Balasundaram","year":"2011","unstructured":"Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: the maximum $$k$$ k -plex problem. Oper. Res. 59, 133\u2013142 (2011)","journal-title":"Oper. Res."},{"key":"1586_CR4","doi-asserted-by":"publisher","first-page":"1559","DOI":"10.1007\/978-1-4419-7997-1_9","volume-title":"Handbook of Combinatorial Optimization","author":"B Balasundaram","year":"2013","unstructured":"Balasundaram, B., Mahdavi Pajouh, F.: Graph theoretic clique relaxations and applications. In: Pardalos, P.M., Du, D.Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 1559\u20131598. Springer, New York (2013)"},{"key":"1586_CR5","doi-asserted-by":"crossref","unstructured":"Baum, D.: A point-based algorithm for multiple 3D surface alignment of drug-sized molecules. Ph.D. thesis, Free University of Berlin (2007)","DOI":"10.1007\/11875741_18"},{"key":"1586_CR6","doi-asserted-by":"crossref","unstructured":"Bian, Z., Chudak, F., Israel, R., Lackey, B., Macready, W.G., Roy, A.: Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. arXiv preprint arXiv:1603.03111 (2016)","DOI":"10.3389\/fict.2016.00014"},{"key":"1586_CR7","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1038\/nphys2900","volume":"10","author":"S Boixo","year":"2014","unstructured":"Boixo, S., Ronnow, T.F., Isakov, S.V., Wang, Z., Wecker, D., Lidar, D.A., Martinis, J.M., Troyer, M.: Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10, 218\u2013224 (2014)","journal-title":"Nat. Phys."},{"key":"1586_CR8","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms10327","author":"S Boixo","year":"2016","unstructured":"Boixo, S., Smelyanskiy, V.N., Shabani, A., Isakov, S.V., Dykman, M., Denchev, V.S., Amin, M.H., Smirnov, A.Y., Mohseni, M., Neven, H.: Computational multiqubit tunnelling in programmable quantum annealers. Nat. Commun. (2016). doi: 10.1038\/ncomms10327","journal-title":"Nat. Commun."},{"key":"1586_CR9","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s11128-015-1150-6","volume":"15","author":"T Boothby","year":"2016","unstructured":"Boothby, T., King, A.D., Roy, A.: Fast clique minor generation in chimera qubit connectivity graphs. Quantum Inf. Process 15, 495\u2013508 (2016)","journal-title":"Quantum Inf. Process"},{"key":"1586_CR10","unstructured":"Boros, E., Gruber, A.: On quadratization of pseudo-Boolean functions. In: International Symposium on Artificial Intelligence and Mathematics (2012)"},{"key":"1586_CR11","unstructured":"Cai, J., Macready, W.G., Roy, A.: A practical heuristic for finding graph minors. arXiv preprint arXiv:1406.2741 (2014)"},{"key":"1586_CR12","doi-asserted-by":"publisher","first-page":"5468","DOI":"10.1103\/PhysRevLett.85.5468","volume":"85","author":"DS Callaway","year":"2000","unstructured":"Callaway, D.S., Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Network robustness and fragility: percolation on random graphs. Phys. Rev. Lett. 85, 5468\u20135471 (2000)","journal-title":"Phys. Rev. Lett."},{"key":"1586_CR13","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s11128-008-0082-9","volume":"7","author":"V Choi","year":"2008","unstructured":"Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193\u2013209 (2008)","journal-title":"Quantum Inf. Process."},{"key":"1586_CR14","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s11128-010-0200-3","volume":"10","author":"V Choi","year":"2011","unstructured":"Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10, 343\u2013353 (2011)","journal-title":"Quantum Inf. Process."},{"key":"1586_CR15","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0378-3758(94)90153-8","volume":"41","author":"BS Clarke","year":"1994","unstructured":"Clarke, B.S., Barron, A.R.: Jeffreys\u2019 prior is asymptotically least favorable under entropy risk. J. Stat. Plan. Inference 41, 37\u201360 (1994)","journal-title":"J. Stat. Plan. Inference"},{"key":"1586_CR16","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1103\/RevModPhys.80.1061","volume":"80","author":"A Das","year":"2008","unstructured":"Das, A., Chakrabarti, B.K.: Colloquium: quantum annealing and analog quantum computation. Rev. Mod. Phys. 80, 1061\u20131081 (2008)","journal-title":"Rev. Mod. Phys."},{"key":"1586_CR17","first-page":"031,015","volume":"6","author":"VS Denchev","year":"2016","unstructured":"Denchev, V.S., Boixo, S., Isakov, S.V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., Neven, H.: What is the computational value of finite-range tunneling? Phys. Rev. X 6, 031,015 (2016)","journal-title":"Phys. Rev. X"},{"key":"1586_CR18","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for $$w[1]$$ w [ 1 ] . Theor. Comput. Sci 141, 109\u2013131 (1995)","journal-title":"Theor. Comput. Sci"},{"key":"1586_CR19","doi-asserted-by":"publisher","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":"1586_CR20","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"1586_CR21","doi-asserted-by":"publisher","first-page":"R393","DOI":"10.1088\/0305-4470\/39\/36\/R01","volume":"39","author":"ES Giuseppe","year":"2006","unstructured":"Giuseppe, E.S., Erio, T.: Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A Math. Gen. 39, R393 (2006)","journal-title":"J. Phys. A Math. Gen."},{"key":"1586_CR22","unstructured":"Hamze, F., Freitas, N.d.: From fields to trees. In: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, pp. 243\u2013250 (2004)"},{"key":"1586_CR23","doi-asserted-by":"publisher","first-page":"042,325","DOI":"10.1103\/PhysRevA.92.042325","volume":"92","author":"I Hen","year":"2015","unstructured":"Hen, I., Job, J., Albash, T., R\u00f8nnow, T.F., Troyer, M., Lidar, D.A.: Probing for quantum speedup in spin-glass problems with planted solutions. Phys. Rev. A 92, 042,325 (2015)","journal-title":"Phys. Rev. A"},{"key":"1586_CR24","unstructured":"Hernandez, M., Zaribafiyan, A., Aramon, M., Naghibi, M.: A novel graph-based approach for determining molecular similarity. arXiv preprint arXiv:1601.06693 (2016)"},{"key":"1586_CR25","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1038\/nature10012","volume":"473","author":"MW Johnson","year":"2011","unstructured":"Johnson, M.W., Amin, M.H.S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A.J., Johansson, J., Bunyk, P., Chapple, E.M., Enderud, C., Hilton, J.P., Karimi, K., Ladizinsky, E., Ladizinsky, N., Oh, T., Perminov, I., Rich, C., Thom, M.C., Tolkacheva, E., Truncik, C.J.S., Uchaikin, S., Wang, J., Wilson, B., Rose, G.: Quantum annealing with manufactured spins. Nature 473, 194\u2013198 (2011)","journal-title":"Nature"},{"key":"1586_CR26","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355\u20135363 (1998)","journal-title":"Phys. Rev. E"},{"key":"1586_CR27","first-page":"031,026","volume":"5","author":"HG Katzgraber","year":"2015","unstructured":"Katzgraber, H.G., Hamze, F., Zhu, Z., Ochoa, A.J., Munoz-Bauza, H.: Seeking quantum speedup through spin glasses: the good, the bad, and the ugly. Phys. Rev. X 5, 031,026 (2015)","journal-title":"Phys. Rev. X"},{"key":"1586_CR28","unstructured":"King, A.D., McGeoch, C.C.: Algorithm engineering for a quantum annealing platform. arXiv preprint arXiv:1410.2628 (2014)"},{"key":"1586_CR29","first-page":"021,041","volume":"4","author":"T Lanting","year":"2014","unstructured":"Lanting, T., Przybysz, A.J., Smirnov, A.Y., Spedalieri, F.M., Amin, M.H., Berkley, A.J., Harris, R., Altomare, F., Boixo, S., Bunyk, P., Dickson, N., Enderud, C., Hilton, J.P., Hoskinson, E., Johnson, M.W., Ladizinsky, E., Ladizinsky, N., Neufeld, R., Oh, T., Perminov, I., Rich, C., Thom, M.C., Tolkacheva, E., Uchaikin, S., Wilson, A.B., Rose, G.: Entanglement in a quantum annealing processor. Phys. Rev. X 4, 021,041 (2014)","journal-title":"Phys. Rev. X"},{"key":"1586_CR30","doi-asserted-by":"crossref","unstructured":"Mandr\u00e0, S., Zhu, Z., Wang, W., Perdomo-Ortiz, A., Katzgraber, H.G.: Strengths and weaknesses of weak-strong cluster problems: a detailed overview of state-of-the-art classical heuristics vs quantum approaches. arXiv preprint arXiv:1604.01746 (2016)","DOI":"10.1103\/PhysRevA.94.022337"},{"key":"1586_CR31","doi-asserted-by":"publisher","first-page":"026,118","DOI":"10.1103\/PhysRevE.64.026118","volume":"64","author":"MEJ Newman","year":"2001","unstructured":"Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E. 64, 026,118 (2001)","journal-title":"Phys. Rev. E."},{"key":"1586_CR32","unstructured":"Perdomo-Ortiz, A., Fluegemann, J., Biswas, R., Smelyanskiy, V.N.: A performance estimator for quantum annealers: gauge selection and parameter setting. arXiv preprint arXiv:1503.01083 (2015)"},{"key":"1586_CR33","doi-asserted-by":"publisher","DOI":"10.1038\/srep18628","author":"A Perdomo-Ortiz","year":"2016","unstructured":"Perdomo-Ortiz, A., O\u2019Gorman, B., Fluegemann, J., Biswas, R., Smelyanskiy, V.N.: Determination and correction of persistent biases in quantum annealers. Sci. Rep. (2016). doi: 10.1038\/srep18628","journal-title":"Sci. Rep."},{"issue":"15","key":"1586_CR34","doi-asserted-by":"publisher","first-page":"2883","DOI":"10.1021\/jp984735q","volume":"103","author":"PLA Popelier","year":"1999","unstructured":"Popelier, P.L.A.: Quantum molecular similarity. 1. BCP space. J. Phys. Chem. A 103(15), 2883\u20132890 (1999)","journal-title":"J. Phys. Chem. A"},{"key":"1586_CR35","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms4243","author":"KL Pudenz","year":"2014","unstructured":"Pudenz, K.L., Albash, T., Lidar, D.A.: Error-corrected quantum annealing with hundreds of qubits. Nat. Commun. (2014). doi: 10.1038\/ncomms4243","journal-title":"Nat. Commun."},{"issue":"5","key":"1586_CR36","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1023\/A:1008068904628","volume":"12","author":"M Rarey","year":"1998","unstructured":"Rarey, M., Dixon, J.S.: Feature trees: a new molecular similarity measure based on tree matching. J. Comput. Aided Mol. Des. 12(5), 471\u2013490 (1998)","journal-title":"J. Comput. Aided Mol. Des."},{"key":"1586_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11128-014-0892-x","volume":"14","author":"EG Rieffel","year":"2015","unstructured":"Rieffel, E.G., Venturelli, D., O\u2019Gorman, B., Do, M.B., Prystay, E.M., Smelyanskiy, V.N.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14, 1\u201336 (2015)","journal-title":"Quantum Inf. Process."},{"key":"1586_CR38","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1126\/science.1252319","volume":"345","author":"TF R\u00f8nnow","year":"2014","unstructured":"R\u00f8nnow, T.F., Wang, Z., Job, J., Boixo, S., Isakov, S.V., Wecker, D., Martinis, J.M., Lidar, D.A., Troyer, M.: Defining and detecting quantum speedup. Science 345, 420\u2013424 (2014)","journal-title":"Science"},{"key":"1586_CR39","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1109\/JSTSP.2016.2574703","volume":"10","author":"G Rosenberg","year":"2016","unstructured":"Rosenberg, G., Haghnegahdar, P., Goddard, P., Carr, P., Wu, J., de Prado, M.: Solving the optimal trading trajectory problem using a quantum annealer. IEEE J. Sel. Top. Signal Process. 10, 1053\u20131060 (2016)","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"1586_CR40","unstructured":"Selby, A.: Efficient subgraph-based sampling of Ising-type models with frustration. arXiv preprint arXiv:1409.3934 (2014)"},{"key":"1586_CR41","first-page":"031,040","volume":"5","author":"D Venturelli","year":"2015","unstructured":"Venturelli, D., Mandr\u00e0, S., Knysh, S., O\u2019Gorman, B., Biswas, R., Smelyanskiy, V.: Quantum optimization of fully connected spin glasses. Phys. Rev. X 5, 031,040 (2015)","journal-title":"Phys. Rev. X"},{"key":"1586_CR42","unstructured":"Venturelli, D., Marchand, D.J.J., Rojo, G.: Quantum annealing implementation of job-shop scheduling. arXiv preprint arXiv:1506.08479 (2015)"},{"key":"1586_CR43","doi-asserted-by":"publisher","first-page":"042,310","DOI":"10.1103\/PhysRevA.92.042310","volume":"92","author":"W Vinci","year":"2015","unstructured":"Vinci, W., Albash, T., Paz-Silva, G., Hen, I., Lidar, D.A.: Quantum annealing correction with minor embedding. Phys. Rev. A 92, 042,310 (2015)","journal-title":"Phys. Rev. A"},{"key":"1586_CR44","doi-asserted-by":"publisher","first-page":"2840","DOI":"10.1021\/ci300400a","volume":"52","author":"C Xu","year":"2012","unstructured":"Xu, C., Cheng, F., Chen, L., Du, Z., Li, W., Liu, G., Lee, P.W., Tang, Y.: In silico prediction of chemical Ames mutagenicity. J. Chem. Inf. Model. 52, 2840\u20132847 (2012)","journal-title":"J. Chem. Inf. Model."},{"key":"1586_CR45","doi-asserted-by":"publisher","first-page":"012,317","DOI":"10.1103\/PhysRevA.93.012317","volume":"93","author":"Z Zhu","year":"2016","unstructured":"Zhu, Z., Ochoa, A.J., Schnabel, S., Hamze, F., Katzgraber, H.G.: Best-case performance of quantum annealers on native spin-glass benchmarks: how chaos can affect success probabilities. Phys. Rev. A 93, 012,317 (2016)","journal-title":"Phys. Rev. A"},{"key":"1586_CR46","doi-asserted-by":"publisher","DOI":"10.1038\/srep11168","author":"KM Zick","year":"2015","unstructured":"Zick, K.M., Shehab, O., French, M.: Experimental quantum annealing: case study involving the graph isomorphism problem. Sci. Rep. (2015). doi: 10.1038\/srep11168","journal-title":"Sci. Rep."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-017-1586-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-017-1586-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-017-1586-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T16:49:38Z","timestamp":1568998178000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-017-1586-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,9]]},"references-count":46,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["1586"],"URL":"https:\/\/doi.org\/10.1007\/s11128-017-1586-y","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,9]]},"article-number":"133"}}