{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T16:01:13Z","timestamp":1762444873997,"version":"3.40.3"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030140816"},{"type":"electronic","value":"9783030140823"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-14082-3_3","type":"book-chapter","created":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T17:58:03Z","timestamp":1550512683000},"page":"23-35","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Assessing Solution Quality of 3SAT on a Quantum Annealing Platform"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Gabor","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Zielinski","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Feld","sequence":"additional","affiliation":[]},{"given":"Christoph","family":"Roch","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Seidel","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Neukart","sequence":"additional","affiliation":[]},{"given":"Isabella","family":"Galter","sequence":"additional","affiliation":[]},{"given":"Wolfgang","family":"Mauerer","sequence":"additional","affiliation":[]},{"given":"Claudia","family":"Linnhoff-Popien","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,2,19]]},"reference":[{"key":"3_CR1","unstructured":"Adams, D.: The Hitchhiker\u2019s Guide to the Galaxy (1979)"},{"key":"3_CR2","unstructured":"Albash, T., Lidar, D.A.: Adiabatic quantum computing. arXiv:1611.04471 (2016)"},{"issue":"25","key":"3_CR3","doi-asserted-by":"publisher","first-page":"6715","DOI":"10.1021\/j100127a023","volume":"97","author":"P Amara","year":"1993","unstructured":"Amara, P., Hsu, D., Straub, J.E.: Global energy minimum searches using an approximate solution of the imaginary time Schr\u00f6dinger equation. J. Phys. Chem. 97(25), 6715\u20136721 (1993)","journal-title":"J. Phys. Chem."},{"issue":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0304-4149(89)90040-9","volume":"33","author":"B Apolloni","year":"1989","unstructured":"Apolloni, B., Carvalho, C., De Falco, D.: Quantum stochastic optimization. Stoch. Process. Their Appl. 33(2), 233\u2013244 (1989)","journal-title":"Stoch. Process. Their Appl."},{"key":"3_CR5","unstructured":"Apolloni, B., De Falco, D., Cesa-Bianchi, N.: A numerical implementation of \u201cquantum annealing\u201d. Technical report (1988)"},{"key":"3_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, 1st edn. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-3-642-58412-1","edition":"1"},{"key":"3_CR7","unstructured":"Benjamin, S.C., Zhao, L., Fitzsimons, J.F.: Measurement-driven quantum computing: Performance of a 3-SAT solver. arXiv:1711.02687 (2017)"},{"issue":"5","key":"3_CR8","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput. 26(5), 1411\u20131473 (1997)","journal-title":"SIAM J. Comput."},{"issue":"6412","key":"3_CR9","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1126\/science.aar3106","volume":"362","author":"S Bravyi","year":"2018","unstructured":"Bravyi, S., Gosset, D., Koenig, R.: Quantum advantage with shallow circuits. Science 362(6412), 308\u2013311 (2018)","journal-title":"Science"},{"key":"3_CR10","unstructured":"Cheeseman, P.C., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: IJCAI, vol. 91 (1991)"},{"issue":"6","key":"3_CR11","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1016\/0893-6080(95)00033-V","volume":"8","author":"L Chen","year":"1995","unstructured":"Chen, L., Aihara, K.: Chaotic simulated annealing by a neural network model with transient chaos. Neural Netw. 8(6), 915\u2013930 (1995)","journal-title":"Neural Netw."},{"key":"3_CR12","unstructured":"Choi, V.: Adiabatic quantum algorithms for the NP-complete maximum-weight independent set, exact cover and 3SAT problems. arXiv:1004.2226 (2010)"},{"issue":"7\u20138","key":"3_CR13","first-page":"638","volume":"11","author":"V Choi","year":"2011","unstructured":"Choi, V.: Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems. Quant. Inform. Comput. 11(7\u20138), 638\u2013648 (2011)","journal-title":"Quant. Inform. Comput."},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. ACM (1971)","DOI":"10.1145\/800157.805047"},{"key":"3_CR15","unstructured":"D-Wave Systems: Postprocessing Methods on D-Wave Systems (2016)"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Ding, J., Sly, A., Sun, N.: Proof of the satisfiability conjecture for large k. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing, STOC 2015. ACM, New York (2015)","DOI":"10.1145\/2746539.2746619"},{"key":"3_CR17","unstructured":"Farhi, E., Goldstone, J., Gosset, D., Gutmann, S., Meyer, H.B., Shor, P.: Quantum adiabatic algorithms, small gaps, and different paths. arXiv:0909.4766 (2009)"},{"key":"3_CR18","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution. arXiv preprint quant-ph\/0001106 (2000)"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Feld, S., et al.: A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. arXiv preprint arXiv:1811.07403 (2018)","DOI":"10.3389\/fict.2019.00013"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"RP Feynman","year":"1982","unstructured":"Feynman, R.P.: Simulating physics with computers. Int. J. Theor. Phys. 21, 467\u2013488 (1982)","journal-title":"Int. J. Theor. Phys."},{"issue":"5\u20136","key":"3_CR21","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0009-2614(94)00117-0","volume":"219","author":"A Finnila","year":"1994","unstructured":"Finnila, A., Gomez, M., Sebenik, C., Stenson, C., Doll, J.: Quantum annealing: a new method for minimizing multidimensional functions. Chem. Phys. Lett. 219(5\u20136), 343\u2013348 (1994)","journal-title":"Chem. Phys. Lett."},{"issue":"10","key":"3_CR22","doi-asserted-by":"publisher","first-page":"1276","DOI":"10.1287\/mnsc.40.10.1276","volume":"40","author":"M Gendreau","year":"1994","unstructured":"Gendreau, M., Hertz, A., Laporte, G.: A Tabu search heuristic for the vehicle routing problem. Manag. Sci. 40(10), 1276\u20131290 (1994)","journal-title":"Manag. Sci."},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"3261","DOI":"10.1007\/978-1-4419-7997-1_17","volume-title":"Handbook of Combinatorial Optimization","author":"F Glover","year":"2013","unstructured":"Glover, F., Laguna, M.: Tabu search*. In: Pardalos, P.M., Du, D.-Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 3261\u20133362. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4419-7997-1_17"},{"key":"3_CR24","unstructured":"Heim, B., Brown, E.W., Wecker, D., Troyer, M.: Designing adiabatic quantum optimization: a case study for the TSP. arXiv:1702.06248 (2017)"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Hsu, T.J., Jin, F., Seidel, C., Neukart, F., De Raedt, H., Michielsen, K.: Quantum annealing with anneal path control: application to 2-SAT problems with known energy landscapes. arXiv:1810.00194 (2018)","DOI":"10.4208\/cicp.OA-2018-0257"},{"issue":"5","key":"3_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(5), 5355 (1998)","journal-title":"Phys. Rev. E"},{"issue":"4598","key":"3_CR27","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671\u2013680 (1983)","journal-title":"Science"},{"issue":"5163","key":"3_CR28","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S Kirkpatrick","year":"1994","unstructured":"Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random Boolean expressions. Science 264(5163), 1297\u20131301 (1994)","journal-title":"Science"},{"key":"3_CR29","unstructured":"Klauck, H.: The complexity of quantum disjointness. In: Leibniz International Proceedings in Informatics, vol. 83. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"3_CR30","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A.: Ising formulations of many NP problems. Front. Phys. 2, 5 (2014)","journal-title":"Front. Phys."},{"issue":"7","key":"3_CR31","doi-asserted-by":"publisher","first-page":"070502","DOI":"10.1103\/PhysRevLett.118.070502","volume":"118","author":"S Mandra","year":"2017","unstructured":"Mandra, S., Zhu, Z., Katzgraber, H.G.: Exponentially biased ground-state sampling of quantum annealing machines with transverse-field driving hamiltonians. Phys. Rev. Lett. 118(7), 070502 (2017)","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"3_CR32","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/s00037-005-0194-x","volume":"14","author":"C Marriott","year":"2005","unstructured":"Marriott, C., Watrous, J.: Quantum Arthur-Merlin games. Comput. Complex. 14(2), 122\u2013152 (2005)","journal-title":"Comput. Complex."},{"issue":"2","key":"3_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00585ED1V01Y201407QMC008","volume":"5","author":"CC McGeoch","year":"2014","unstructured":"McGeoch, C.C.: Adiabatic quantum computation and quantum annealing: theory and practice. Synth. Lect. Quantum Comput. 5(2), 1\u201393 (2014)","journal-title":"Synth. Lect. Quantum Comput."},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"McGeoch, C.C., Wang, C.: Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. In: Proceedings of the ACM International Conference on Computing Frontiers. ACM (2013)","DOI":"10.1145\/2482767.2482797"},{"issue":"5","key":"3_CR35","doi-asserted-by":"publisher","first-page":"056126","DOI":"10.1103\/PhysRevE.66.056126","volume":"66","author":"M M\u00e9zard","year":"2002","unstructured":"M\u00e9zard, M., Zecchina, R.: Random k-satisfiability problem: from an analytic solution to an efficient algorithm. Phys. Rev. E 66(5), 056126 (2002)","journal-title":"Phys. Rev. E"},{"issue":"21","key":"3_CR36","doi-asserted-by":"publisher","first-page":"3881","DOI":"10.1103\/PhysRevLett.76.3881","volume":"76","author":"R Monasson","year":"1996","unstructured":"Monasson, R., Zecchina, R.: Entropy of the k-satisfiability problem. Phys. Rev. Lett. 76(21), 3881 (1996)","journal-title":"Phys. Rev. Lett."},{"issue":"6740","key":"3_CR37","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R Monasson","year":"1999","unstructured":"Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic \u201cphase transitions\u201d. Nature 400(6740), 133 (1999)","journal-title":"Nature"},{"key":"3_CR38","doi-asserted-by":"crossref","unstructured":"Morimae, T., Nishimura, H.: Merlinization of complexity classes above BQP. arXiv:1704.01514 (2017)","DOI":"10.26421\/QIC17.11-12-3"},{"issue":"3","key":"3_CR39","doi-asserted-by":"publisher","first-page":"032323","DOI":"10.1103\/PhysRevA.95.032323","volume":"95","author":"DJ Moylett","year":"2017","unstructured":"Moylett, D.J., Linden, N., Montanaro, A.: Quantum speedup of the traveling-salesman problem for bounded-degree graphs. Phys. Rev. A 95(3), 032323 (2017)","journal-title":"Phys. Rev. A"},{"issue":"2","key":"3_CR40","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117\u2013129 (1987)","journal-title":"Math. Program."},{"key":"3_CR41","doi-asserted-by":"publisher","first-page":"29","DOI":"10.3389\/fict.2017.00029","volume":"4","author":"F Neukart","year":"2017","unstructured":"Neukart, F., Compostella, G., Seidel, C., von Dollen, D., Yarkoni, S., Parney, B.: Traffic flow optimization using a quantum annealer. Front. ICT 4, 29 (2017)","journal-title":"Front. ICT"},{"issue":"6195","key":"3_CR42","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., et al.: Defining and detecting quantum speedup. Science 345(6195), 420\u2013424 (2014)","journal-title":"Science"},{"issue":"5","key":"3_CR43","doi-asserted-by":"publisher","first-page":"050501","DOI":"10.1103\/PhysRevLett.109.050501","volume":"109","author":"RD Somma","year":"2012","unstructured":"Somma, R.D., Nagaj, D., Kieferov\u00e1, M.: Quantum speedup by quantum annealing. Phys. Rev. Lett. 109(5), 050501 (2012)","journal-title":"Phys. Rev. Lett."},{"key":"3_CR44","unstructured":"Strand, J., Przybysz, A., Ferguson, D., Zick, K.: ZZZ coupler for native embedding of MAX-3SAT problem instances in quantum annealing hardware. In: APS Meeting Abstracts (2017)"},{"key":"3_CR45","doi-asserted-by":"crossref","unstructured":"Van Dam, W., Mosca, M., Vazirani, U.: How powerful is adiabatic quantum computation? In: 42nd IEEE Symposium on Foundations of Computer Science. IEEE (2001)","DOI":"10.1109\/SFCS.2001.959902"},{"issue":"2","key":"3_CR46","first-page":"101","volume":"2","author":"RH Warren","year":"2017","unstructured":"Warren, R.H.: Small traveling salesman problems. J. Adv. Appl. Math. 2(2), 101\u2013107 (2017)","journal-title":"J. Adv. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Quantum Technology and Optimization Problems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-14082-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T02:04:37Z","timestamp":1662948277000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-14082-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030140816","9783030140823"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-14082-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"19 February 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"QTOP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Quantum Technology and Optimization Problems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 March 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 March 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"qtop2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/netsys2019.org\/workshops\/qtop19\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}