{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:21Z","timestamp":1750219941079,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":24,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,15]],"date-time":"2023-07-15T00:00:00Z","timestamp":1689379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Bundesministerium f\u00fcr Bildung und Forschung","award":["13N16196"],"award-info":[{"award-number":["13N16196"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,15]]},"DOI":"10.1145\/3583133.3596330","type":"proceedings-article","created":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T23:30:33Z","timestamp":1690241433000},"page":"2263-2271","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-0894-8996","authenticated-orcid":false,"given":"Sebastian","family":"Zielinski","sequence":"first","affiliation":[{"name":"LMU Munich, Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7129-1237","authenticated-orcid":false,"given":"Jonas","family":"N\u00fc\u00dflein","sequence":"additional","affiliation":[{"name":"LMU Munich, Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5727-9151","authenticated-orcid":false,"given":"Jonas","family":"Stein","sequence":"additional","affiliation":[{"name":"LMU Munich, Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2048-8667","authenticated-orcid":false,"given":"Thomas","family":"Gabor","sequence":"additional","affiliation":[{"name":"LMU Munich, Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6284-9286","authenticated-orcid":false,"given":"Claudia","family":"Linnhoff-Popien","sequence":"additional","affiliation":[{"name":"LMU Munich, Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2782-1469","authenticated-orcid":false,"given":"Sebastian","family":"Feld","sequence":"additional","affiliation":[{"name":"Delft University of Technology, Delft, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Physics and Geometry: Proceedings of the Ascona-Locarno Conference. 97--111","author":"Apolloni Bruno","year":"1990","unstructured":"Bruno Apolloni , Nicol\u00f2 Cesa-Bianchi , and Diego De Falco . 1990 . A numerical implementation of \"quantum annealing\". In Stochastic Processes , Physics and Geometry: Proceedings of the Ascona-Locarno Conference. 97--111 . Bruno Apolloni, Nicol\u00f2 Cesa-Bianchi, and Diego De Falco. 1990. A numerical implementation of \"quantum annealing\". In Stochastic Processes, Physics and Geometry: Proceedings of the Ascona-Locarno Conference. 97--111."},{"volume-title":"Computational complexity: a modern approach","author":"Arora Sanjeev","key":"e_1_3_2_1_2_1","unstructured":"Sanjeev Arora and Boaz Barak . 2009. Computational complexity: a modern approach . Cambrtidge University Press . Sanjeev Arora and Boaz Barak. 2009. Computational complexity: a modern approach. Cambrtidge University Press."},{"key":"e_1_3_2_1_3_1","volume-title":"A practical heuristic for finding graph minors. arXiv preprint arXiv:1406.2741","author":"Cai Jun","year":"2014","unstructured":"Jun Cai , William G Macready , and Aidan Roy . 2014. A practical heuristic for finding graph minors. arXiv preprint arXiv:1406.2741 ( 2014 ). Jun Cai, William G Macready, and Aidan Roy. 2014. A practical heuristic for finding graph minors. arXiv preprint arXiv:1406.2741 (2014)."},{"key":"e_1_3_2_1_4_1","volume-title":"A direct mapping of Max k-SAT and high order parity checks to a chimera graph. Scientific reports 6, 1","author":"Chancellor Nicholas","year":"2016","unstructured":"Nicholas Chancellor , Stefan Zohren , Paul A Warburton , Simon C Benjamin , and Stephen Roberts . 2016. A direct mapping of Max k-SAT and high order parity checks to a chimera graph. Scientific reports 6, 1 ( 2016 ), 37107. Nicholas Chancellor, Stefan Zohren, Paul A Warburton, Simon C Benjamin, and Stephen Roberts. 2016. A direct mapping of Max k-SAT and high order parity checks to a chimera graph. Scientific reports 6, 1 (2016), 37107."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-008-0082-9"},{"key":"e_1_3_2_1_6_1","volume-title":"Adiabatic quantum algorithms for the NP-complete maximum-weight independent set, exact cover and 3SAT problems. arXiv preprint arXiv:1004.2226","author":"Choi Vicky","year":"2010","unstructured":"Vicky Choi . 2010. Adiabatic quantum algorithms for the NP-complete maximum-weight independent set, exact cover and 3SAT problems. arXiv preprint arXiv:1004.2226 ( 2010 ). Vicky Choi. 2010. Adiabatic quantum algorithms for the NP-complete maximum-weight independent set, exact cover and 3SAT problems. arXiv preprint arXiv:1004.2226 (2010)."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"volume-title":"Algorithms","author":"Dasgupta Sanjoy","key":"e_1_3_2_1_8_1","unstructured":"Sanjoy Dasgupta , Christos H Papadimitriou , and Umesh Virkumar Vazirani . 2008. Algorithms . McGraw-Hill Higher Education New York . Sanjoy Dasgupta, Christos H Papadimitriou, and Umesh Virkumar Vazirani. 2008. Algorithms. McGraw-Hill Higher Education New York."},{"key":"e_1_3_2_1_9_1","volume-title":"QUBO formulations for training machine learning models. Scientific reports 11, 1","author":"Date Prasanna","year":"2021","unstructured":"Prasanna Date , Davis Arthur , and Lauren Pusey-Nazzaro . 2021. QUBO formulations for training machine learning models. Scientific reports 11, 1 ( 2021 ), 10029. Prasanna Date, Davis Arthur, and Lauren Pusey-Nazzaro. 2021. QUBO formulations for training machine learning models. Scientific reports 11, 1 (2021), 10029."},{"key":"e_1_3_2_1_10_1","volume-title":"A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 5516","author":"Farhi Edward","year":"2001","unstructured":"Edward Farhi , Jeffrey Goldstone , Sam Gutmann , Joshua Lapan , Andrew Lundgren , and Daniel Preda . 2001. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 5516 ( 2001 ), 472--475. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. 2001. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 5516 (2001), 472--475."},{"key":"e_1_3_2_1_11_1","volume-title":"Quantum computation by adiabatic evolution. arXiv preprint quant-ph\/0001106","author":"Farhi Edward","year":"2000","unstructured":"Edward Farhi , Jeffrey Goldstone , Sam Gutmann , and Michael Sipser . 2000. Quantum computation by adiabatic evolution. arXiv preprint quant-ph\/0001106 ( 2000 ). Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. 2000. Quantum computation by adiabatic evolution. arXiv preprint quant-ph\/0001106 (2000)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-14082-3_3"},{"key":"e_1_3_2_1_13_1","volume-title":"ECAI","volume":"94","author":"Gent Ian P","year":"1994","unstructured":"Ian P Gent and Toby Walsh . 1994 . The SAT phase transition . In ECAI , Vol. 94 . PITMAN, 105--109. Ian P Gent and Toby Walsh. 1994. The SAT phase transition. In ECAI, Vol. 94. PITMAN, 105--109."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412700.1412710"},{"key":"e_1_3_2_1_15_1","volume-title":"Application of quantum annealing to nurse scheduling problem. Scientific reports 9, 1","author":"Ikeda Kazuki","year":"2019","unstructured":"Kazuki Ikeda , Yuma Nakamura , and Travis S Humble . 2019. Application of quantum annealing to nurse scheduling problem. Scientific reports 9, 1 ( 2019 ), 1--10. Kazuki Ikeda, Yuma Nakamura, and Travis S Humble. 2019. Application of quantum annealing to nurse scheduling problem. Scientific reports 9, 1 (2019), 1--10."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.58.5355"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387940.3391472"},{"key":"e_1_3_2_1_18_1","volume-title":"Ising formulations of many NP problems. Frontiers in physics 2","author":"Lucas Andrew","year":"2014","unstructured":"Andrew Lucas . 2014. Ising formulations of many NP problems. Frontiers in physics 2 ( 2014 ), 5. Andrew Lucas. 2014. Ising formulations of many NP problems. Frontiers in physics 2 (2014), 5."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3019344"},{"key":"e_1_3_2_1_20_1","volume-title":"Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization. arXiv preprint arXiv:2302.03536","author":"N\u00fc\u00dflein Jonas","year":"2023","unstructured":"Jonas N\u00fc\u00dflein , Sebastian Zielinski , Thomas Gabor , Claudia Linnhoff-Popien , and Sebastian Feld . 2023. Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization. arXiv preprint arXiv:2302.03536 ( 2023 ). Jonas N\u00fc\u00dflein, Sebastian Zielinski, Thomas Gabor, Claudia Linnhoff-Popien, and Sebastian Feld. 2023. Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization. arXiv preprint arXiv:2302.03536 (2023)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.3390\/a12110224"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.39.11828"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387902.3392635"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"}],"event":{"name":"GECCO '23 Companion: Companion Conference on Genetic and Evolutionary Computation","sponsor":["SIGEVO ACM Special Interest Group on Genetic and Evolutionary Computation"],"location":"Lisbon Portugal","acronym":"GECCO '23 Companion"},"container-title":["Proceedings of the Companion Conference on Genetic and Evolutionary Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583133.3596330","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583133.3596330","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:54Z","timestamp":1750182534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583133.3596330"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,15]]},"references-count":24,"alternative-id":["10.1145\/3583133.3596330","10.1145\/3583133"],"URL":"https:\/\/doi.org\/10.1145\/3583133.3596330","relation":{},"subject":[],"published":{"date-parts":[[2023,7,15]]},"assertion":[{"value":"2023-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}