{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:47:06Z","timestamp":1773798426953,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T00:00:00Z","timestamp":1605484800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T00:00:00Z","timestamp":1605484800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s42484-020-00028-4","type":"journal-article","created":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T16:06:40Z","timestamp":1605542800000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Mapping graph coloring to quantum annealing"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4941-1009","authenticated-orcid":false,"given":"Carla","family":"Silva","sequence":"first","affiliation":[]},{"given":"Ana","family":"Aguiar","sequence":"additional","affiliation":[]},{"given":"Priscila M. V.","family":"Lima","sequence":"additional","affiliation":[]},{"given":"In\u00eas","family":"Dutra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,16]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Alom MZ, Van Essen B, Moody AT, Widemann DP, Taha TM (2017) Quadratic unconstrained binary optimization (QUBO) on neuromorphic computing system. In: 2017 International Joint Conference on Neural Networks (IJCNN), pp 3922\u20133929","DOI":"10.1109\/IJCNN.2017.7966350"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Bernal DE, Booth K EC, Dridi R, Alghassi H, Tayur S, Venturelli D (2019) Integer programming techniques for minor-embedding in quantum annealers","DOI":"10.1007\/978-3-030-58942-4_8"},{"key":"28_CR3","doi-asserted-by":"publisher","first-page":"14","DOI":"10.3389\/fict.2016.00014","volume":"3","author":"Z Bian","year":"2016","unstructured":"Bian Z, Chudak F, Israel RB, Lackey B, Macready WG, Roy A (2016) Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. Frontiers in ICT 3:14","journal-title":"Frontiers in ICT"},{"issue":"1","key":"28_CR4","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 AD, Roy A (2016) Fast clique minor generation in Chimera qubit connectivity graphs. Quantum Inf Process 15(1):495\u2013508","journal-title":"Quantum Inf Process"},{"issue":"1","key":"28_CR5","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"123","author":"E Boros","year":"2002","unstructured":"Boros E, Hammer PL (2002) Pseudo-Boolean optimization. Discret Appl Math 123(1):155\u2013225","journal-title":"Discret Appl Math"},{"key":"28_CR6","unstructured":"Cai J, Macready WG, Roy A (2014) A practical heuristic for finding graph minors"},{"issue":"4","key":"28_CR7","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s11128-019-2236-3","volume":"18","author":"P Date","year":"2019","unstructured":"Date P, Patton R, Schuman C, Potok T (2019) Efficiently embedding qubo problems on adiabatic quantum computers. Quantum Inf Process 18(4):117","journal-title":"Quantum Inf Process"},{"issue":"4","key":"28_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s11128-019-2236-3","volume":"18","author":"P Date","year":"2019","unstructured":"Date P, Patton R, Schuman C, Potok T (2019) Efficiently embedding QUBO problems on adiabatic quantum computers. Quantum Inf Process 18(4):117","journal-title":"Quantum Inf Process"},{"issue":"1","key":"28_CR9","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1051\/ita\/2011013","volume":"45","author":"D deFalco","year":"2011","unstructured":"deFalco D, Tamascelli D (2011) An introduction to quantum annealing. RAIRO - Theoretical Informatics and Applications 45(1):99\u2013116","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.3389\/fict.2019.00013","volume":"6","author":"S Feld","year":"2019","unstructured":"Feld S, Roch C, Gabor T, Seidel C, Neukart F, Galter I, Mauerer W, Linnhoff-Popien C (2019) A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Frontiers in ICT 6:13","journal-title":"Frontiers in ICT"},{"key":"28_CR11","unstructured":"Fujii K (2018) Quantum speedup in stoquastic adiabatic quantum computation"},{"issue":"4","key":"28_CR12","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10288-019-00424-y","volume":"17","author":"F Glover","year":"2019","unstructured":"Glover F, Kochenberger G, Du Y (2019) Quantum bridge analytics I: a tutorial on formulating and using QUBO models. 4OR 17(4):335\u2013371","journal-title":"4OR"},{"issue":"5","key":"28_CR13","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s11128-018-1863-4","volume":"17","author":"TD Goodrich","year":"2018","unstructured":"Goodrich TD, Sullivan BD, Humble TS (2018) Optimizing adiabatic quantum program compilation using a graph-theoretic framework. Quantum Inf Process 17(5):118","journal-title":"Quantum Inf Process"},{"key":"28_CR14","doi-asserted-by":"publisher","first-page":"034007","DOI":"10.1103\/PhysRevApplied.5.034007","volume":"5","author":"I Hen","year":"2016","unstructured":"Hen I, Spedalieri FM (2016) Quantum annealing for constrained optimization. Phys. Rev. Applied 5:034007","journal-title":"Phys. Rev. Applied"},{"issue":"1","key":"28_CR15","doi-asserted-by":"publisher","first-page":"12837","DOI":"10.1038\/s41598-019-49172-3","volume":"9","author":"K Ikeda","year":"2019","unstructured":"Ikeda K, Nakamura Y, Humble TS (2019) Application of quantum annealing to nurse scheduling problem. Scientific Reports 9(1):12837","journal-title":"Scientific Reports"},{"key":"28_CR16","unstructured":"Inc D-WS (2020) D-Wave. https:\/\/www.dwavesys.com"},{"key":"28_CR17","unstructured":"Inc D-WS (2020) Leap. https:\/\/cloud.dwavesys.com\/leap\/"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"Irie H, Wongpaisarnsin G, Terabe M, Miki A, Taguchi S (2019) Quantum annealing of vehicle routing problem with time, state and capacity. In: Feld S, Linnhoff-Popien C (eds) Quantum technology and optimization problems, Springer International Publishing, Cham, pp 145\u2013156","DOI":"10.1007\/978-3-030-14082-3_13"},{"issue":"6","key":"28_CR19","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"DS Johnson","year":"1989","unstructured":"Johnson DS, Aragon CR, McGeoch LA, Schevon C (1989) Optimization by simulated annealing: an experimental evaluation. part i, graph partitioning. Oper. Res. 37(6):865\u2013892","journal-title":"Oper. Res."},{"key":"28_CR20","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 (1998) Quantum annealing in the transverse ising model. Phys. Rev. E 58:5355\u20135363","journal-title":"Phys. Rev. E"},{"key":"28_CR21","first-page":"031026","volume":"5","author":"HG Katzgraber","year":"2015","unstructured":"Katzgraber HG, Hamze F, Zhu Z, Ochoa AJ, Munoz-Bauza H (2015) Seeking quantum speedup through spin glasses: the good, the bad, and the ugly. Phys. Rev. X 5:031026","journal-title":"Phys. Rev. X"},{"issue":"4598","key":"28_CR22","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 CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671\u2013680","journal-title":"Science"},{"issue":"2","key":"28_CR23","doi-asserted-by":"publisher","first-page":"022301","DOI":"10.1103\/PhysRevA.98.022301","volume":"98","author":"K Kudo","year":"2018","unstructured":"Kudo K (2018) Constrained quantum annealing of graph coloring. Phys Rev A 98(2):022301","journal-title":"Phys Rev A"},{"issue":"7285","key":"28_CR24","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1038\/nature08812","volume":"464","author":"TD Ladd","year":"2010","unstructured":"Ladd TD, Jelezko F, Laflamme R, Nakamura Y, Monroe C, O\u2019Brien JL (2010) Quantum computers. Nature 464(7285):45\u201353","journal-title":"Nature"},{"issue":"2","key":"28_CR25","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/net.21751","volume":"70","author":"M Lewis","year":"2017","unstructured":"Lewis M, Glover F (2017) Quadratic unconstrained binary optimization problem preprocessing: theory and empirical analysis. Networks 70(2):79\u201397","journal-title":"Networks"},{"key":"28_CR26","doi-asserted-by":"crossref","unstructured":"Lima P MV, Morveli-Espinoza MM, Pereira GC, Fran\u00e7a F MG (2005) Satyrus: a SAT-based neuro-symbolic architecture for constraint processing. In: Fifth International Conference on Hybrid Intelligent Systems (HIS\u201905), 6 pp.\u2013","DOI":"10.1109\/ICHIS.2005.97"},{"key":"28_CR27","unstructured":"Lima P MV (2017) Q-satyrus: mapping neuro-symbolic reasoning into an adiabatic quantum computer. In: Proceedings of the Twelfth International Workshop on Neural-Symbolic Learning and Reasoning, NeSy 2017, London, UK, July 17-18, 2017"},{"key":"28_CR28","doi-asserted-by":"crossref","unstructured":"Lima P MV, Pereira GC, Morveli-Espinoza M MM, Fran\u00e7a F MG (2005) Mapping and combining combinatorial problems into energy landscapes via pseudo-Boolean constraints. In: DeGregorio M, DiMaio V, Frucci M, Musio C (eds) Brain, vision, and artificial intelligence, Springer Berlin Heidelberg, Berlin, Heidelberg, pp 308\u2013317","DOI":"10.1007\/11565123_30"},{"key":"28_CR29","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas A (2014) Ising formulations of many NP problems. Frontiers in Physics 2:5","journal-title":"Frontiers in Physics"},{"key":"28_CR30","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 (2017) Traffic flow optimization using a quantum annealer. Frontiers in ICT 4:29","journal-title":"Frontiers in ICT"},{"key":"28_CR31","doi-asserted-by":"crossref","unstructured":"Nielsen MA, Chuang IL (2010) Quantum computation and quantum information","DOI":"10.1017\/CBO9780511976667"},{"issue":"1","key":"28_CR32","doi-asserted-by":"publisher","first-page":"2098","DOI":"10.1038\/s41598-018-38388-4","volume":"9","author":"S Okada","year":"2019","unstructured":"Okada S, Ohzeki M, Terabe M, Taguchi S (2019) Improving solutions by embedding larger subproblems in a D-Wave quantum annealer. Scientific Reports 9(1):2098","journal-title":"Scientific Reports"},{"issue":"5-6","key":"28_CR33","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1017\/S1471068418000066","volume":"18","author":"S Pakin","year":"2018","unstructured":"Pakin S (2018) Performing fully parallel constraint logic programming on a quantum annealer. Theory and Practice of Logic Programming 18(5-6):928\u2013949","journal-title":"Theory and Practice of Logic Programming"},{"issue":"1","key":"28_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11128-014-0892-x","volume":"14","author":"EG Rieffel","year":"2015","unstructured":"Rieffel EG, Venturelli D, O\u2019Gorman B, Do MB, Prystay EM, Smelyanskiy VN (2015) A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf Process 14 (1):1\u201336","journal-title":"Quantum Inf Process"},{"key":"28_CR35","unstructured":"Silva C, Dutra I (2020) Code [available.] https:\/\/github.com\/cmaps\/graphcoloring-quantumannealing"},{"issue":"2","key":"28_CR36","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0377-0427(01)00493-9","volume":"142","author":"B Szafnicki","year":"2002","unstructured":"Szafnicki B (2002) A unified approach for degree reduction of polynomials in the Bernstein basis part I: real polynomials. J Comput Appl Math 142(2):287\u2013312","journal-title":"J Comput Appl Math"},{"issue":"6","key":"28_CR37","doi-asserted-by":"publisher","first-page":"061010","DOI":"10.7566\/JPSJ.88.061010","volume":"88","author":"K Tanahashi","year":"2019","unstructured":"Tanahashi K, Takayanagi S, Motohashi T, Tanaka S (2019) Application of Ising machines and a software development for ising machines. J Phys Soc Jpn 88(6):061010","journal-title":"J Phys Soc Jpn"},{"key":"28_CR38","unstructured":"Tran TT, Do M, Rieffel EG, Frank J, Wang Z, O\u2019Gorman B, Venturelli D, Beck JC (2016) A hybrid quantum-classical approach to solving scheduling problems. In: Proceedings of the Ninth Annual Symposium on Combinatorial Search, SOCS 2016, Tarrytown, NY, USA, July 6-8, 2016, AAAI Press, pp 98\u2013106"},{"issue":"1","key":"28_CR39","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s42484-019-00001-w","volume":"1","author":"D Venturelli","year":"2019","unstructured":"Venturelli D, Kondratyev A (2019) Reverse quantum annealing approach to portfolio optimization problems. Quantum Machine Intelligence 1(1):17\u201330","journal-title":"Quantum Machine Intelligence"},{"key":"28_CR40","doi-asserted-by":"crossref","unstructured":"Vysko\u010dil T, Pakin S, Djidjev HN (2019) Embedding inequality constraints for quantum annealing optimization. In: Feld S, Linnhoff-Popien C (eds) Quantum technology and optimization problems, Springer International Publishing, Cham, pp 11\u201322","DOI":"10.1007\/978-3-030-14082-3_2"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00028-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s42484-020-00028-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00028-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,21]],"date-time":"2020-12-21T17:06:05Z","timestamp":1608570365000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s42484-020-00028-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,16]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["28"],"URL":"https:\/\/doi.org\/10.1007\/s42484-020-00028-4","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,16]]},"assertion":[{"value":"11 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"16"}}